visual walkthrough
Bag of Tokens
Greedily spend at one end and gain at the other.
The idea
Gaining a point is cheapest with the lowest-value token, and recovering power is most efficient with the highest-value one. Sort, then play the cheapest face up whenever you can, and sell the dearest face down only when you're stuck.
Track the best score along the way, since the final score may be lower than the peak.
Complexity
| approach | time | space |
|---|---|---|
| Sort + two pointers | O(n log n) | O(1) |