Optimal Strategy for a Game

The problem, simply

Coins lie in a row, usually an even number of them. You and a friend take turns. On your turn you take one coin from the left end or from the right end. You go first, and your friend is just as smart as you: they always play their best.

Give back the largest total you can be sure to collect.

A story to remember it

Picture it

Examples

Way 1: the simple way

Write a helper f(i, j): the most the player to move can get from coins i to j.

1. One coin left: take it. No coins left: 0.
2. If you take the left coin a[i], your friend then moves on i+1..j. They will leave you either f(i+2, j) (they took the left) or f(i+1, j-1) (they took the right). They play well, so you get the smaller one.
3. Same for taking the right coin a[j]: you get a[j] + min(f(i+1, j-1), f(i, j-2)).
4. Answer the bigger of the two.

class Solution {
    public int optimalStrategy(int[] arr) {
        return f(arr, 0, arr.length - 1);
    }

    private int f(int[] a, int i, int j) {
        if (i > j) return 0;          // no coins left
        if (i == j) return a[i];      // one coin: take it
        // take the left coin, then the friend leaves us the worse option
        int takeLeft = a[i] + Math.min(f(a, i + 2, j), f(a, i + 1, j - 1));
        // take the right coin
        int takeRight = a[j] + Math.min(f(a, i + 1, j - 1), f(a, i, j - 2));
        return Math.max(takeLeft, takeRight);
    }
}

How long it takes: each call makes up to four calls on a row that is two coins shorter, so about O(2^n). Extra room: the call chain, O(n).

Way 2: the clever way

The helper only ever looks at a stretch i..j of the row. There are about n * n / 2 stretches. Fill a table best[i][j] for every stretch, short stretches first, so every answer you need is already there.

1. One coin: best[i][i] = a[i].
2. Two coins: the bigger one.
3. Longer stretches: best[i][j] = max(a[i] + min(best[i+2][j], best[i+1][j-1]), a[j] + min(best[i+1][j-1], best[i][j-2])).
4. The answer is best[0][n-1], the top right corner.

class Solution {
    public int optimalStrategy(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;
        int[][] best = new int[n][n];
        for (int gap = 0; gap < n; gap++) {            // stretch length minus 1
            for (int i = 0; i + gap < n; i++) {
                int j = i + gap;
                if (gap == 0) { best[i][j] = arr[i]; continue; }
                int a = (i + 2 <= j) ? best[i + 2][j] : 0;      // friend took left after us
                int b = (i + 1 <= j - 1) ? best[i + 1][j - 1] : 0; // the middle stretch
                int c = (i <= j - 2) ? best[i][j - 2] : 0;      // friend took right after us
                int takeLeft = arr[i] + Math.min(a, b);
                int takeRight = arr[j] + Math.min(b, c);
                best[i][j] = Math.max(takeLeft, takeRight);
            }
        }
        return best[0][n - 1];
    }
}

How long it takes: about n * n / 2 cells, each in a few steps, O(n^2). Extra room: the table, O(n^2).

Another way: count the lead

A neat version that interviewers like: let lead[i][j] be how far ahead the player to move can finish on coins i..j. If you take a[i], your friend then leads by lead[i+1][j], so your lead is a[i] - lead[i+1][j]. Take the better end. At the end your total is (sum + lead) / 2.

class Solution {
    public int optimalStrategy(int[] arr) {
        int n = arr.length;
        if (n == 0) return 0;
        int[] lead = new int[n];      // lead[j] holds lead for stretch i..j
        int sum = 0;
        for (int i = n - 1; i >= 0; i--) {
            sum += arr[i];
            lead[i] = arr[i];                        // one coin
            for (int j = i + 1; j < n; j++) {
                // lead[j] still holds i+1..j, lead[j-1] already holds i..j-1
                lead[j] = Math.max(arr[i] - lead[j], arr[j] - lead[j - 1]);
            }
        }
        return (sum + lead[n - 1]) / 2;
    }
}

This uses one row of n numbers, so O(n) extra room and still O(n^2) time.

Watch out for

• Greedy (always take the bigger end) is wrong. [8, 15, 3, 7] shows it.
• Index checks: best[i+2][j] and best[i][j-2] do not exist when the stretch has two coins. Treat them as 0.
• Fill by stretch length. A plain row by row loop from the top reads cells that are not ready yet.

What interviewers ask next

• Can the first player always win with an even number of coins? Yes, never lose. Color the coins in turns, odd and even positions. The first player can always take all odd ones or all even ones, whichever sum is bigger. That only proves you never lose, and the table gives the true best.
• Print the moves, not only the total. Keep which end gave the max in each cell, then follow it from best[0][n-1].
• What if a player may take one, two or three coins from the front only? A similar table over how many coins are left.
• Can you do it in O(n) space? Yes, with the lead version above.

Remember this

Grown-up words: planning for the friend's best move is minimax, a stretch of coins is an interval, the table is interval dynamic programming, and the lead version is a zero sum game score difference.