Best Rotation for the Scoreboard
HardArrays & Hashing
Problem
A scoreboard shows the values nums (each between 0 and n - 1) in a row of n slots. Rotating by k shows [nums[k], nums[k+1], …, nums[n-1], nums[0], …, nums[k-1]].
After rotating, the board earns one point for every slot j whose shown value is at most j. Return the rotation k (0 ≤ k < n) that earns the most points; if several tie, return the smallest such k.
Example 1
- Input:
- nums = [2, 3, 1, 4, 0]
- Output:
- 3
k = 3 shows [4, 0, 2, 3, 1]: slots 1, 2, 3, 4 score, 4 points. No rotation scores 5.
Example 2
- Input:
- nums = [2, 2, 0, 1]
- Output:
- 2
k = 2 shows [0, 1, 2, 2]: every slot scores, 4 points.
Example 3
- Input:
- nums = [1, 3, 0, 2, 4]
- Output:
- 0
Every rotation scores 3, so the smallest k wins.
Constraints
- 1 ≤ n ≤ 10^5
- 0 ≤ nums[i] < n
Hint
Show the first hint
Instead of scoring each rotation, ask the reverse question for each value: for which rotations k does it score?
Walkthrough
How to approach it
01Clarify before coding
- Which direction is a rotation? Rotation k moves nums[k] to slot 0 (a left shift by k).
- Ties? Return the smallest k.
- Are values always within 0..n-1? Yes, so every value scores for at least one rotation.
02Brute force
For each k from 0 to n - 1, build the rotated board and count scoring slots.
Cost: O(n²) time: 10^10 steps at n = 10^5.
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.