Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
2.1.1.
Input
2.1.2.
Output
2.1.3.
Explanation
3.
Naive/Brute Force Approach
3.1.
Algorithm
3.2.
Dry Run
3.2.1.
Iteration 1
3.2.2.
Iteration 2
3.2.3.
Iteration 3
3.2.4.
Iteration 4
3.3.
C++ Implementation
3.4.
Java Implementation
3.5.
Python Implementation
3.6.
Output
3.7.
Time Complexity
3.8.
Space Complexity
4.
Optimized Approach
4.1.
Algorithm
4.2.
Dry Run
4.2.1.
Index 0
4.2.2.
Index 1
4.2.3.
Index 2
4.2.4.
Index 3
4.3.
C++ Implementation
4.4.
Java Implementation
4.5.
Python Implementation
4.6.
Output
4.7.
Time Complexity
4.8.
Space Complexity
5.
Frequently Asked Questions
5.1.
What is an Array?
5.2.
What do you mean by a Deque?
5.3.
What operations can you perform on a Deque?
5.4.
What is the advantage of a Deque over a Queue?
5.5.
What is the time complexity of push operations in deque?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Array Obtained by Repeatedly Reversing Array after Every Insertion from the Given Array

Career growth poll
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.

Array Obtained by Repeatedly Reversing the Array After Every Insertion from the Given Array

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 1

Iteration 2

After inserting the 2nd element, A = {2, 4}. After reversing the array A = {4, 2}.

Iteration 2

Iteration 3

After inserting the 3rd element, A = {4, 2, 6}. After reversing the array A = {6, 2, 4}.

Iteration 3

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}.

Iteration 4

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
Run Code

Java Implementation

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};
 
		// Input Array
		System.out.print("Input Array: ");
		for(int i=0;i<N;i++) {
			System.out.print(A[i] + " ");
		}
		System.out.println();
 
		/*
			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
		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
Run Code

Python Implementation

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
Run Code

Output

Output

Time Complexity

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 0

Index 1

Since one is odd, Push the element at the start of the deque.

Index 1

Index 2

Since two is even, Push the element at the end of the deque.

Index 2

Index 3

The index three is odd; Push the element at the start of the deque.

Index 3

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
Run Code

Java Implementation

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
Run Code

Python Implementation

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
Run Code

Output

Output

Time Complexity

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.

Also see,  Rabin Karp Algorithm

Must Read  C Program to Reverse a Number

Frequently Asked Questions

What is an Array?

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:

 

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem Design, etc. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and so much more!

Happy Learning, Ninjas!

Live masterclass