What two lists have in common
EasyStuck?
Show a hintHide the hint
Put the first list in a set, then walk the second collecting anything the set contains. Use a set for the answer too, so nothing repeats.
The idea behind this problem
Next in this lesson
Longest run of consecutive numbersGiven two lists, return the values that appear in both, each one only once, in increasing order.
Worked example#
For [4, 9, 5] and [9, 4, 9, 8, 4]:
| value | in the first? | in the second? | in the answer? |
|---|---|---|---|
| 4 | yes | yes | yes |
| 9 | yes | yes | yes |
| 5 | yes | no | no |
| 8 | no | yes | no |
So the answer is [4, 9], sorted.
Note that 9 and 4 appear twice in the second list but only once in the answer, which is what makes a set the right tool: it remembers whether something is present, not how often.
Checking every pair would be n × m comparisons. Putting one list in a set and walking the other is n + m.
Constraints#
1 <= length of each list <= 1000000 <= values <= 10^9
Input
a is a count then that many integers. b is a count then that many integers.
Output
The shared values in increasing order, separated by spaces.
Examples
Input
3 4 9 5 5 9 4 9 8 4
Output
4 9
4 and 9 are in both lists. They appear once each in the answer even though 9 appears twice in the second list.
Input
3 1 2 3 3 4 5 6
Output
Nothing is shared, so the answer is empty.
Input
2 1 1 2 1 1
Output
1
Only one 1 in the answer, however many times it appears.
Something wrong with this problem? Report an issue
Ready to try it
Write your solution in C, C++, Java or Python and see every test case come back with the time and memory it took.
Free, and it stays free. No card.