java recursive self explanatory solution


  • 1
    P
    public boolean PredictTheWinner(int[] nums) {
    
            if (nums == null || nums.length < 1) {
                return false;
            }
    
            int totalSum = 0;
    
            for (int i = 0; i < nums.length; i++) {
                totalSum += nums[i];
            }
            int firstPlayerSum = helper(nums, 0, nums.length - 1);
            int secondPlayerSum = totalSum - firstPlayerSum;
    
            return firstPlayerSum >= secondPlayerSum;
        }
    
        private int helper(int[] nums, int start, int end) {
    
            if (start > end) {
                return 0;
            }
    
            int first = nums[start] + Math.min(helper(nums, start + 2, end), helper(nums, start + 1, end - 1));
            int last = nums[end] + Math.min(helper(nums, start + 1, end - 1), helper(nums, start, end - 2));
    
            return Math.max(first, last);
        }

  • 0

    @pramodnegi I like your solution, easier to follow. But during the recursion there are overlapping combinations of start and end, which is a DP problem. So I added the DP part into your solution, and it runs 6ms!

    public class Solution {
        
        int[][] mem;
        
        public boolean PredictTheWinner(int[] nums) {
    
            if (nums == null || nums.length < 1) {
                return false;
            }
    
            int totalSum = 0;
    
            for (int i = 0; i < nums.length; i++) {
                totalSum += nums[i];
            }
            
            mem = new int[nums.length][nums.length];
            
            int firstPlayerSum = helper(nums, 0, nums.length - 1);
            int secondPlayerSum = totalSum - firstPlayerSum;
    
            return firstPlayerSum >= secondPlayerSum;
        }
    
        private int helper(int[] nums, int start, int end) {
    
            if (start > end) {
                return 0;
            }
            
            if(mem[start][end]>0)
                return mem[start][end];
    
            int first = nums[start] + Math.min(helper(nums, start + 2, end), helper(nums, start + 1, end - 1));
            int last = nums[end] + Math.min(helper(nums, start + 1, end - 1), helper(nums, start, end - 2));
            mem[start][end] = Math.max(first, last);
            return Math.max(first, last);
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.