Maximize sum of consecutive differences in a circular array

The problem, simply

You get some numbers. Put them in a circle in any order you like. Walk around the circle and add up the gap between each pair of neighbours. The gap is the bigger number minus the smaller one, written |a - b|. Because it is a circle, the last number is also a neighbour of the first.

Give back the biggest total you can get.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every seating plan. For each order, walk around the circle, add the gaps, and keep the best total. Turning the table does not change the total, so you can keep the first seat fixed and shuffle the rest.

1. Fix a[0] in seat 0.
2. Try every order of the other numbers in the other seats.
3. For each order, add |seat[i] - seat[i + 1]| for every seat, wrapping the last back to the first.

class Solution {
    private long best;

    public long maxCircularDiffSum(int[] a) {
        best = 0;
        shuffle(a, 1);           // keep a[0] in place, try every order of the rest
        return best;
    }

    private void shuffle(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]);  // wrap around
            }
            best = Math.max(best, total);
            return;
        }
        for (int i = start; i < a.length; i++) {
            swap(a, start, i);
            shuffle(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: there are (n - 1)! orders and each costs n to add up, so O(n! * n). Ten numbers is already 3 million orders. Extra room: the recursion is n deep, O(n).

Way 2: the clever way

Every gap is a big number minus a small number. So each number is either added or taken away once for each of its two neighbours.

• If both neighbours are smaller, the number is added twice.
• If both neighbours are bigger, the number is taken away twice.
• If one is bigger and one is smaller, it is added once and taken away once, so it counts 0.

The best you can hope for is that the biggest half is added twice and the smallest half is taken away twice. The small, big, small, big seating does exactly that. With an odd count, one middle number is left, and it counts 0.

1. Sort the numbers.
2. Pair the smallest with the biggest, the second smallest with the second biggest, and so on.
3. Each pair adds 2 * (big - small). The middle number, if any, adds nothing.

import java.util.Arrays;

class Solution {
    public long maxCircularDiffSum(int[] a) {
        int n = a.length;
        Arrays.sort(a);
        long total = 0;
        for (int i = 0; i < n / 2; i++) {
            total += 2L * (a[n - 1 - i] - a[i]);  // big counts +2, small counts -2
        }
        return total;                              // an odd middle number counts 0
    }
}

How long it takes: the sort is O(n log n) and the pairing walk is O(n). Extra room: O(1) beyond the sort.

Watch out for

• Use long. Two times a gap of two billion does not fit in int.
• Two numbers make a circle of two seats, so their gap is counted twice: [3, 10] gives 14.
• Negative numbers work the same way. Sorting puts them in the small half.
• Repeated numbers need no special care. The pairing formula works on them as they are.

What interviewers ask next

• Return the seating, not just the total. Use two pointers on the sorted row: take from the left, then from the right, until they meet.
• What if it is a straight line, not a circle? The two end seats have one neighbour each, so they count once instead of twice. Try both shapes (big numbers at the peaks, or small numbers at the peaks), give the two end seats to the numbers closest to the middle, and keep the better total. Still O(n log n).
• Why is the greedy seating optimal? Each number appears in exactly two gaps, so at most n / 2 numbers can be added twice. The best case adds the biggest ones, and the zigzag reaches that bound.
• Minimise the total instead? Seat them in sorted order around the circle. The total becomes 2 * (max - min).

Remember this

Grown-up words: the round table is a circular array, a gap is the absolute difference, the small and big seating is a zigzag arrangement, and the count trick is a contribution argument.