Reverse An Array

Difficulty: Easy

Unders t anding The Problem

Problem Description

Given an array, the task is to reverse the array.

Examples →

Input  : arr[] = {34, 12, 23}
Output : arr[] = {23, 12, 34}

Input :  arr[] = {1, 2, 3, 4, 5, 6}
Output : arr[] = {6, 5, 4, 3, 2, 1}

Solution

We will be discussing a simple approach to reverse the array in-place. In place means, we will not be using some auxiliary space.

To reverse an array, we will use the concept of swapping. Swapping is a term used for interchanging the values at two different locations with each other.

Look at the below example to get a clear understanding of the array that should be reversed.

So, we can set two pointers at the start and end of the array and start iterating over it till the (length of array)/2 . For every idx , we will swap array[idx] with array[length - idx] . Thus, the array will be reversed in-place.

Solution Steps

Place the two pointers (let start and end ) at the start and end of the array.
Swap arr[start] and arr[end]
Increment start and decrement end with 1
If start reached to the value length/2 or start ≥ end , then terminate otherwise repeat from step 2.

Pseudo Code

void rvereseArray(int[] arr) {
    start = 0 
    end = arr.length - 1 
    while (start < end) {
        // swap arr[start] and arr[end]
        int temp = arr[start]
        arr[start] = arr[end]
        arr[end] = temp
        start = start + 1
        end = end - 1
    }
}

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Critical Ideas to Think

The loop will run only till length/2 then why the asymptotic time complexity is O(n) instead of O(n/2) ?
How did we perform swapping?
Why did we iterate until start < end or start < (length of array)/2 ?
What will happen if the while condition would be start < length of array , instead of start < end in pseudocode? Can you dry run the code over some examples?