Reversing an Array

Reverse the Array

Example 1: The problem is quite straight forward, we have to reverse the array given to us.

Input: N = 8
value[] = {1,2,3,4,5,2,1,7,8}
Output[] = {8,7,1,2,5,4,3,2,1}  
Explanation:  The elements of the array are reversed.

Solution:-

There could be multiple ways to solve this problem, but I will be discussing two approaches. First of all I will be discussing the very basic approach (Brute Force) and then I will be discussing the most optimal approach in terms of space and time to solve the same problem.

Brute Force Solution:-

In this approach, we will be using an extra array. We will be traversing the given array from end to start and keep storing the values in the new array. Now, the new array will be having the elements in reverse order of the original array.

This solution will be using O(N) extra space to store the elements in the new array, and we will have to traverse the entire array resulting in O(N) time complexity.

Here is the code to reverse the array using brute force method.

#include<bits/stdc++.h>

using namespace std;

vector<int> reverseArray(vector<int> V, int size){

    vector<int> ans(size);

    int i = 0;

    // pointer at 0 so that we can store the elements in ans array

    for(int j=size-1; j>=0; --j){

        ans[i] = V[j];

        ++i;

    }

    return ans;

}

  

int main(){

    int size; 

    cin>>size; //taking size of the array

    vector<int> V(size); //intializing a vector of same size

    //taking array as input from user

    for(int i=0; i<size; ++i){

        cin>>V[i];

    }

    vector<int> ans = reverseArray(V,size);

    for(auto element: ans){

        cout<<element<<" ";

    }

    return 0;

}

Optimal Solution (Two Pointer Method):-

In this approach, we will be using two pointers, the first pointer will point to the first element in the array and the second pointer will point to the last element. We will then be swapping the elements at these two positions and increment the first pointer by one and decrement the second pointer by one.

We will have to do the same until first pointer crosses the second pointer, as soon the position of first pointer becomes greater than or equal to the second pointer, we break out of the loop.

At the end, we will notice that the elements in our array are reversed.

This solution doesn’t use any extra space, in fact the array is reversed in place resulting in O(1) space complexity. Also we don’t have to run the loop N times, we will have to run it N/2 times, but still the time complexity will be O(N/2), though it will be considered linear.

Here is the code to reverse the array using two pointer approach.

#include<bits/stdc++.h>
using namespace std;

void reverseArray(vector<int>& V, int size){
    int p = 0; // first pointer to first element
    int q = size-1; //second pointer to last element
    
    while(p<q){
        int temp = V[p];
        V[p] = V[q];
        V[q] = temp;
        
        ++p; --q;
    }
}

int main(){
    int size; 
    cin>>size; //taking size of the array
    
    vector<int> V(size); //intializing a vector of same size
    
    //taking array as input from user
    for(int i=0; i<size; ++i){
        cin>>V[i];
    }
    
    // calling reverse function to reverse the array in place
    reverseArray(V,size);
    
    for(auto element: V){
        cout<<element<<" ";
    }
    
    return 0;
}

You can also follow me on GitHub, and fork my DSA-Practice Repository to get solutions to more solutions.

Thank you,
Gaurav Goyal

Github
LinkedIn