Maximum sum of absolute difference of an array

The problem, simply

You get some numbers. Arrange them in any order. Then add the gaps between neighbours, |a[0] - a[1]| + |a[1] - a[2]| + ..., and also the gap from the last number back to the first, as if the row were a ring.

Give back the biggest total, and be ready to show the arrangement that makes it.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every order. For each one, add the gaps around the ring and keep the best. Spinning the ring gives the same total, so the first number can stay put.

class Solution {
    private long best;

    public long maxRingGapSum(int[] a) {
        best = 0;
        tryOrders(a, 1);
        return best;
    }

    private void tryOrders(int[] a, int start) {
        if (start >= a.length) {
            long total = 0;
            for (int i = 0; i < a.length; i++) {
                total += Math.abs(a[i] - a[(i + 1) % a.length]);   // last wraps to first
            }
            best = Math.max(best, total);
            return;
        }
        for (int i = start; i < a.length; i++) {
            swap(a, start, i);
            tryOrders(a, start + 1);
            swap(a, start, i);
        }
    }

    private void swap(int[] a, int i, int j) { int t = a[i]; a[i] = a[j]; a[j] = t; }
}

How long it takes: (n - 1)! orders, each added up in n steps, so O(n! * n). Extra room: recursion n deep, O(n).

Way 2: the clever way

A gap is wasted when two big numbers or two small numbers sit together. So make big and small take turns. Sort the numbers, then use two pointers: lo at the small end and hi at the big end. Take from lo, then from hi, then from lo again, until they meet.

1. Sort the numbers.
2. Build the seating: take a[lo++], then a[hi--], in turns, while lo <= hi.
3. Add the gaps around the ring, including last to first.

Why it is the best: every number touches exactly two gaps. In a gap the bigger number counts plus and the smaller counts minus. The zigzag makes each of the biggest half count plus twice and each of the smallest half count minus twice, which is the most any ring can do.

import java.util.Arrays;

class Solution {
    public long maxRingGapSum(int[] a) {
        int n = a.length;
        int[] s = a.clone();
        Arrays.sort(s);
        int[] seat = new int[n];
        int lo = 0, hi = n - 1, k = 0;
        boolean takeSmall = true;
        while (lo <= hi) {
            seat[k++] = takeSmall ? s[lo++] : s[hi--];   // small, big, small, big
            takeSmall = !takeSmall;
        }
        long total = 0;
        for (int i = 0; i < n; i++) {
            total += Math.abs(seat[i] - seat[(i + 1) % n]); // the ring closes at the end
        }
        return total;
    }
}

How long it takes: the sort is O(n log n), building and adding are O(n). Extra room: the seating array, O(n). If you only need the total, pair the ends of the sorted row and add 2 * (big - small) for each pair, which needs O(1) extra room.

Watch out for

• Do not forget the gap from the last number back to the first.
• Use long. Gaps between big numbers can pass the int limit when added up.
• Sorting from big to small and starting with the biggest gives the same total. Any zigzag that alternates the two halves works.
• Two numbers form a ring of two, so their gap counts twice: [3, 10] gives 14.

What interviewers ask next

• A straight line instead of a ring? The two ends have only one neighbour each. Try putting the big numbers at the peaks and the small numbers at the peaks, give the end seats to numbers near the middle, and keep the better total.
• Make the total as small as possible? Seat them in sorted order. The ring then costs 2 * (max - min), and nothing can be smaller, because the ring must climb from the minimum to the maximum and come back.
• Prove the greedy. Each number is in two gaps, so at most n / 2 numbers can count plus twice. The zigzag picks the biggest n / 2 for that, so no order can beat it.
• What if the numbers come in a stream? Keep them sorted in a balanced tree or two heaps for the small and big halves, and update the total as numbers arrive.

Remember this

Grown-up words: the ring is a circular arrangement, a gap is an absolute difference, taking from both ends is the two pointer technique, and the plus and minus count is a contribution argument.