Free Hashing lessonsHashing · Stage 3 · Sets for structure · Step 1

What both lists share

Find the values that appear in both lists, using a set of one of them. About 7 minutes.

Ask one list about the other

Two friends compare their playlists: which songs do both have? Put one friend's songs in a set. Then go through the other friend's list, and for each song ask the set "is it there?". Every yes is a shared song.

Collect the shared songs in a second set, so a song that appears twice in the list is still listed once.

One set, then lookups: one question per song.

a = [4, 9, 5] goes in a set; now walk b

both: {9}
set(a): {4, 9, 5}

9: a's set knows it. Add it to the answer set.

Move 1 of 5

Sort at the end if order matters

Sets don't keep any useful order. If the answer must be sorted, sort it at the very end. You only sort the shared values, which is usually a short list.

Each shared value appears once in the answer, however many copies either list had. For 4, 9, 5 and 9, 4, 9, 8, 4 the answer is just 4, 9.

Sort only the shared values: at the very end.

In code

in_a = set(a)
both = set()
for x in b:
    if x in in_a:
        both.add(x)
return sorted(both)

Quick check

The lists are 1, 2, 2, 1 and 2, 2. What's the answer?

A2
B2, 2
C1, 2

Show the answer

2. 2 is the only value in both, and it's listed once.

Your problem

Values in both lists

Return the distinct values that appear in both lists, from smallest to largest.

Example

a = [4, 9, 5], b = [9, 4, 9, 8, 4] → [4, 9]

0 ≤ lengths ≤ 1,000,000

Solve it in your browserFree account, no card. Python, C++, Java or JavaScript, with hints if you get stuck, and your progress is saved.