Bonus Tokens for the Team
HardGreedy
Problem
Employees sit in a row and each has a performance score scores[i]. A manager hands out bonus tokens with two rules: everyone gets at least one token, and anyone with a strictly higher score than an immediate neighbour gets more tokens than that neighbour.
Return the minimum total number of tokens.
Example 1
- Input:
- scores = [1, 0, 2]
- Output:
- 5
Tokens [2, 1, 2].
Example 2
- Input:
- scores = [1, 2, 2]
- Output:
- 4
Tokens [1, 2, 1]: equal neighbours have no constraint between them.
Example 3
- Input:
- scores = [1, 3, 4, 5, 2]
- Output:
- 11
Tokens [1, 2, 3, 4, 1].
Constraints
- 1 ≤ scores.length ≤ 2 · 10^4
- 0 ≤ scores[i] ≤ 2 · 10^4
Hint
Show the first hint
Split the rule in two: the constraint with the left neighbour and the constraint with the right neighbour.
Walkthrough
How to approach it
01Clarify before coding
- Do equal neighbours need equal tokens? No: there is no constraint between equal scores.
- Is it only immediate neighbours? Yes.
- Is the answer the total only? Yes.
02Brute force
Start everyone at 1 and repeatedly fix any violated constraint by raising the higher-scoring person, until nothing changes.
Cost: O(n²) in the worst case (a long descending run is fixed one step per sweep): 4 · 10^8 operations.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.