Correction Night Leaders
Smallest index of a maximum array value after each additive update
An election office maintains provisional vote totals for candidate_count candidates, numbered from 0 through candidate_count - 1. Every candidate initially has zero votes.
The office processes a correction log in order. Entry i adds adjustments[i] to the vote total of candidate candidates[i]. A positive adjustment records newly verified votes, a negative adjustment removes previously counted votes, and a zero adjustment leaves the total unchanged. The log is guaranteed never to make any candidate's total negative.
After each entry, the office publishes the current leader: the candidate with the largest vote total. If several candidates share that total, the candidate with the smallest number leads. Candidates who have never appeared in the log still participate with zero votes.
Return the published leader numbers in log order. An empty log produces an empty list.
Examples
Example 1
Input: candidate_count = 4, candidates = [2,1,1,2,3], adjustments = [5,5,-2,-4,4] Output: [2,1,2,1,3]
The first two corrections give different candidates equal totals, so the candidate-number tie rule matters. Later corrections remove votes and can change the leader without increasing anyone else's total.
Example 2
Input: candidate_count = 5, candidates = [4,2,4,2], adjustments = [3,2,-3,-2] Output: [4,4,2,0]
Both candidates who receive votes later lose all of them. At that point, the tie rule applies to every candidate, including those absent from the log.
Example 3
Input: candidate_count = 1, candidates = [], adjustments = [] Output: []
There are no corrections, so there are no leader announcements.
Constraints
- 1 <= candidate_count <= 100000
- candidates.length == adjustments.length
- 0 <= candidates.length <= 4000
- 0 <= candidates[i] < candidate_count
- -1000000 <= adjustments[i] <= 1000000
- After every correction, every candidate's vote total is nonnegative.
A lazy heap solution takes O(m log(m + 1)) time and O(m) space for m log entries. It need not allocate an array of length candidate_count. Zero-total candidates can remain implicit: if nobody has a positive total, candidate 0 leads.
Hints
Show hint 1Hint 1
A candidate can lose votes, so a previously largest total cannot simply be kept as the current answer.
Show hint 2Hint 2
Store positive totals in a priority queue ordered by descending total and ascending candidate number. When examining the top, check whether its recorded total still matches the current total.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you support a much longer log while keeping priority-queue storage proportional to the number of candidates that have appeared?
- How would the design change if candidates could have negative totals, while unmentioned candidates still started at zero?
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