Recount Disagreement Slips
Sorted unmatched elements after canceling equal pairs across two arrays
An election office independently counts the same ballot box twice. Each count produces a sorted list of candidate codes, with one occurrence of a code for every ballot credited to that candidate.
You are given the two lists, first and second, both sorted in nondecreasing order. Cancel occurrences with the same code across the two lists, one occurrence from each list at a time, until no more matches are possible.
Return all uncanceled codes in nondecreasing order. Include each code as many times as it remains unmatched, regardless of which count it came from.
For example, if a code occurs five times in one count and twice in the other, that code must appear three times in the returned list. If every occurrence can be canceled, return an empty list.
Examples
Example 1
Input: first = [1,1,3,5], second = [1,2,3,3] Output: [1,2,3,5]
Some occurrences match across the counts, while others remain unmatched. The extra occurrence of candidate 1 comes from the first count, and the unmatched occurrences of candidates 2, 3, and 5 come from their respective counts.
Example 2
Input: first = [4,4,7], second = [4,4,7] Output: []
Both counts contain exactly the same number of occurrences of every candidate code, so every occurrence is canceled.
Example 3
Input: first = [], second = [2,2,9] Output: [2,2,9]
The first count is empty, so none of the occurrences in the second count can be canceled.
Constraints
- 0 <= first.length, second.length <= 6000
- 1 <= first[i], second[i] <= 999999
- Both lists are sorted in nondecreasing order.
This is an Easy problem. The intended solution runs in O(n + m) time and uses O(1) auxiliary space, excluding the returned list. Do not modify the input lists.
Hints
Show hint 1Hint 1
Compare the smallest occurrence that has not yet been processed in each list.
Show hint 2Hint 2
Equal codes cancel each other. If the codes differ, the smaller code cannot match any remaining code in the other list.
Follow-up questions
What an interviewer might ask once you have a working solution.
- How would you change the result to identify which count contributed each unmatched occurrence?
- If the lists were not sorted, what approaches could you use, and how would their complexity differ?
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