Reverse the array

The problem, simply

You get an array. Reverse it: the last item becomes the first, the second to last becomes the second, and so on. The best answer changes the array itself instead of making a new one.

A story to remember it

Picture it

Examples

Way 1: the simple way

Make a new array of the same size. Walk the old array from the back and write into the new one from the front.

1. Make out with n slots.
2. For i from 0 to n - 1, set out[i] = arr[n - 1 - i].
3. Return out.

class Solution {
    public int[] reverseArray(int[] arr) {
        int n = arr.length;
        int[] out = new int[n];
        for (int i = 0; i < n; i++) {
            out[i] = arr[n - 1 - i];     // read from the back, write from the front
        }
        return out;
    }
}

How long it takes: one walk, O(n). Extra room: a whole new array, O(n).

Way 2: the clever way

Two fingers, one at each end.

1. lo = 0, hi = n - 1.
2. While lo < hi: swap arr[lo] and arr[hi], then move lo right and hi left.
3. When they meet or cross, stop.

class Solution {
    public void reverseArray(int[] arr) {
        int lo = 0, hi = arr.length - 1;
        while (lo < hi) {
            int t = arr[lo];         // swap the two ends
            arr[lo] = arr[hi];
            arr[hi] = t;
            lo++;                    // step inward
            hi--;
        }
    }
}

How long it takes: n / 2 swaps, which is still O(n). Extra room: two fingers and one temp, O(1).

Watch out for

• Use lo < hi, not lo <= hi. Swapping the middle item with itself is harmless, but <= is a sign the stop rule is not clear in your head.
• For an empty array, hi starts at -1, so the loop never runs. Good.
• In Java, int[] is changed in place, so the caller sees the reversed array. Returning a new array instead is a different contract; say which you do.

What interviewers ask next

• Do it with recursion. reverse(lo, hi): if lo >= hi return, else swap and call reverse(lo + 1, hi - 1). That uses O(n) room on the call stack.
• Reverse only part of the array, from l to r. Start the two fingers at l and r. This is the building block for rotating an array by k: reverse the whole thing, then reverse the two parts.
• Reverse the words in a sentence. Reverse the whole string, then reverse each word.
• Reverse a linked list. There is no index to jump to the end, so you flip the arrows one node at a time instead.

Remember this

Grown-up words: the two fingers are two pointers, changing the array itself is in place, and a stretch of the array from l to r is a subarray.