Array obtained by repeatedly reversing array after every insertion from the given array

Nishant Rana
Last Updated: May 13, 2022

Introduction

In the coding genre, Arrays are the base for every data structure. It collects variables of the same data type like integers, floating-point numbers, etc.

The array index starts from 0. So, to access the first element in an array, we can directly use arr[0].

In this problem, we have to reverse the array after every insertion, which is the slight variation of reverse the array. For solving this problem, your concept should be clear about arrays. 

 

Problem Statement

We are given an array, and our task is to print the array obtained by inserting the elements and reversing the array after every operation.

 

Example:

 

Input: 1 2 3 

Output: 3 1 2

 

Iteration 1 - arr1[]={1} (Inserting)

                   arr1[]={1} (Reversing the array}

Iteration 2 - arr1[]={1,2}(Inserting)

                   arr1[]={2,1}(Reversing the array)

Iteration 3 - arr1[]={2,1,3}(Inserting)

                   arr1[]={3,1,2}(Reversing the Array)

 

We will be heading to two approaches to solve this problem.

 

Approach 1: Naive

A simple approach is to traverse the array and insert the elements one by one and then reversing the array after each insertion.

 

 public class Main {
    
    // Function for reversing the array
    public static void reverse(int arr[],int start,int end) {
            while(start<end) {
            int temp=arr[start];
            arr[start]=arr[end];
            arr[end]=temp;
            start++;
            end--;
            }
     }

    public static void main(String[] args) {
            int n=3;
            int arr[]= {1,2,3};
            int arr1[]=new int[n];

           for(int i=0;i<n;i++) {
           arr1[i]=arr[i];
           reverse(arr1,0,i);
           }

          for(int j=0;j<n;j++) {
          System.out.println(arr1[j]);
          }
    }
}
 
 

 

Output:

 

3 
1
2

 

 

Analysis of Complexity:

Time Complexity: The time complexity for the above approach is O(N * N) (where N is the number of elements) because we are inserting N elements and for each insertion, we are reversing the array which takes O(N) time.

Space Complexity: The space complexity for the above approach is O(1) because we are not using any auxiliary space.

Approach 2: Efficient

 

The efficient approach to this problem could be using Double-Ended Queue, or Deque, which allows insertion and deletion at both ends.

It offers two operations for adding the element at the front of the deque or the end of the deque.

There will be two cases:-

  1. If the index for the current element is even then we will push the element at the end of the deque.
  2. If the index of the current element is odd then we will push the current element at the starting of the deque. Adding at the first will make sure that the array is automatically reversed.

 

If the number of elements are odd then we need to reverse our final deque because, as we know we are not reversing in the case of an even index. Hence, after the last element is inserted the array is not reversed.

 

Refer to the below implementation of the above approach.

class Main{
    
    // To print the elements which are reversed after every insertion.
    static void array(int arr[], int n)
    {
   
     // Doubly ended Queue(Deque)
     Deque<Integer> res = new LinkedList<>();
    
     
     for(int i = 0; i < n; i++)
     {
     
     // Push array elements 
     if ((i & 1) != 0)
     res.addFirst(arr[i]);
     else
     res.add(arr[i]);
     }
    
     // If the size of the list is odd
     if ((n & 1) != 0)
     {
     
     // Reverse the list using java Collections.
     Collections.reverse(Arrays.asList(res));
     }
    
     // Print the final elements
     for(int j:res)
     {
     System.out.print(j + " ");
     }
     System.out.println();
    }
    
    public static void main (String[] args)
    {
     int n = 3;
     int arr[] = { 123};
     
     array(arr, n);
    }
}

 

Output

3 1 2

 

 

Analysis of Complexity:

 

Time Complexity: The time complexity for the above approach is O(N), where ‘N’ is the number of elements in the given array because we are just iterating the array once.

Space Complexity: The space complexity for the above approach is O(N), where ‘N’ is the number of elements in the given array because we are maintaining a Deque which will store all the elements.

 

FAQ’S

 

1). What is the time complexity of the efficient approach?

The time needed by the efficient code to be executed O(n), where n is the number of elements in the array.

 

2). What do you mean by Deque?

Deque is a version of the Queue data structure where elements can be inserted at both the front and back ends of the queue.

 

Key Takeaways

 

In this blog, we have covered the following things.

  • Naive approach with O(N ^ 2) time complexity using an array to store the new inserted and reversed elements.
  • Efficient approach with O(N) time complexity using deque.

 

If you want to learn more about Arrays and practice some questions requiring you to take your basic knowledge a notch higher, you can visit our ARRAY CODING INTERVIEW QUESTIONS.

 

Keep Coding!!!

 

Was this article helpful ?
1 upvote