Problem

Given an array, write an algorithm to reverse the array.

Examples

1
2

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

Solution

Method 1 - Using 2 Pointers

Here is the approach:

  • Use two pointers, start and end.
  • start points to the beginning of the array.
  • end points to the end of the array.
  • Swap the elements at these positions.
  • Increment the start pointer and decrement the end pointer.
  • Continue until the start pointer is greater than or equal to the end pointer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

public class Solution {
    public static void reverseArray(int[] arr) {
        int start = 0;
        int end = arr.length - 1;
        
        while (start < end) {
            // Swap the elements at start and end
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
            
            // Move the pointers towards the center
            start++;
            end--;
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        
        System.out.println("Original array: " + Arrays.toString(arr));
        reverseArray(arr);
        System.out.println("Reversed array: " + Arrays.toString(arr));
        // Expected output: [5, 4, 3, 2, 1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution:
    def reverse_array(self, arr: List[int]) -> None:
        start = 0
        end = len(arr) - 1
        
        while start < end:
            # Swap the elements at start and end
            arr[start], arr[end] = arr[end], arr[start]
            
            # Move the pointers towards the center
            start += 1
            end -= 1

Complexity

  • ⏰ Time complexity: O(n), where n is the number of elements in the array. Each element is swapped once.
  • 🧺 Space complexity: O(1), No additional space is used, aside from a few variables for the indices and temporary storage during swapping.

Method 2 - Using Stack

Here is the approach:

  • Use a stack to reverse the array.
  • Push all elements of the array onto the stack.
  • Pop all elements from the stack and place them back into the array in order.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

public class Solution {
    public static void reverseArray(int[] arr) {
        Stack<Integer> stack = new Stack<>();
        
        // Push all elements of the array onto the stack
        for (int num : arr) {
            stack.push(num);
        }
        
        // Pop all elements from the stack and put them back into the array
        int index = 0;
        while (!stack.isEmpty()) {
            arr[index++] = stack.pop();
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        
        System.out.println("Original array: " + Arrays.toString(arr));
        reverseArray(arr);
        System.out.println("Reversed array: " + Arrays.toString(arr));
        // Expected output: [5, 4, 3, 2, 1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution:
    def reverse_array(self, arr: List[int]) -> None:
        stack = []
        
        # Push all elements of the array onto the stack
        for num in arr:
            stack.append(num)
        
        # Pop all elements from the stack and put them back into the array
        index = 0
        while stack:
            arr[index] = stack.pop()
            index += 1

Complexity

  • ⏰ Time complexity: O(n), If the array contains n items, this algorithm takes 2n steps, so it has run time O(n).
  • 🧺 Space complexity: O(n)