Java O(1) space solution with Game Theory

• 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;
}
}
``````

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