# Java 1 Line Recursion Solution

• ``````public class Solution {
public boolean PredictTheWinner(int[] nums) {
return helper(nums, 0, nums.length-1)>=0;
}
private int helper(int[] nums, int s, int e){
return s==e ? nums[e] : Math.max(nums[e] - helper(nums, s, e-1), nums[s] - helper(nums, s+1, e));
}
}
``````

Inspired by @sameer13, add a cache:

``````public class Solution {
public boolean PredictTheWinner(int[] nums) {
return helper(nums, 0, nums.length-1, new Integer[nums.length][nums.length])>=0;
}
private int helper(int[] nums, int s, int e, Integer[][] mem){
if(mem[s][e]==null)
mem[s][e] = s==e ? nums[e] : Math.max(nums[e]-helper(nums,s,e-1,mem),nums[s]-helper(nums,s+1,e,mem));
return mem[s][e];
}
}
``````

Explanation
So assuming the sum of the array it SUM, so eventually player1 and player2 will split the SUM between themselves. For player1 to win, he/she has to get more than what player2 gets. If we think from the prospective of one player, then what he/she gains each time is a plus, while, what the other player gains each time is a minus. Eventually if player1 can have a >0 total, player1 can win.

Helper function simulate this process. In each round:
if e==s, there is no choice but have to select nums[s]
otherwise, this current player has 2 options:
--> nums[s]-helper(nums,s+1,e): this player select the front item, leaving the other player a choice from s+1 to e
--> nums[e]-helper(nums,s,e-1): this player select the tail item, leaving the other player a choice from s to e-1
Then take the max of these two options as this player's selection, return it.

• @chidong Brilliant!

• same strategy, but does not work for python. It says time limit exceeded.

class Solution(object):
def PredictTheWinner(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""

``````    def MaxScore(l,s,e):

if e-s == 1:
#print e,s
return max(l[s:e+1]),min(l[s:e+1])

if e==s:
return l[e],0

M2_a, M1_a = MaxScore(l,s+1,e)
M1_a += l[s]

M2_b, M1_b = MaxScore(l,s,e-1)
M1_b += l[e]

if M1_a > M1_b:
return M1_a, M2_a
else:
return M1_b, M2_b

if len(nums)<3:
return True

r1,r2 = MaxScore(nums,0,len(nums)-1)

return r1>=r2``````

• Brilliant solution

Rewritten in c++
class Solution {
private:
int nextPlayer(vector<int>& nums, int start, int end){
// Each player level will pick the ends which will maximize their score
return (start == end) ? nums[start] : max(nums[start] - nextPlayer(nums,start+1,end) , nums[end] - nextPlayer(nums,start,end-1));
}
public:
bool PredictTheWinner(vector<int>& nums) {
return nextPlayer(nums, 0, nums.size()-1) >= 0;
}
};

Spoiler

• )

Good solution. However, if you make use of memoization by storing the intermediate results, it would become great solution.

• @sameer13 Thanks. Edited.

• Could you explain what you are doing? What's the return value of helper()?

Thanks!

• @zzwcsong Explained. Helper function returns the maximum gain for the current player in this round with the selection choice from s to e. Gain: plus his/her own selection in this round and minus the opponent's gain in the next round.

• Python memoization version based on your brilliant idea.

``````class Solution(object):
def PredictTheWinner(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
self.memo = {}
def helper(i, j):
if (i,j) not in self.memo:
self.memo[(i, j)] = nums[i] if i == j else \
max(nums[i] - helper(i+1, j), nums[j] - helper(i, j-1))
return self.memo[(i, j)]
return helper(0, len(nums)-1) >= 0
``````

• Note that only the score difference `int sd` and tiebreaker `bool tb` matter in the game's outcome, i.e.,

• A player wins if and only if his `sd + tb > 0`.

I have a post with a different version of practically 1-liner DFS:

``````    bool PredictTheWinner(vector<int>& a, int s = 0, size_t e = INT_MAX, int sd = 0, bool tb = true) {
return s==e? sd+tb>0 : !PredictTheWinner(a, s+1, e=min(e,a.size()), -sd-a[s],   !tb) ||
!PredictTheWinner(a, s,   e-1,               -sd-a[e-1], !tb);
}
``````

Note: `[s, e)` is the remaining score index range.

• Good solution. But I want to point out that this is not really an one-line solution. It is a multi-line solution written in one line, which makes it harder to understand.

• @austurela Yes, you are right. I squeezed multiple logic blocks into one line for fun :-)

• @tbjc Refer to this post which talks about Tail Recursion. I have faced similar problem before.

• Super nice solution! Thanks!

• talks

Thanks for your suggestion. But I do not think TRO is the cause. In Chidong's method, the return is not simply the function head, so even his java code can not be optimized by TRO. I think this is just a bug for leetcode. TLE standards should be the same for different language. But the modified code with cache or memorization does work.

• Can somebody please explain to me the overlapping sub problems over here as we are using dynamic programming?

• @tbjc add memoization to it
As the problem has repeated subproblem, memoization will solve the issue for now.
Which is the essential condition for a DP.

``````class Solution(object):
def __init__(self):
self.mem={}

def PredictTheWinner(self, nums):
p1,p2=self.rec(nums, 0, len(nums)-1, False)
#print(self.mem )
return p1>=p2

def rec(self, nums, st, end, turn):
#end conition
if(st==end):
p2score=p1score=0
if(turn):
p2score+=nums[st]
else:
p1score+=nums[st]
return (p1score, p2score)
index=int(turn)

#memoization
if((st,end) in self.mem):
#print(index, st,end)
return self.mem[(st,end)]
nextTurn=not turn

if(turn):
#p2
first=self.rec(nums,st+1, end, nextTurn)
first=(first[0],nums[st]+ first[1])
last=self.rec(nums, st, end-1, nextTurn)
last=(last[0], last[1]+nums[end])
else:
#player 1 turn
first=self.rec(nums, st+1, end, nextTurn)
first=(first[0]+nums[st], first[1])
last=self.rec(nums, st, end-1, nextTurn)
last=(last[0]+nums[end], last[1])

maxy= first if first[index]>last[index] else last

#print(index,st,end,"->", maxy, "[", first, last)
self.mem[(st,end)]=maxy
return maxy
``````

• bravoooooooooooooooooooo!!!

• Hey @Chidong thanks for sharing your solution. Could you tell me, what would be the time complexity of this solution? I am confused.. Thank you :)

• Time complexity?

Acc to me, it should be O(2^n) for non-memoized and O(n^2) for memoized.

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