Java O(1) space solution with Game Theory


  • 0
    X

    Some one might argue that if you are using recursion, it is not O(1) space. Well, but I saw many posts use O(n) space as well as recursion.

    The idea is from game theory: In all possibilities if you can find one that make the other lose, you win. Here there are only 2 possibilities: pick the first or the last.

    class Solution {
        public boolean PredictTheWinner(int[] nums) {
            return helper(nums, 0, nums.length - 1, 0, 0, true);
        }
        
        private boolean helper(int[] nums, int left, int right, int me, int other, boolean isMe) {
            if (left > right) {
                if (isMe) return me >= other; // From the test we know that I win if there is a tie
                else return other > me;
            }
            
            if (left <= right && left < nums.length) {
                if (isMe) {
                    // My turn
                    if (!helper(nums, left + 1, right, me + nums[left], other, !isMe)) return true;
                } else {
                    // Other's turn
                    if (!helper(nums, left + 1, right, me, other + nums[left], !isMe)) return true;
                }
            }
            
            if (left <= right && right >= 0) {
                if (isMe) {
                    // My turn
                    if (!helper(nums, left, right - 1, me + nums[right], other, !isMe)) return true;
                } else {
                    // Other's turn
                    if (!helper(nums, left, right - 1, me, other + nums[right], !isMe)) return true;
                }
            }
            return false;
        }
    }
    

Log in to reply
 

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