Reverse an array

Intuition:

To reverse an array, the objective is to reorder the elements such that the last element becomes the first and the second last becomes the second, and so forth. The straightforward approach involves creating a new array of the same size and populating it by iterating through the input array from end to start, thereby storing elements in reverse order.

Approach:

Declare a new array having the same size as the input array.
Iterate through the input array from the end to the beginning and for each element in the input array, store it in the corresponding position in the new array.
After the loop ends, the new array will contain the reversed elements.
Copy the elements back to the original array to get the reversed array.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
 
class Solution {
public:
    // Function to reverse array using an auxiliary array
    void reverse(int arr[], int n) {
        int* ans = new int[n];
        
        /* Fill new array with elements of 
        original array in reverse order */
        for (int i = n-1; i >= 0; i--) {
            ans[n-i-1] = arr[i];
        }
        
        // Copy the elements back to the original array
        for(int i=0; i < n; i++) {
            arr[i] = ans[i];
        }
        
        // Free the dynamically allocated memory
        delete[] ans; 
        
        // Return
        return;
    }
};
 
// Function to print array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
int main() {
    int n = 5;
    int arr[] = {5, 4, 3, 2, 1};
    
    // Creating instance of Solution class
    Solution solution;
    cout << "Original array: ";
    printArray(arr, n);
    
    // Function call to reverse the array 
    solution.reverse(arr, n); 
    cout << "Reversed array: ";
    printArray(arr, n);
    
    return 0;
}
 
import java.util.Arrays;
 
class Solution {
    // Function to reverse array using an auxiliary array
    public void reverse(int arr[], int n) {
        int[] ans = new int[n];
        
        /* Fill new array with elements of 
        original array in reverse order */
        for (int i = n - 1; i >= 0; i--) {
            ans[n - i - 1] = arr[i];
        }
        
        // Copy the elements back to the original array
        for(int i = 0; i < n; i++) {
            arr[i] = ans[i];
        }
        
        // Return
        return;
    }
}
 
class Main {
    // Function to print array
    public static void printArray(int arr[], int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int n = 5;
        int[] arr = {5, 4, 3, 2, 1};
        
        // Creating instance of Solution class
        Solution solution = new Solution();
        System.out.print("Original array: ");
        printArray(arr, n);
        
        // Function call to reverse the array 
        solution.reverse(arr, n); 
        System.out.print("Reversed array: ");
        printArray(arr, n);
    }
}
class Solution:
    # Function to reverse array using an auxiliary array
    def reverse(self, arr, n):
        ans = [0] * n
        
        # Fill new array with elements of 
        # original array in reverse order
        for i in range(n - 1, -1, -1):
            ans[n - i - 1] = arr[i]
        
        # Copy the elements back to the original array
        for i in range(n):
            arr[i] = ans[i]
        
        # Return
        return
 
# Function to print array
def printArray(arr, n):
    for i in range(n):
        print(arr[i], end=" ")
    print()
 
if __name__ == "__main__":
    n = 5
    arr = [5, 4, 3, 2, 1]
    
    # Creating instance of Solution class
    solution = Solution()
    print("Original array: ", end="")
    printArray(arr, n)
    
    # Function call to reverse the array 
    solution.reverse(arr, n) 
    print("Reversed array: ", end="")
    printArray(arr, n)
class Solution {
    // Function to reverse array using an auxiliary array
    reverse(arr, n) {
        let ans = new Array(n);
        
        /* Fill new array with elements of 
        original array in reverse order */
        for (let i = n - 1; i >= 0; i--) {
            ans[n - i - 1] = arr[i];
        }
        
        // Copy the elements back to the original array
        for (let i = 0; i < n; i++) {
            arr[i] = ans[i];
        }
        
        // Return
        return;
    }
}
 
// Function to print array
function printArray(arr, n) {
    console.log(arr.join(" "));
}
 
const n = 5;
const arr = [5, 4, 3, 2, 1];
 
// Creating instance of Solution class
let solution = new Solution();
console.log("Original array: ");
printArray(arr, n);
 
// Function call to reverse the array 
solution.reverse(arr, n); 
console.log("Reversed array: ");
printArray(arr, n);

Complexity Analysis:

Time Complexity: O(N), A single-pass of the array with N elements is being done to reverse the array.

Space Complexity: O(N), for the extra array of the same size used.

Intuition:

To reverse an array in place without additional space, employ a swapping technique utilizing two pointers: one starting from the beginning of the array and the other from the end. By exchanging the elements at these pointers and progressively moving them toward the center, the array can be reversed efficiently within the same memory allocation. This method is both space-efficient and effective.

Approach:

Initialize a pointer p1 at the first index and another pointer p2 at the last index of the array.
Swap the elements pointed by p1 and p2 and increment p1 by 1 while decrementing p2 by 1 simultaneously.
Repeat the process for the first n/2 elements, where n is the length of the array.

Dry Run

Solution

#include <bits/stdc++.h>
using namespace std;
 
class Solution {
public:
    // Function to reverse array using two pointers
    void reverse(int arr[], int n) {
        int p1 = 0, p2 = n - 1;
        /* Swap elements pointed by p1 and p2 
        until they meet in the middle */
        while (p1 < p2) {
            int tmp = arr[p1];
            arr[p1] = arr[p2];
            arr[p2] = tmp;
            p1++;
            p2--;
        }
        // Return
        return;
    }
};
 
// Function to print array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}
 
int main() {
    int n = 5;
    int arr[] = {5, 4, 3, 2, 1};
    
    // Creating instance of Solution class
    Solution solution;
    cout << "Original array: ";
    printArray(arr, n);
    
    // Function call to reverse the array 
    solution.reverse(arr, n); 
    cout << "Reversed array: ";
    printArray(arr, n);
    
    return 0;
}
import java.util.Arrays;
 
class Solution {
    // Function to reverse array using two pointers
    public void reverse(int[] arr, int n) {
        int p1 = 0, p2 = n - 1;
        /* Swap elements pointed by p1 and 
        p2 until they meet in the middle */
        while (p1 < p2) {
            int tmp = arr[p1];
            arr[p1] = arr[p2];
            arr[p2] = tmp;
            p1++;
            p2--;
        }
        // Return
        return;
    }
}
 
class Main {
    // Function to print array
    public static void printArray(int arr[], int n) {
        for (int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }
    
    public static void main(String[] args) {
        int n = 5;
        int[] arr = {5, 4, 3, 2, 1};
        
        // Creating instance of Solution class
        Solution solution = new Solution();
        System.out.print("Original array: ");
        printArray(arr, n);
        
        // Function call to reverse the array 
        solution.reverse(arr, n); 
        System.out.print("Reversed array: ");
        printArray(arr, n);
    }
}
class Solution:
    # Function to reverse array using two pointers
    def reverse(self, arr, n):
        p1 = 0
        p2 = n - 1
        # Swap elements pointed by p1 and 
        # p2 until they meet in the middle
        while p1 < p2:
            tmp = arr[p1]
            arr[p1] = arr[p2]
            arr[p2] = tmp
            p1 += 1
            p2 -= 1
        # Return
        return
 
# Function to print array
def printArray(arr, n):
    for i in range(n):
        print(arr[i], end=" ")
    print()
 
if __name__ == "__main__":
    n = 5
    arr = [5, 4, 3, 2, 1]
    
    # Creating instance of Solution class
    solution = Solution()
    print("Original array: ", end="")
    printArray(arr, n)
    
    # Function call to reverse the array 
    solution.reverse(arr, n) 
    print("Reversed array: ", end="")
    printArray(arr, n)
class Solution {
    // Function to reverse array using two pointers
    reverse(arr, n) {
        let p1 = 0, p2 = n - 1;
        /* Swap elements pointed by p1 and p2
        until they meet in the middle */
        while (p1 < p2) {
            let tmp = arr[p1];
            arr[p1] = arr[p2];
            arr[p2] = tmp;
            p1++;
            p2--;
        }
        // Return
        return;
    }
}
 
// Function to print array
function printArray(arr, n) {
    console.log(arr.join(" "));
}
 
const n = 5;
const arr = [5, 4, 3, 2, 1];
 
// Creating instance of Solution class
let solution = new Solution();
console.log("Original array: ");
printArray(arr, n);
 
// Function call to reverse the array 
solution.reverse(arr, n); 
console.log("Reversed array: ");
printArray(arr, n);

Complexity Analysis:

Time Complexity: O(N), A single-pass of the array with N elements is being done to reverse the array

Space Complexity: O(1), no extra data structure is being used so no extra space.

Problem List

Examples:

Constraints

Company Tags

Editorial

Intuition:

Approach:

Dry Run

Solution

Complexity Analysis:

Intuition:

Approach:

Dry Run

Solution

Complexity Analysis:

Notes

Code