Hash set membership

When to use it

Use it when all you need to know about a value is whether you have it, not where it was or how many times it came.

It belongs to the foundations group: Remember what you have seen, in a shape that makes the next question take one step.

Watch it work

A radio station played these songs in this order. Return each song once, in the order it was first played.

Input
songs = ["sun", "rain", "sun", "wind", "rain"]

Output
["sun", "rain", "wind"]

The method

1. Start with an empty set of songs seen and an empty answer
2. A song already in the set was played before: skip it
3. A new song goes into the answer and into the set
4. Every song was looked at once: return the answer

The run, one moment at a time

1. Step 1. No song has been looked at, so the set and the answer are empty.

   songs: sun rain sun wind rain
   seen: empty
   answer: empty
   

2. Step 3. "sun" is not in the set, so it is new. Add it to the answer and to the set.

   songs: sun rain sun wind rain
   seen: sun
   answer: sun
   

3. Step 3. "rain" is not in the set, so it is new. Add it to the answer and to the set.

   songs: sun rain sun wind rain
   seen: sun rain
   answer: sun rain
   

4. Step 2. "sun" is already in the set, so it was played before. Skip it.

   songs: sun rain sun wind rain
   seen: sun rain
   answer: sun rain
   

5. Step 3. "wind" is not in the set, so it is new. Add it to the answer and to the set.

   songs: sun rain sun wind rain
   seen: sun rain wind
   answer: sun rain wind
   

6. Step 2. "rain" is already in the set, so it was played before. Skip it.

   songs: sun rain sun wind rain
   seen: sun rain wind
   answer: sun rain wind
   

7. Step 4. Five songs, five lookups. The answer holds each song once, in the order first played.

   songs: sun rain sun wind rain
   seen: sun rain wind
   answer: sun rain wind
   

The code

The numbered comments are the steps of the method.

function solve(songs) {
  // 1. Start with an empty set of songs seen and an empty answer
  const seen = new Set();
  const first = [];
  for (const song of songs) {
    // 2. A song already in the set was played before: skip it
    if (seen.has(song)) continue;
    // 3. A new song goes into the answer and into the set
    first.push(song);
    seen.add(song);
  }
  // 4. Every song was looked at once: return the answer
  return first;
}

def solve(songs):
    # 1. Start with an empty set of songs seen and an empty answer
    seen = set()
    first = []
    for song in songs:
        # 2. A song already in the set was played before: skip it
        if song in seen:
            continue
        # 3. A new song goes into the answer and into the set
        first.append(song)
        seen.add(song)
    # 4. Every song was looked at once: return the answer
    return first

How to spot it

Asked: Has this value been seen before?

The set holds everything met so far, so the question is one lookup for each value.

Asked: Which values are in one list but not in the other?

Put one list in a set, then test each value of the other list against it.

Given: Values in no useful order, and all you ask is whether one is there

A set does not need order. It finds a value by the value itself, and yes or no is all it answers.

Limits: Up to 100,000 values, so checking every pair for a repeat is too slow

Every pair is about 5 billion comparisons. One set check for each value is 100,000.

Looks like it, but is not

• You must return the position of the matching value, not only that it exists. Use Hash map lookup. A set says yes or no. A map keeps something beside each value, such as its position.
• You must know how many times each value appears. Use Frequency counting. A set forgets repeats. Counting needs a number kept for each value.
• The list is sorted and you are looking for one value. Use Binary search on a sorted range. Sorted order already lets you find a value in a few steps, with no extra memory.

Cost and mistakes

Time grows with the number of values, about n steps, written O(n), because each check and each add is one step on average. Extra space is one set entry for each different value.

Watch out

• Check before you add. If the value goes into the set first, every value looks like a repeat.
• A set matches simple values. To remember a pair such as a row and a column, make it one value first: the string "2,5" in JavaScript, the tuple (2, 5) in Python.

In the 150

5 problems of the 150 use it. Naming them gives their method away, so the list is folded.