Shared Values, Sorted
EasyArrays & Hashing
Problem
Two warehouses each export the list of product codes they currently stock; a code may appear several times in a list.
Given the lists a and b, return every code that appears in both, each code once, in ascending order.
Example 1
- Input:
- a = [4, 9, 5], b = [9, 4, 9, 8, 4]
- Output:
- [4, 9]
4 and 9 are stocked in both warehouses; 5 and 8 are not.
Example 2
- Input:
- a = [1, 2], b = [3]
- Output:
- []
Constraints
- 0 ≤ a.length, b.length ≤ 10^5
- -10^9 ≤ a[i], b[i] ≤ 10^9
Hint
Show the first hint
Duplicates inside a list do not matter. What structure removes them and gives fast membership tests?
Walkthrough
How to approach it
01Clarify before coding
- Should repeated shared codes appear more than once? No, once each.
- Is the output order fixed? Yes, ascending, so the answer is unique.
- Are the inputs sorted? No.
02Brute force
For each value of a, scan all of b; add matches to the result if not already there.
Cost: O(|a| · |b|) time: 10^10 steps for two lists of 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.