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++

Code Implementation in Java

Code Implementation in python

Output:

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++:

Code Implementation in java:

Code Implementation in python:

Output:

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:

Output:

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++:

Output:

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++

Code Implementation in Java

Code Implementation in Python

Output:

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++:

Output:

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++:

Output:

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