You have an initial power P, an initial score of 0 points, and a bag of tokens.
Each token can be used at most once, has a value token[i], and has potentially two ways to use it.

If we have at least token[i] power, we may play the token face up, losing token[i] power, and gaining 1 point.
If we have at least 1 point, we may play the token face down, gaining token[i] power, and losing 1 point.

Return the largest number of points we can have after playing any number of tokens.
 



Example 1:
Input: tokens = [100], P = 50
Output: 0


Example 2:
Input: tokens = [100,200], P = 150
Output: 1


Example 3:
Input: tokens = [100,200,300,400], P = 200
Output: 2

 
Note:

tokens.length <= 1000
0 <= tokens[i] < 10000
0 <= P < 10000

Difficulty: interview

Starter code:

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        

Solutions:
class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        tokens = sorted(tokens)
        left = 0
        right = len(tokens) - 1
        points = 0

        if len(tokens) == 1:
            if tokens[0] <= P:
                return 1
        if len(tokens) == 0:
            return 0
        while left < right:

            if tokens[left] <= P:
                P -= tokens[left]
                left += 1
                points += 1

            elif tokens[left] > P and points > 0:
                P += tokens[right]
                points -= 1
                right -= 1
            
            
            elif points == 0 and tokens[left] > P:
                break
        if P >= tokens[left]:
            points += 1
        return points

class Solution:
    
    # O(nlog(n) + n) = O(n(log(n) + 1)) = O(nlog(n)) time / O(1) space or memory
    # Where 'n' is the number of tokens passed in the input
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        # we wanna maximize the points in this game (by giving the power to get points)
        # we can give point away to get power
        tokens.sort() # O(mlog(m))
        max_points = 0
        points = 0
        i = 0
        j = len(tokens) - 1
        
        while i <= j:
            if P >= tokens[i]:
                points += 1 # get a coin
                P -= tokens[i] # give up power
                max_points = max(points, max_points)
                i += 1
            elif points > 0:
                points -= 1 # give up that coin
                P += tokens[j] # get power
                j -= 1
            else:
                return max_points
            
        return max_points

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        max_points, points = 0, 0
        tokens.sort()
        i, j = 0, len(tokens) - 1
        while i <= j:
            if P < tokens[i]:
                if i == j or points == 0: break
                P += tokens[j]
                points -= 1
                j -= 1
            points += 1
            P -= tokens[i]
            i += 1
            max_points = max(max_points, points)
        return max(max_points, points)

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        tokens.sort()
        if(not tokens or P < tokens[0]):
            return 0
        l, r = 0, len(tokens)-1
        points = 0
        
        while(l <= r):
            if(P >= tokens[l]):
                points += 1
                P -= tokens[l]
                l += 1
            else:
                if(r-l > 1):
                    points -= 1
                    P += tokens[r]
                    r -= 1
                else:
                    break
        return points

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        if not tokens: return 0
        
        tokens.sort()
        
        point = 0
        while tokens:
            if P < tokens[0]:
                if point and len(tokens) > 1:
                    P += tokens.pop()
                    point -= 1
                else:
                    break
            else:
                P -= tokens.pop(0)
                point += 1
        
        return point

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        # use 100, P = 100, p = 1
        # 400 down, P = 500, p = 0
        # use 200, P = 300, p = 1
        # use 300, P = 0, p = 2

        '''
        sort tokens
        play smallest tokens until you can't anymore
        turn over largest tokens until you can play smaller tokens again
        '''
        
        tokens.sort()
        maxPoints = 0
        points = 0
        left, right = 0, len(tokens) - 1
        while left <= right and P >= 0:
            if P - tokens[left] >= 0:
                P -= tokens[left]
                points += 1
                maxPoints = max(maxPoints, points)
                left += 1
            else:
                if points > 0:
                    P += tokens[right]
                    
                    points -= 1
                    right -= 1
                else:
                    break
        
        return max(maxPoints, points)

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        tokens.sort()
        left = 0
        right = len(tokens) - 1
        ans = 0
        curr = 0
        while not left > right:
            if P >= tokens[left]:
                curr += 1
                ans = max(ans, curr)
                P -= tokens[left]
                left += 1
            elif curr > 0:
                P += tokens[right]
                curr -= 1
                right -= 1
            else: break
            
        return ans

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        n = len(tokens)
        tokens.sort()
        i = 0
        j = n-1
        points = 0
        result = 0
        
        while i <= j:
            if tokens[i] <= P:
                points += 1
                result = max(result, points)
                P -= tokens[i]
                i += 1
            else:
                if points == 0:
                    break
                P += tokens[j]
                points -= 1
                j -= 1
        
        return result

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        max_points, points = 0, 0
        tokens.sort()
        i, j = 0, len(tokens) - 1
        while i <= j:
            if P < tokens[i]:
                if i == j or points == 0: break
                P += tokens[j]
                points -= 1
                j -= 1
            points += 1
            P -= tokens[i]
            i += 1
            max_points = max(max_points, points)
        return max_points

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        startIndex = 0
        endIndex = len(tokens) - 1
        points = 0
        tokens.sort()
        while(True):
            print(startIndex, endIndex, P)
            if(startIndex > endIndex or endIndex < startIndex):
                return points
            if(P >= tokens[startIndex]):
                points += 1
                P -= tokens[startIndex]
                startIndex += 1
            else:
                if(points == 0):
                    return points
                else:
                    if(startIndex == endIndex):
                        return points
                    else:
                        P += tokens[endIndex]
                        endIndex -= 1
                        points -= 1

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        tokens.sort()
        
        buyer,seller = 0,len(tokens)-1
        max_items = current_items = 0
        
        while buyer <= seller:
            if P >= tokens[buyer]:
                P -= tokens[buyer]
                current_items+=1
                buyer+=1
            else:
                if current_items ==0:
                    break;
                else:
                    P += tokens[seller]
                    current_items -=1
                    seller -=1
            max_items = max(max_items,current_items)
        return max_items

class Solution:
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        if not len(tokens) :
            return 0
        tokens.sort()
        res = 0
        deque = collections.deque(tokens)
        
        while( len( deque ) > 1 and ( P >= deque[0] or res ) ):
            while( deque and P > deque[0] ):
                res += 1
                P -= deque.popleft()
            if( len( deque ) > 1 and res ):
                P += deque.pop()
                res -= 1

        if ( deque and P >= deque[0] ):
            res += 1
        return res

class Solution:
    # all the tokens start in a neutral position. Can either play it face up or face down.
    def bagOfTokensScore(self, tokens: List[int], P: int) -> int:
        tokens.sort()
        
        # start from front and back. greedily take all the powers from the front and spend score in back to get more to add to the front
        def twoPointer(tokens, P):
            i = 0
            j = len(tokens)-1
            score = 0
            maxScore = 0
            while i <= j:

                flag = False
                while i < len(tokens) and P >= tokens[i]:
                    score += 1
                    P -= tokens[i]
                    i += 1
                    flag = True
                if flag:
                    maxScore = max(score, maxScore)
                    continue
                    
                if score > 0:
                    score -= 1
                    P += tokens[j]
                    j -= 1
                
                elif P < tokens[i]:
                    return score
            return maxScore
        
        def helper(tokens, P, score):
            maxVal = score
            if score > 0 and len(tokens) > 0:
                maxVal = max(helper(tokens[:len(tokens)-1], P + tokens[len(tokens)-1], score - 1), maxVal)
        
            for i in range(len(tokens)-1, -1, -1):
                if P >= tokens[i]:
                    maxVal = max(helper(tokens[:i] + tokens[i+1:], P - tokens[i], score + 1), maxVal)
            return maxVal
        
        return twoPointer(tokens, P)