Predict the Winner

Problem

Given an array of scores that are non-negative integers. Player 1 picks one of the numbers from either end of the array followed by the player 2 and then player 1 and so on. Each time a player picks a number, that number will not be available for the next player. This continues until all the scores have been chosen. The player with the maximum score wins.

Given an array of scores, predict whether player 1 is the winner. You can assume each player plays to maximize his score.

Recursion

Idea
- i == j -> pick i
- i != j
  - pick i -> let player2 pick in (i + 1 … j)
  - pick j -> let player2 pick in (i … j - 1)
  - compare the values between these 2 options, find the max.

Solution

public boolean PredictTheWinner(int[] nums) {
    return predictHelper(nums, 0, nums.length - 1) >= 0;
}

public int predictHelper(int[] nums, int left, int right) {
    if (left == right) {
        return nums[left];
    }
    return Math.max(
        nums[left] - predictHelper(nums, left + 1, right),
        nums[right] - predictHelper(nums, left, right - 1));
}

Analysis
Time complexity: O(2^n)
Space complexity: O(n)

Memorization

Idea
In the last approach, a lot of duplicate calls to predictHelper function will be made with the same set of arguments, since the same subarray could be obtained by following different paths in the search space. This redundancy can be removed by making use of memoization.

Solution

public boolean PredictTheWinner(int[] nums) {
    Integer[][] cache = new Integer[nums.length][nums.length];
    return predictHelper(nums, 0, nums.length - 1, cache) >= 0;
}

public int predictHelper(int[] nums, int left, int right, Integer[][] cache) {
    if (left == right) {
        return nums[left];
    }
    return cache[left][right] != null ?
        cache[left][right] :
        Math.max(
            nums[left] - predictHelper(nums, left + 1, right, cache),
            nums[right] - predictHelper(nums, left, right - 1, cache));
}

Analysis
Time complexity: O(n^2)
Space complexity: O(n^2)

DP

Idea
- dp[i][j]: maximum effective score possible for the subarray nums[i,j].
- dp[i][j] = Math.max((nums[i] - dp[i + 1][j]), nums[j] - dp[i][j - 1])

Solution

public class Solution {
    public boolean PredictTheWinner(int[] nums) {
        int[][] dp = new int[nums.length + 1][nums.length + 1];
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i + 1; j < nums.length; j++) {
                dp[i][j] = Math.max(nums[i] - dp[i + 1][j], nums[j] - dp[i][j - 1]);
            }
        }
        return dp[0][nums.length - 1] >= 0;
    }
}

public boolean PredictTheWinnerOptimized(int[] nums) {
      int[] dp = new int[nums.length];
      for (int i = nums.length - 1; i >= 0; i--) {
          for (int j = i + 1; j < nums.length; j++) {
              dp[j] = Math.max(nums[i] - dp[j], nums[j] - dp[j - 1]);
          }
      }
      return dp[nums.length - 1] >= 0;
  }

Analysis
Time complexity: O(n^2)
Space complexity: O(n^2) / O(n)

Problem

Recursion

Memorization

DP

More info