Do you think IIT Guwahati certified course can help you in your career?
Introduction
Hello Ninjas! Hope your preparation is going smoothly. The Array data structure is one of the most used data structures and also the most asked in the interviews. We have brought you an important question on the array to boost your preparation.
In this article, we will solve the problem of finding the array obtained by repeatedly reversing the array after every insertion from the given array. We will look at different approaches and codes for the same in multiple programming languages.
Problem Statement
You've been given an array, 'A', of size 'N'. You need to find the array obtained by repeatedly reversing the array after every intersection from the given array. Print the array obtained.
Example
Input
N = 4
A = [ 2, 4, 6, 8 ]
Where 'N' is the size of the array, and 'A' represents the input array.
Output
8 4 2 6
Explanation
After the first iteration, the array will be: [ 2 ].
After the second iteration, array = [ 4, 2 ].
After the third iteration, array = [ 6, 2, 4 ].
After the fourth iteration, array = [ 8, 4, 2, 6 ].
Please try to solve this problem on your own before moving on to further discussion.
First, let's see the Naive approach to solving this problem.
Naive/Brute Force Approach
The very basic approach we can think of is to insert an element at each step and then reverse the array using a reverse function.
Algorithm
Initialize an empty array of the size N.
Iterate the input array and perform these steps for each element:
Insert the element in the resultant array.
Reverse the array after insertion.
Print the resultant array
Dry Run
Let's suppose the following input is given:
N = 4
Array = { 2, 4, 6, 8 }
The array is empty initially A = { }.
Iteration 1
After inserting the 1st element, A = {2}. After reversing the array A = {2}.
Iteration 2
After inserting the 2nd element, A = {2, 4}. After reversing the array A = {4, 2}.
Iteration 3
After inserting the 3rd element, A = {4, 2, 6}. After reversing the array A = {6, 2, 4}.
Iteration 4
After inserting the 4th element, A = {6, 2, 4, 8}, and after reversing the array, The final array is A = {8, 4, 2, 6}.
C++ Implementation
#include<iostream>
using namespace std;
// Function to reverse an array
void reverse(int A[], int s, int e) {
while(s<e) {
int temp = A[s];
A[s] = A[e];
A[e] = temp;
s++; e--;
}
}
int main() {
int N = 4;
int A[4] = {2, 4, 6, 8};
int res[4];
// Input Array
cout<<"Input Array: ";
for(int i=0;i<N;i++) {
cout<<A[i]<<" ";
}
cout<<endl;
/*
Inserting the element into the resultant array
Reversing the array
*/
for(int i=0;i<N;i++) {
res[i] = A[i];
reverse(res, 0, i);
}
// Resultant Array
cout<<"Resultant Array: ";
for(int i=0;i<N;i++) {
cout<<res[i]<<" ";
}
return 0;
}
You can also try this code with Online C++ Compiler
import array as arr
# Function to reverse an array
def reverse(A, s, e):
while(s<e):
temp = A[s];
A[s] = A[e];
A[e] = temp;
s = s+1;
e = e-1;
N = 4
A = arr.array('i', [2, 4, 6, 8])
res = arr.array('i', [0, 0, 0, 0])
# Input Array
print("Input Array: ", end=" ")
for i in A:
print(i, end = " ")
print()
# Inserting the element to the resultant array
# Reversing the array
for i in range(N):
res[i] = A[i]
reverse(res, 0, i)
# Resultant Array
print("Resultant Array: ", end=" ")
for i in res:
print(i, end = " ")
print()
You can also try this code with Online Python Compiler
The time complexity for the above solution is O(N * N) (where N represents the number of elements) because we are iterating the full array, and for each iteration, we are reversing the array, which takes O(N) time.
Space Complexity
The space complexity for the above solution is O(N) ('N' is the number of elements in the given array) as the resultant array takes O(N) space.
Optimized Approach
The efficient approach to this problem could be using Double-Ended Queue, or Deque, which allows insertion and deletion at both ends.
There will be two cases:-
If the index for the current element is even, then we will push the element at the end of the deque.
If the current element's index is odd, then we will push the current element at the start of the deque. Adding a first will make sure that the array is automatically reversed.
Algorithm
First, initialize a Double-Ended Queue to store the results.
Iterate the input array and perform this step for each element:
Push the element at the start of the deque if the index is odd.
If the index is even, then push the element at the end of the deque.
Once the iteration is complete, copy the contents of Deque into a resultant array
If the size of the array is odd, reverse the resultant array.
Print the resultant array
Dry Run
Initialize a deque first and traverse the input array
Index 0
For index: 0, since zero is even, Push the element at the end of the deque.
Index 1
Since one is odd, Push the element at the start of the deque.
Index 2
Since two is even, Push the element at the end of the deque.
Index 3
The index three is odd; Push the element at the start of the deque.
C++ Implementation
#include<iostream>
#include<deque>
#include<algorithm>
using namespace std;
int main() {
int N = 4;
int A[4] = {2, 4, 6, 8};
int res[4];
deque<int> dq;
// Input Array
cout<<endl<<"Input Array: ";
for(int i=0;i<N;i++) {
cout<<A[i]<<" ";
}
cout<<endl;
/*
If the index is even, insert it at back of deque
Else if the index is odd, insert it at front of deque
*/
for(int i=0;i<N;i++) {
if(i % 2 == 0) {
dq.push_back(A[i]);
}
else {
dq.push_front(A[i]);
}
}
// Copy the contents of the deque
int i=0;
for(auto x: dq) {
res[i++] = x;
}
// Reverse the result if size is odd
if(N%2==1){
reverse(res, res+N);
}
// Resultant Array
cout<<"Resultant Array: ";
for(int i=0;i<N;i++) {
cout<<res[i]<<" ";
}
cout<<endl;
return 0;
}
You can also try this code with Online C++ Compiler
import java.io.*;
import java.util.*;
class main {
// Function to reverse an array
static void reverse (int A[], int s, int e) {
while(s<e) {
int temp = A[s];
A[s] = A[e];
A[e] = temp;
s++; e--;
}
}
public static void main (String[] args) {
int N = 4;
int A[] = {2, 4, 6, 8};
int res[] = {0, 0 ,0, 0};
Deque<Integer> dq = new LinkedList<>();
// Input Array
System.out.print("Input Array: ");
for(int i=0;i<N;i++) {
System.out.print(A[i] + " ");
}
System.out.println();
/*
If the index is even, insert it at back of deque
Else if the index is odd, insert it at front of deque
*/
for(int i=0;i<N;i++) {
if(i % 2 == 0) {
dq.add(A[i]);
}
else {
dq.addFirst(A[i]);
}
}
// Copy the contents of the deque
int j=0;
for(int x : dq) {
res[j++] = x;
}
// Reverse the result if size is odd
if(N%2==1){
reverse(res, 0, N-1);
}
// Resultant Array
System.out.print("Resultant Array: ");
for(int i=0;i<N;i++) {
System.out.print(res[i] + " ");
}
}
}
You can also try this code with Online Java Compiler
from collections import deque
import array as arr
# Function to reverse an array
def reverse(A, s, e):
while(s<e):
temp = A[s];
A[s] = A[e];
A[e] = temp;
s = s+1;
e = e-1;
N = 4
A = arr.array('i', [2, 4, 6, 8])
res = arr.array('i', [0, 0, 0, 0])
dq = deque()
# Input Array
print("Input Array: ", end=" ")
for i in A:
print(i, end = " ")
print()
# If the index is even, insert it at back of deque
# Else if the index is odd, insert it at front of deque
for i in range(N):
if(i % 2 == 0):
dq.append(A[i]);
else:
dq.appendleft(A[i]);
# Copy the contents of the deque
j = 0
for x in dq:
res[j] = x
j = j+1
# Reverse the result if size is odd
if(N%2==1):
reverse(res, 0, N-1)
# Resultant Array
print("Resultant Array: ", end=" ")
for i in res:
print(i, end = " ")
print()
You can also try this code with Online Python Compiler
The time complexity for the optimized approach is O(N) ('N' is the number of elements in the given array) because we are just iterating the array once and insertion in deque cost O(1) time.
Space Complexity
The space complexity for the above approach is O(N) ('N' is the number of elements in the given array) because we are maintaining a Deque, which will store all the elements.
An array data structure consists of a collection of elements, each of which is identified by at least one array index or key. An array is stored in such a way that the position of the individual elements can be calculated using a mathematical formula from its index tuple.
What do you mean by a Deque?
A deque is a data structure that stands for "double-ended queue." It is similar to a queue or a stack but allows you to add and remove elements from either end of the queue. Deques are often implemented as dynamic arrays, which means that they can grow or shrink as needed.
What operations can you perform on a Deque?
There are several common operations that can be performed on a deque, including the following: push_front(), push_back(), pop_front(), pop_back(), front(), back(), empty(), and size().
What is the advantage of a Deque over a Queue?
Deques allow you to add and remove elements from both ends of the data structure, whereas, with a queue, you can only add elements to the back and remove them from the front. This can be useful in certain situations where you need to efficiently add or remove elements from both ends of the data structure.
What is the time complexity of push operations in deque?
If the deque is implemented as a dynamic array, the time complexity of both push_front and push_back is typically O(1) on average. However, in the worst case, such as when the array is full and needs to be resized, the time complexity can be O(n).
Conclusion
In the article, we have learned about a coding problem of finding the array obtained by repeatedly reversing the array after every insertion from the given array. We have seen two approaches, the brute force, and the optimized method. We have also analyzed the time and space complexity for both.
To solve more such problems, you can check out our other blogs:
237+ registered 
