Reverse an Array [Novel Techniques]

In this article, we have explained three novel approaches to reverse an array in place or in a new array, with swaps and without swap. This is a must read to understand how to reverse an array efficiently.

Table of content:

  1. Problem Statement: Reverse an Array
  2. Approach 1: Two Pointer Technique
  3. Approach 2: Reverse by copying
  4. Approach 3: Reverse by insert operation

By going through this article, you will be able to make sense of this table:

Approach Time Complexity Space Complexity Swaps
Two Pointer Technique O(N) O(1) N/2
Reverse by copying O(N) O(N) 0
Reverse by insert O(N^2) O(1) 0

Let us get started exploring the techniques to reverse an array.

Problem Statement: Reverse an Array

We are given an array of N elements. We need to reverse the array of N elements.

If array A is [a0, a1, a2, ..., aN-1]
then output array will be [aN-1, aN-2, ..., a1, a0]

For example:

array = [2,5,3,7,4]
Reversed array = [4,7,3,5,2]

array = [-1, 0, -99, 40]
Reversed array = [40, -99, 0, -1]

We will work on two approaches:

  • Approach 1: Two Pointer Technique
  • Approach 2: Reverse by copying
  • Approach 3: Reverse by insert operation

Approach 1: Two Pointer Technique

To learn more about this technique, you go through this article: Two Pointer Technique in Array.

A commonly used method to solve this problem uses the 2 pointer approach. One pointer points to the first element while the second on points to the last element.

The elements pointed to by the pointers are swapped and the one pointing to the first elemnt is incremented whereas the one pointing to the last element is decremented (Condition for manipulation).

This continues until the pointers meet (Condition for stopping).

Steps:

  1. Define two pointers: first pointing to element at index 0 and last pointing to element at index N-1.
  2. If first pointer != last pointer
    3. Swap elements at first and last pointer
    4. Increment first pointer
    5. Decrement last pointer
    6. Go to step 2
  3. Array is reversed in place.

This algorithm involves:

  • N/2 swaps
  • N/2 increment and decrement operations

This brings the Time Complexity to O(N).
Space Complexity is O(1). No auxiliary space is used.

Code

Following is the implementation using Two Pointer Technique in Java:

public static void reverseArray(int arr[], int n)
{
    int  i = 0, j = n-1;
    while(i < j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
}

Following is the implementation using Two Pointer Technique in C++:

void reverseArray(int arr[], int n)
{
    int  i = 0, j = n-1;
    while(i < j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
        i++;
        j--;
    }
}

Approach 2: Reverse by copying

In this technique, the idea is to traverse the array in reverse order and copy elements to a second array from the first index. The first array is not modified while the second array (output) is reversed.

Steps:

  1. Define index I = N-1 (last element) and index D = 0 (first element)
  2. Read element at index I and copy that element to second array B at index D
  3. Decrement index I and increment index D
  4. Go to step 2 if I < D

The difference in this approach compared to the previous approach is that in this approach we are not doing any swaps. Swap is an expensive operation in many computing systems and it may be avoided. If this is the case, then approach 2 (current approach) or approach 3 shall be used.

Implementation in Java:

public static void reverseArray(int original[], int reverse[], int n)
{
    int  i = 0, j = n-1;
    while(i < j)
    {
        int element = original[j];
        reverse[i] = element;
        i ++;
        j --;
    }
}

Time Complexity: O(N) as:

  • There are N/2 copy operations
  • N/2 increment and decrement operations

Space Complexity: O(N) as a new array is defined to store the output.

Note: In approach 1, the input array is reversed itself.

Approach 3: Reverse by insert operation

In this approach, the idea is to delete the last element and insert it to the front of the array and do this operation N times. With this, the original array is reversed with a time complexity of O(N^2) but with no swap.

Steps:

  1. Define index last = N-1, first = 0 and count = 0.
  2. Delete element E at index last.
  3. Insert element E at index first.
  4. Increment count and go to step 2 if count < last/2.

Implementation in Java:

// No swap
// O(N^2) time
// O(1) time
public static void reverseArray(int array[], int n)
{
    int  first = 0, last = n-1, count = 0;
    while(count < last-1)
    {
        int element = array[last];
        // takes O(1) time
        delete_last(array);
        // takes O(N) time
        insert_front(array, element);
        count ++;
    }
    // array is reversed
}

public static void delete_last(int array[])
{
    int N = length(array);
    array[N-1] = 0; // same as deletion
}

public static void insert_front(int array[], int element)
{
    int N = length(array);
    int i = N-1;
    // move all elements from index 1 to 
    // right by one position
    while (i > 0)
    {
        array[i] = array[i-1];
        -- i;
    }
    array[0] = element;
}

Time Complexity: O(N^2)

This takes O(N^2) time as the operation to insert an element at front of array takes linear time O(N) as we have to move all elements by one index towards the right.

Insert and delete operations will be done N-1 times for reversing N elements.

This can be used in a system where swap operations should be avoided and in-place reversal of array is needed.

Space Complexity: O(1)

No extra space is needed as original array is reversed.

In summary:

Approach Time Complexity Space Complexity Swaps
Two Pointer Technique O(N) O(1) N/2
Reverse by copying O(N) O(N) 0
Reverse by insert O(N^2) O(1) 0

Depending on your system, you need to choose the correct reversal algorithm.

With this article at OpenGenus, you must have the complete idea of reversing an array using different techniques.