20. Common Guests
Two parties were held on the same weekend. Each guest has a badge number, and the guest lists of the two parties are given as arrays; a guest may appear more than once on a list if they were scanned in several times.
Write a method commonElements that takes the arrays a and b and returns the badge numbers that appear in both lists. Each badge number must appear only once in the answer, and the answer must be sorted from smallest to largest.
Example 1
- Input:
- a = [1,2,2,1], b = [2,2]
- Output:
- [2]
- Explanation:
Only badge 2 is on both lists, and it is reported once.
Example 2
- Input:
- a = [4,9,5], b = [9,4,9,8,4]
- Output:
- [4,9]
- Explanation:
Badges 4 and 9 appear on both lists; in sorted order the answer is [4, 9].
Constraints
1 ≤ a.length, b.length ≤ 1000
-109 ≤ a[i], b[i] ≤ 109
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n log n)
- Space
- O(n)