https://leetcode.com/problems/bag-of-tokens

The first thing we need to notice, that if we want to play token face up, we need to do it with the smallest value, if we want to play token down, we need to do it with the biggest value. So:

  1. Sort our tokens in increasing order.
  2. Now, we use two pointers approach, beg pointer deals with small values, and end pointer deals with big values.
  3. At each step, our goal is to maximize our score, so we first check if we can play our token up: if we can, we do it, decrease P, increase S; also we move beg one position to the right and we update our max_S: it can happen in future, that final S is not the biggest one, so we need to fix the biggest reached score. If it is not possible to play token up, we try to play token down: we increase our P, decrease S and move end pointer one place to the left. If both of these options are not possible, we break.
  4. Finally, we return max_S, maximum score reached during all traversal of tokens.

Complexity: time complexity is O(n log n) to sort our data and O(n) to use two pointers approach, so it is O(n log n) in all. Space complexity is O(log n), if we sort our tokens in place (it is not O(1), because for example merge or quick sort and others use recursion with O(log n) space for stack).

class Solution:
    def bagOfTokensScore(self, tokens, P):
        tokens.sort()
        beg, end, S, max_S = 0, len(tokens) - 1, 0, 0
        while beg <= end:
            if tokens[beg] <= P:
                P -= tokens[beg]
                S += 1
                max_S = max(max_S, S)
                beg += 1
            elif S >= 1:
                P += tokens[end]
                S -= 1
                end -= 1
            else: break
        return max_S

If you like the solution, you can upvote it on leetcode discussion section: Problem 0948