Reverse an Array

Problem Statement

Given an array arr[] of length N, print the reverse of it.

Example

Consider the following example:

arr[] = {1,2,3,4,5}

After reversing this array,we have the new array as

arr[] = {5,4,3,2,1}

Example Explanation

The initial array [1,2,3,4,5] when reversed gives [5,4,3,2,1].

Constraints

$1 <= N <= 10^5$

There N is the length of the array.

Approach 1- Recursive Approach

In this approach, we recursively divide the array into smaller subarrays while reversing the remaining part.

Let’s define a recursive function reverse(start, end, arr) which reverses the array arr from index start to index end.
Initially start is 0 and end is N-1.
In each recursive step we swap the arr[end] and arr[start] and call the function for the subarray start+1 and end-1.

The above process is simulated as follows:

Algorithm

1) Call the function reverse(start, end , arr) where start=0 and end = N-1.
2) Swap the numbers arr[start] and arr[end].
3) Recursively call the same function for the subarray start+1 and end-1.

 reverse(start,end,arr):
    swap(arr[start],start[end])
    reverse(start+1,end-1,arr)

Let’t see the implementation part:

Code Implementation in C++

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

//Reverse array function
void reverse(int start, int end, int arr[]){
    // Base case
     if(start >= end)
         return;


    //Swap the arr[start] and arr[end]
    swap(arr[start],arr[end]);

     //Recursive step.
    reverse(start+1,end-1,arr);
}

//Auxuliary function to print the array
void printArray(int n, int arr[]){
     for(int i=0;i<n;i++)
         cout << arr[i] << " ";
}

//Driver program
int main(){

    //Input array
    int arr[] = {1,2,3,4,5};

    //Size of the input array
    int n = sizeof arr/sizeof arr[0];


    //call the function for the reverse
    reverse(0,n-1,arr);

    //Print the array
    printArray(n,arr);

}

Code Implementation in Java

import java.io.*;

class Main{

    //function to reverse the array
    static void reverse(int arr[], int start, int end){
        //Base case
         if(start >= end)
             return;

        //Swap the numbers 
        int temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;

        //Reverse the remaining array
        reverse(arr,start+1,end-1);
    }

   //Function to print the given array
   static void printArray(int arr[], int n){
        for(int i=0;i<n;i++)
            System.out.print(arr[i] + " ");
   }

   //Driver program!
   public static void main (String[] args) {
        int arr[] = {1, 2, 3, 4, 5};
        reverse(arr, 0, 4);
        printArray(arr, 5);
    }
}

Code Implementation in python

# Function to reverse arr[] from start to end
def reverse(arr, start, end):
    if start >= end:
        return
    arr[start], arr[end] = arr[end], arr[start]
    reverse(arr, start+1, end-1)


# Driver function to test above function
arr = [1, 2, 3, 4, 5]
reverse(arr, 0, 4)
print(arr)

Output:

5 4 3 2 1

Time Complexity

Since we are calling the reverse function at most n/2 times, where n, is the length of the array, the time complexity is O(n).

Space Complexity

The implementation does not use any auxiliary space, therefore the space complexity is O(1).

Approach 2 – Iterative Approach

In this approach, we iterate the array up to n/2 and for each index i we swap it with $(n-i-1)^{th}$ element of the array.
The approach is a type of two pointer approach where the first pointer is i and the second is (n-i-1).

The process is simulated below:

Algorithm

1) Initialize two variable start = 0 and end = n-1.
2) In a loop, iterate over the array and swap the elements at start and end and change the pointers as
start = start + 1 , end = end-1

Code Implementation in C++:

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

// Function to reverse the array
void reverse(int n, int arr[]){
     //start and end pointers
     for(int i=0;i<n/2;i++)
         swap(arr[i],arr[n-i-1]);

}

//Function to print the array
void printArray(int n, int arr[]){
     for(int i=0;i<n;i++)
         cout << arr[i] << " ";
}

//Driver function
int main(){

    //Input array
    int arr[] = {1,2,3,4,5};

    //size of the array
    int n = sizeof arr / sizeof arr[0];

    //reverse the array
    reverse(n,arr);

    //Print the array
    printArray(n,arr);
}

Code Implementation in Java:

import java.io.*;

class Main{

    //function to reverse the array
    static void reverse(int n, int arr[]){
         for(int i=0;i<n/2;i++){
             int temp = arr[i];
             arr[i] = arr[n-i-1];
             arr[n-i-1] = temp;
         }
    }

    //Function to print the array
    static void printArray(int n, int arr[]){
        for(int i=0;i<n;i++)
            System.out.print(arr[i] + " ");
    }

    //main driver function
    public static void main(String args[]){

        //Input array
        int arr[] = {1,2,3,4,5};
        reverse(5,arr);
        printArray(5,arr);
    }
}

Code Implementation in python:

# function to reverse the array
def reverse(arr, n):
    start = 0
    end = n-1
    while start < end:
        arr[start], arr[end] = arr[end], arr[start]
        start = start + 1
        end = end - 1


# input array
arr = [1,2,3,4,5]
reverse(arr,5)
print(arr)

Output:

5 4 3 2 1

Time Complexity

Since we are iterating over the array once, therefore the time complexity is O(n).

Space Complexity

Since we are not using any auxiliary space for the implementation the space complexity is O(1).

Approach 3 – Using Python List Slicing

Array or list in Python can be reversed using the Python List slicing.

Syntax:

list_name[start: end] where list_name represents the name of the list to be reversed while start and end are the starting and ending indices.

To read more about python slicing read python slicing.

Algorithm

1) Printing the list_name[::-1] will simply reverse the input list and print the reversed list.

Code Implementation in Python:

# function to reverse the array
def reverse(arr):
    print(arr[::-1])

arr = [1,2,3,4,5]
print("Reversed list is:")
reverse(arr)

Output:

5 4 3 2 1

Time Complexity

Since we are using the python in-built slice method, where the complexity of the slice method is O(n) for a list to be sliced of length n, therefore the time complexity is O(n).

Space Complexity

Since the implementation does not use any auxiliary space, space complexity is O(1).

Approach 4 – Reverse an Array in C++ Using the reverse() Function

In c++, there is an in-built reverse function that is used to reverse arrays.

Algorithm

Use reverse function and pass the address of first element and ending address of the array.

Syntax:

reverse(arr,arr+n) will reverse the array arr of length n.

Code Implementation in C++:

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

//reverse the array using in-built function
void reverse(int arr[], int n){
    reverse(arr,arr+n);
}

//function to print the array
void printArray(int arr[], int n){
     for(int i=0;i<n;i++)
         cout << arr[i] << " ";
}

//Driver program
int main(){

    //Input array
     int arr[] = {1,2,3,4,5};

    //Size of the array
    int n = sizeof arr/sizeof arr[0];

    // reverse the array
    reverse(arr,n);

    //Print the given array
    printArray(arr,n);
}

Output:

5 4 3 2 1

Time Complexity

The time complexity of the reverse function is O(n), therefore the time complexity of the above implementation is O(n).

Space Complexity

Since the implementation is not using any auxiliary space, the space complexity is O(1).

Approach 5- Using Concept of Swapping

In this approach, we use the concept of swapping i.e. interchanging the values to reverse the array using a third variable.
We iterate over the array from i=0 to i=n/2 and swap the values at arr[i] and arr[n-i-1] using a temporary variable temp.

Algorithm

1) Initialize two pointers start = 0 and end = n-1;
2) Swap the values arr[start] and arr[end].
3) Increment start by 1 and decrement end by 1.
4) If start reached the value upto n/2 or start >= end then terminate, else repeat the step 2 and 3.

Code Implementation in C++

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

//Function to reverse the array
void reverse(int n, int arr[]){
     int start = 0 , end = n-1;
     while(start < end){
          int temp = arr[start];
          arr[start] = arr[end];
          arr[end] = temp;
          start += 1;
          end -= 1;
     }
}

//Print array
void printArray(int n, int arr[]){
     for(int i=0;i<n;i++)
         cout << arr[i] << " ";
}

//Driver program
int main(){

    //Input array
    int arr[] = {1,2,3,4,5};


    //Size of the array
    int n = sizeof arr / sizeof arr[0];

    //call the reverse function
    reverse(n,arr);

    //Print the array
    printArray(n,arr);
}

Code Implementation in Java

import java.io.*;

class Main{

    //Function to reverse the array
     static void reverse(int arr[], int n){
          int start = 0, end = n-1;
          while(start < end){
               int temp = arr[start];
              arr[start] = arr[end];
              arr[end]=temp;
              start += 1;
              end -= 1;
          }
     }

    //Print array function
    static void printArray(int arr[], int n){
        for(int i=0;i<n;i++)
            System.out.print(arr[i] +  " ");
    }

    //Driver Function
    public static void main(String args[]){
        //INput arrat
        int arr[] = {1,2,3,4,5};

        //Size of the array
        int n = arr.length;

        //Call the reverse array function
        reverse(arr,n);

        //Print the reversed array
        printArray(arr,n);
    }

}

Code Implementation in Python

# function to reverse the array
def reverse(n, arr):
    start = 0
    end = n-1
    while start < end:
        arr[start],arr[end] = arr[end],arr[start]
        start += 1
        end -= 1


# input array
arr = [1,2,3,4,5]
reverse(len(arr),arr)
print(arr)

Output:

[5 ,4, 3, 2, 1]

Time Complexity

Since, we are iterating over the array up to n/2 i.e. the operations are proportional to n hence the time complexity is O(n).

Space Complexity

Since the implementation does not use any extra space, therefore the space complexity is O(1).

Approach 6 – User-defined Function

In this approach, the logic is same as we did in iterative approach,but we do not use any inbuild library function, rather we reverse the array using user-defined functions for reversing as well as swapping.

Algorithm

1) Define a function reverseArray which is used to reverse the array.
2) In the function initialize two pointers start=0 and end=n-1.
3) Swap the elements at start and end and move the pointers start as start+1 and end as end-1.

Code Implementation in C++:

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

//Function to reverse the array
void reverseArray(int arr[], int n);

void printArray(int arr[], int n){
    for(int i=0; i<n; i++) cout << arr[i] << " ";
    cout << endl;
}

//Driver program
int main(){
    //Input array
    int arr[] = {1,2,3,4,5};

    //Length of the array
    int n = sizeof arr/sizeof arr[0];

    //Function to reverse the array
    reverseArray(arr,n);

    //Function to print the array
    printArray(arr,n);
}

//Function to reverse the array
void reverseArray(int ar[], int n){
    int i, j, temp;  
    j = n - 1;  
    for ( i = 0; i < j; i++, j--)  
    {  
        temp = ar[i];  
        ar[i] = ar[j];  
        ar[j] = temp;  
    }  
}

Output:

5 4 3 2 1

Time Complexity

Since we are iterating over the array once, the time complexity becomes O(n).

Space Complexity

Since the implementation does not use any auxiliary space, the space complexity becomes O(1).

Approach 7 – Reverse an Array in C++ Using the Pointers

In this approach, we use the concept of the c++ pointer to reverse the array where we basically use two pointers pointer1 which points to the beginning address of the array, and pointer2 which points to the ending address of the array.

The elements at these two locations are swapped and the pointer1 pointer is moved to the address of the next array element and the pointer2 pointer is moved to the address of the previous array element.

Algorithm

1) Initialize two pointers pointer1 and pointer2 with the beginning and ending address of the array.
2) Swap the values present at the start and end addresses, increment the start pointer by one and decrement the end pointer by 1.
3) Repeat the second step until the start address crosses the end address or they become the same.

We shall use three functions

reverse: Used to reverse the array
swap: Used to swap the values at addresses pointed by pointer1 and pointer2.
print: Used to print the array elements

Code Implementation in C++:

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

//swap function
void swap(int *a, int *b){
      int temp = *a;
      *a = *b;
      *b = temp;
}

//reverse array function
void reverse(int arr[], int n){

    //Pointer pointing at the beginning
    int *pointer1 = arr;

    //Pointer pointing at the end of the array
    int *pointer2 = arr + n -1;

    while(pointer1 < pointer2){
        swap(pointer1,pointer2);
        pointer1++;
        pointer2--;
    }   
}

///Print the array
void print(int *arr, int n){

    //size at the end of the array
    int *size = arr + n;

    //Position pointing to the beginning of the
    // array
    int *pos = arr;
    for(pos = arr;pos < size; pos++)
        cout << *pos << " ";
}

//Driver program
int main(){

    //Input array
    int arr[] = {1,2,3,4,5};


    //Length of the array
    int n = sizeof arr / sizeof arr[0];

    //reverse the array
    reverse(arr,n);

    //print the array
    print(arr,n);
}

Output:

5 4 3 2 1

Time Complexity

Since, we are iterating over the array exactly once while swapping elements,hence the time complexity is O(n).

Space Complexity

Since we are not using any extra space, therefore the space complexity is O(1).

Conclusion

• We conclude that there are many methods to reverse an array.
• Technically, they are divided into two approaches, either it can be recursive approach or an iterative approach.
• Some languages provide in-built functions to reverse an array like slicing in python and reverse in c++.
• Arrays can be reversed in-place i.e. there is no need to use any extra space.

Unlimited access and expert analysis combine with storytelling and non-stop action to give the channel the full taste of the Blue and White. The cold light of day dvdrip ac3 xvid bestdivx crankhv. The use of botulinum toxin for headache syndromes followed from observations that patients treated for forehead frown lines showed improvement in headache. Mount Olive is 60 miles southeast of the capital city of Raleigh, North Carolina and 75 miles northwest of the coastal town of Wilmington, North Carolina. Then we create the system startup links for MySQL and Apache so that both start automatically whenever the system boots and start both services. Just as electric cars are helping to reduce pollution from passenger vehicles, electric trucks and buses could eliminate tailpipe pollution entirely, and increase the development of clean, renewable electricity and hydrogen. Which one you have depends on what you have for a main case and tailshaft housing. A pressure canner is not the same as a pressure cooker, although some pressure canners can also be used for pressure cooking. A lot was directly addressed in on short time period and also resolved — both on a personal level as well as professional! List of Pennsylvania state historical markers in Mercer County While Khadijah was the first Muslim of all, 7 : she was closely followed by her neighbour Lubaba bint al-Harith, 2 : her four daughters, 9 : 21, 25—26 and the first male converts, Ali, Zayd and Abu Bakr. Sure a rep comes out to the job and hands you the installation manual and goes over how to put the fittings together. The automated validation suite runs continuously on hundreds of systems simultaneously, rapidly providing wide-ranging test coverage. The party was officially launched as the Haryana Lok Dal Rashtriya in, and by the following year it had become known as the Indian National Lok Dal.