Common Readings
EasyTwo Pointers
Problem
Two weather stations log temperature readings, each list sorted in non-decreasing order: a and b. A reading counts as shared as many times as it appears in both lists (if 2 appears three times in a and twice in b, it is shared twice).
Return the shared readings in non-decreasing order.
Example 1
- Input:
- a = [1, 2, 2, 3, 5], b = [2, 2, 2, 5, 7]
- Output:
- [2, 2, 5]
2 appears twice in a and three times in b → shared twice; 5 once.
Example 2
- Input:
- a = [1, 4], b = [2, 3]
- Output:
- []
Constraints
- 0 ≤ a.length, b.length ≤ 10^5
- -10^9 ≤ a[i], b[i] ≤ 10^9
- a and b are sorted in non-decreasing order
Hint
Show the first hint
Compare the two smallest unused readings. If they differ, can the smaller one still be shared?
Walkthrough
How to approach it
01Clarify before coding
- Do duplicates count with multiplicity? Yes, min(count in a, count in b) copies.
- Is the output sorted? Yes, non-decreasing.
- Could a hash map be used? Yes, but sortedness gives O(1) extra memory.
02Brute force
For each element of a, search b for an unused equal element and mark it used.
Cost: O(n · m) time, or O(n + m) with a counting map using O(n) memory.
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.