Rearrange a Sorted Array in Max/Min Form

Given an array sorted in ascending order, rearrange it so that it alternates between the largest and smallest remaining values: first the maximum, then the minimum, then the second maximum, then the second minimum, and so on.

Example 1

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

Example 2

Input:  [1, 2, 3, 4, 5]
Output: [5, 1, 4, 2, 3]
Explanation: with an odd length, the middle value ends up last.

Brute force: two pointers into a new array

lo points at the smallest unused value (the left end) and hi points one position past the largest unused value (the right end). Alternate between taking from hi and from lo until they meet.

Walkthrough with [1, 2, 3, 4, 5, 6]:

import java.util.Arrays;

public class Main {
    static int[] maxMin(int[] nums) {
        int[] result = new int[nums.length];
        int lo = 0, hi = nums.length;
        boolean takeMax = true;
        int k = 0;

        while (lo < hi) {
            if (takeMax) {
                hi--;
                result[k++] = nums[hi];
            } else {
                result[k++] = nums[lo];
                lo++;
            }
            takeMax = !takeMax;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(maxMin(new int[]{1, 2, 3, 4, 5, 6})));
        System.out.println(Arrays.toString(maxMin(new int[]{1, 2, 3, 4, 5})));
    }
}

[6, 1, 5, 2, 4, 3]
[5, 1, 4, 2, 3]

Time: O(n). Space: O(n) for the new array. Because hi is exclusive, nums[hi] is read only after hi is decremented, so the index is always valid.

This is the solution to give first. The follow-up question is usually: can you do it with O(1) extra space?

Optimal space: store two values in each slot

Writing the result into nums directly would overwrite values we still need. The trick is to make each slot hold both its old value and its new value for a while.

Pick m = max + 1, a number larger than every element. For any two values old and new, both between 0 and max, the number old + new * m encodes both:

• (old + new * m) % m == old
• (old + new * m) / m == new

So at index i, add new * m to the slot. Any slot that has already been updated still gives back its original value through % m. At the end, divide every slot by m to keep only the new values.

Walkthrough with [1, 2, 3, 4, 5, 6], m = 7:

Dividing by 7 gives [6, 1, 5, 2, 4, 3].

import java.util.Arrays;

public class Main {
    static void maxMin(long[] nums) {
        int n = nums.length;
        if (n == 0) {
            return;
        }
        long m = nums[n - 1] + 1; // larger than every value (the input is sorted)
        int lo = 0, hi = n - 1;

        for (int i = 0; i < n; i++) {
            long source;
            if (i % 2 == 0) {
                source = nums[hi];
                hi--;
            } else {
                source = nums[lo];
                lo++;
            }
            nums[i] += (source % m) * m; // `% m` recovers the original value
        }
        for (int i = 0; i < n; i++) {
            nums[i] /= m;
        }
    }

    public static void main(String[] args) {
        long[] a = {1, 2, 3, 4, 5, 6};
        long[] b = {0, 10, 20, 30, 40};
        maxMin(a);
        maxMin(b);
        System.out.println(Arrays.toString(a) + " " + Arrays.toString(b));
    }
}

[6, 1, 5, 2, 4, 3] [40, 0, 30, 10, 20]

Time: O(n). Space: O(1).

This technique has two limits, and you should state them when you present it:

• Values must be non-negative. % and / do not separate the two values correctly for negative numbers. For negative input, shift every value by -min first and shift back at the end.
• Overflow. old + new * m can be close to max², so the code uses long. With int, the encoded value wraps silently once max passes about 46,000.

Edge cases

• Empty array or one element: returned unchanged.
• Duplicates: both approaches handle them.
• Input not sorted: sort it first, which adds O(n log n).