Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Reverse an Array In Place

Try it yourself
EasyProblem

Description

Reverse the array arr in place, so its first element becomes its last, its second becomes its second-to-last, and so on, and return it. Don't use a second array.

Examples

Example 1

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

Output: [5, 4, 3, 2, 1]

Explanation: The ends swap first, 1 and 5, then 2 and 4; 3 in the middle stays.

Example 2

Input: arr = [1, 2]

Output: [2, 1]

Explanation: Two elements: one swap.

Example 3

Input: arr = [7]

Output: [7]

Explanation: One element is its own reverse.

Example 4

Input: arr = [3, 1, 4, 1]

Output: [1, 4, 1, 3]

Explanation: An even length: 3 swaps with the last 1, then 1 with 4.

Constraints

  • 1 ≤ arr.length ≤ 10^5
  • -10^9 ≤ arr[i] ≤ 10^9

Editorial

Approach - Swap the Ends, Then Move In

Intuition

In the reversed array the first element is the last, the second is the second-to-last, and so on: element i and its mirror, n - 1 - i, trade places. So swap the two ends, step both indexes inward, and swap again, until they meet in the middle. Each swap puts two elements in their final places, so n / 2 swaps reverse the whole array.

Building a reversed copy is easy, but it uses a second array, and the problem asks for the array itself to change. Stop at the middle, too: carrying on would swap every pair back.

Step-by-Step Explanation

Let's trace Example 1, arr = [1, 2, 3, 4, 5]:

  1. i = 0, j = 4: swap them, giving [5, 2, 3, 4, 1].
  2. i = 1, j = 3: swap them, giving [5, 4, 3, 2, 1].
  3. i = 2, j = 2: they've met, so stop; arr[2] is the middle, already in place. Return [5, 4, 3, 2, 1].

Swap the Ends — The two indexes swap their elements and step inward until they meet.

Algorithm

  1. Set i = 0 and j = n - 1.
  2. While i < j: swap arr[i] and arr[j], then add 1 to i and take 1 from j.
  3. Return arr.

Code

class Solution {
public:
    vector<int> reverseArray(vector<int>& arr) {
        int i = 0, j = (int) arr.size() - 1;
        while (i < j) {                     // the two ends swap, then move in
            swap(arr[i], arr[j]);
            i++;
            j--;
        }
        return arr;
    }
};

from typing import List

class Solution:
    def reverseArray(self, arr: List[int]) -> List[int]:
        i, j = 0, len(arr) - 1
        while i < j:                        # the two ends swap, then move in
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
            j -= 1
        return arr

class Solution {
    public int[] reverseArray(int[] arr) {
        int i = 0, j = arr.length - 1;
        while (i < j) {                     // the two ends swap, then move in
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
            i++;
            j--;
        }
        return arr;
    }
}

var reverseArray = function(arr) {
    let i = 0, j = arr.length - 1;
    while (i < j) {                         // the two ends swap, then move in
        [arr[i], arr[j]] = [arr[j], arr[i]];
        i++;
        j--;
    }
    return arr;
};

Complexity Analysis

Time Complexity: O(n)

n / 2 swaps.

Space Complexity: O(1)

Two indexes and one value in the middle of a swap.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Swapping all the way across. for i in range(n):

On arr = [1, 2, 3, 4, 5] it returns [1, 2, 3, 4, 5]; the answer is [5, 4, 3, 2, 1]. Every element swaps with its mirror once in the first half; going on to the end swaps each pair a second time, which puts everything back. Stop when the two indexes meet in the middle.

Stopping one pair early. range(n // 2 - 1)

On arr = [1, 2, 3, 4] it returns [4, 2, 3, 1]; the answer is [4, 3, 2, 1]. An array of n elements has n // 2 pairs to swap. range(n // 2 - 1) leaves the innermost pair where it was, so [1, 2, 3, 4] comes out [4, 2, 3, 1].

Reversing a copy. reversed_copy = arr[::-1]

On arr = [1, 2, 3, 4, 5] it returns [1, 2, 3, 4, 5]; the answer is [5, 4, 3, 2, 1]. arr[::-1] makes a new, reversed list and leaves arr as it was. Returning arr then gives back the original order: the reversing has to happen in the array itself.

Where This Pattern Is Taught

This problem practises two indexes moving toward each other from the ends of an array. It's taught in Introduction to Two Pointers.