Recount Seal Arbitration
Original indices surviving magnitude-based conflicts in a signed integer array
An election office receives a sequence of recount seals. Each seal has a nonzero signed integer score:
- A positive score is a clearance seal.
- A negative score is a hold seal.
- The absolute value of the score is the seal's authority.
The office maintains an ordered row of surviving seals, initially empty. Process the seals in their original order, appending each new seal to the row.
Whenever the final two seals in the row are a clearance seal followed by a hold seal, they conflict. Resolve that conflict as follows:
- If their authorities differ, discard the seal with lower authority. The surviving seal keeps its original score.
- If their authorities are equal, discard both seals.
After resolving a conflict, check the final two surviving seals again. Continue until they no longer conflict, then process the next input seal. No other pair of seal types conflicts.
Return the zero-based original indices of the seals remaining after all processing, in increasing order.
Examples
Example 1
Input: scores = [9,3,-5,2] Output: [0,3]
The hold seal at index 2 first defeats the clearance seal at index 1, then loses to the stronger clearance seal at index 0. The last clearance seal creates no conflict.
Example 2
Input: scores = [4,-4,-2,7] Output: [2,3]
The first clearance and hold seals have equal authority, so both are discarded. The next hold seal remains, and the final clearance seal does not conflict with it.
Example 3
Input: scores = [2,6,-8] Output: [2]
The final hold seal defeats both earlier clearance seals in succession.
Constraints
- 0 <= len(scores) <= 8000
- -10^9 <= scores[i] <= 10^9
- scores[i] != 0
The intended solution takes O(n) time and O(n) auxiliary space. Each seal is pushed at most once and removed at most once.
Hints
Show hint 1Hint 1
Only the last surviving seal can initially interact with a newly appended seal.
Show hint 2Hint 2
Keep surviving indices in a stack. A hold seal may remove several clearance seals before it is discarded or survives.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you return the surviving scores alongside their original indices?
- Can you process seals incrementally as they arrive without storing the complete input?
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