Arrays: Practice Problems II - Reversing an Array In Place

Every index has a mirror at n - 1 - i

To reverse [4, 2, 7, 1, 5], each value must move to the index equally far from the other end. With n = 5, index 0 has mirror index 5 - 1 - 0 = 4, so 4 and 5 exchange positions. Index 1 has mirror index 5 - 1 - 1 = 3, so 2 and 1 exchange positions. Index 2 mirrors itself because 5 - 1 - 2 = 2, so 7 stays in the middle.

int[] a = {4, 2, 7, 1, 5};
int n = a.length;

// Required exchanges:
// index 0 with index 4
// index 1 with index 3
// index 2 stays where it is

Direct assignment destroys a value that the next step still needs

The assignment a[i] = a[n - 1 - i] copies the mirror value into the left slot, but it does not preserve the value that was already there. For i = 0, the assignment copies 5 into index 0, changing the array from [4, 2, 7, 1, 5] to [5, 2, 7, 1, 5]. The original 4 is gone from the array. No later read of index 0 can recover it.

Continuing the same assignment for i = 1 copies 1 into index 1, changing the array to [5, 1, 7, 1, 5]. The original 2 is now gone as well. Later assignments cannot repair either loss, because they read values from the already changed array.

for (int i = 0; i < n; i++) {
    a[i] = a[n - 1 - i];
}

A temporary variable preserves both values during a swap

A swap must save the left value before either array slot is overwritten. For indices 0 and 4, temp first stores 4. Then a[0] receives 5, while temp still holds 4. Finally, a[4] receives temp. The array becomes [5, 2, 7, 1, 4], so both values have changed positions instead of one being lost.

int i = 0;
int mirror = n - 1 - i;
int temp = a[i];
a[i] = a[mirror];
a[mirror] = temp;

The same order swaps indices 1 and 3. Before the swap, the array is [5, 2, 7, 1, 4]. Saving a[1] stores 2, copying a[3] into a[1] produces [5, 1, 7, 1, 4], and copying the saved value into a[3] produces [5, 1, 7, 2, 4].

Stopping at n / 2 prevents every swap from being undone

The array has only two distinct mirror pairs: indices 0 and 4, then indices 1 and 3. Index 2 is its own mirror and needs no change. Therefore the loop should run for i = 0 and i = 1, which is exactly i < n / 2 because integer division makes 5 / 2 equal to 2.

for (int i = 0; i < n / 2; i++) {
    int mirror = n - 1 - i;
    int temp = a[i];
    a[i] = a[mirror];
    a[mirror] = temp;
}

After i = 0, the array is [5, 2, 7, 1, 4]. After i = 1, it is [5, 1, 7, 2, 4]. If the loop continued through the second half, i = 3 would swap indices 3 and 1 again, and i = 4 would swap indices 4 and 0 again. Those repeated swaps would restore the original array instead of reversing it.