948 Bag of Tokens

Link: Bag of Tokens

Thought

For this question, I find we could do 2 things: spend any cost form the tokens, and get 1 point. Or, spend 1 point, get any power from the tokens. So it turns to be pretty clear that I will firstly sort all tokens by value, and trying to get as much point as possible by flipping from left(smaller) side. If I can not flip any more, try to gain as much power as possible(AKA from right side).

And during the same time, keep tracking the maximum points I can get.

Code

class Solution(object):
    def bagOfTokensScore(self, tokens, P):
        """
        :type tokens: List[int]
        :type P: int
        :rtype: int
        """
        tokens.sort()
        init = 0
        maxx = 0
        lindx = 0
        rindx = len(tokens) - 1
        while lindx <= rindx:
            while lindx <= rindx and tokens[lindx] <= P:
                P -= tokens[lindx]
                init += 1
                lindx += 1
            maxx = max(maxx, init)
            if init == 0:
                break
            if lindx <= rindx:
                init -= 1
                P += tokens[rindx]
                rindx -= 1
        return maxx

Runtime

Time: O(NlogN)

Space: O(1)