Java 1 Line Recursion Solution


  • 68
    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.


  • 1

    @chidong Brilliant!


  • 0
    T

    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

  • 0
    F

    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


  • 1
    S

    @chidong said in Java 1 Line Recursion Solution:

    )

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


  • 1

    @sameer13 Thanks. Edited.


  • 0
    Z

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

    Thanks!


  • 2

    @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.


  • 2

    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
    

  • 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.


  • 1
    A

    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.


  • 0

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


  • 0
    H

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


  • 0
    C

    Super nice solution! Thanks!


  • 0
    T

    @harshaneel said in Java 1 Line Recursion Solution:

    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.


  • 0
    M

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


  • 0
    A

    @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
    

  • 0
    X

    bravoooooooooooooooooooo!!!


  • 0
    I

    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 :)


  • 1
    P

    Time complexity?

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


Log in to reply
 

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