Spotlight Cooldown Scores
Final array after repeatedly halving the leftmost maximum, rounded down
A social network is testing a spotlight carousel for a fixed collection of posts. Each post has a nonnegative integer freshness score. The score of post i is initially scores[i].
For each of rounds spotlight rounds:
- Choose the post with the highest current freshness score.
- If several posts share that score, choose the one with the smallest original index.
- Replace the chosen post's score with half its current score, rounded down.
Posts remain eligible for future rounds, even when their score becomes zero. Original indices never change.
Return the final freshness scores in the same order as the input.
Examples
Example 1
Input: scores = [9,9,4], rounds = 3 Output: [2,4,4]
The first round selects post 0 because it wins the initial tie. The second selects post 1, and the third selects post 0 because all three posts then share the highest score.
Example 2
Input: scores = [0,7], rounds = 5 Output: [0,0]
The zero-score post remains eligible, but the other post has a higher score until repeated halving also brings it to zero.
Example 3
Input: scores = [8,3,8], rounds = 0 Output: [8,3,8]
With no spotlight rounds, every post keeps its initial score.
Constraints
- 1 <= scores.length <= 4000
- 0 <= scores[i] <= 1000000000
- 0 <= rounds <= 100000
- All scores and rounds are integers.
The reference solution uses a heap ordered by descending score and ascending index. It runs in O(n + rounds log n) time and O(n) auxiliary space. Once the maximum score is zero, later rounds cannot change the returned scores.
Hints
Show hint 1Hint 1
Which data structure lets you repeatedly retrieve the highest-priority post without scanning every post?
Show hint 2Hint 2
Include the original index in each priority so ties are resolved consistently. Only the selected post's priority changes.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you also return the index selected in every round?
- How would the priority structure change if each post had its own positive cooldown divisor?
Practice this with an AI interviewer
Explain your approach out loud, write Python or JavaScript, run it against hidden tests (including large inputs), and get a scored debrief.
Start this problem