Why does a set make 'contains duplicate' O(n) instead of O(n²)?

Each membership check and insert in a hash set is O(1) on average, so one pass over n items costs O(n). The nested-loop version compares every pair, which is O(n²).

In Two Sum with a map, why check for the partner before storing the current number?

So a number can't pair with itself. If you stored it first, target = 2 × number would match the same index twice.

What does the hash-map pattern cost in exchange for its speed?

Extra memory: in the worst case the set or map holds every element, so O(n) extra space.

Hash Map: Remember What You've Seen — DSA Patterns Made Simple

The problem

Contains Duplicate: given a list of numbers, return whether any value appears twice.

The simple version compares every pair: O(n²). With 100,000 numbers that's 5 billion comparisons. Yet a person would just keep a mental list of numbers already seen and stop at the first repeat.

How to spot it

Reach for a set or map when the problem says or implies:

"Has this appeared before?" (duplicates, first repeat)
"Find a pair that adds up to / matches…" (the partner can be looked up)
"First unique / non-repeating…"
Your simple version has an inner loop that searches for something.

The idea

Walk the list once. For each item, ask your memory a question ("have I seen this?", "have I seen its partner?") and then add the item to memory. A set answers "seen or not?"; a map (dictionary) also remembers something about it, like its position or a count. Both answer in O(1) on average.

You trade a little memory (O(n) extra space) for a big speed-up (O(n²) → O(n)).

The template

def solve(items):
    seen = set()              # or {} when you need to remember a position/count
    for item in items:
        if item in seen:      # or: if partner(item) in seen
            return True       # found what we were looking for
        seen.add(item)
    return False

function solve(items) {
  const seen = new Set();     // or new Map() when you need a position/count
  for (const item of items) {
    if (seen.has(item)) return true;   // or: seen.has(partner(item))
    seen.add(item);
  }
  return false;
}

The order matters: check first, then add. Adding first would make every item "seen" when you check it.

Worked example

Two classic uses: a set for duplicates, and a map for Two Sum (the map remembers each number's position so we can return it).

Contains Duplicate and Two SumTry it yourself

def contains_duplicate(nums):
    seen = set()
    for n in nums:
        if n in seen:
            return True
        seen.add(n)
    return False


def two_sum(nums, target):
    position = {}                      # number -> index where we saw it
    for i, n in enumerate(nums):
        if target - n in position:     # is the partner already in memory?
            return [position[target - n], i]
        position[n] = i
    return []


print("duplicate in [1, 2, 3, 1]:", "yes" if contains_duplicate([1, 2, 3, 1]) else "no")
print("duplicate in [1, 2, 3, 4]:", "yes" if contains_duplicate([1, 2, 3, 4]) else "no")
print("two sum [2, 7, 11, 15], 9 ->", two_sum([2, 7, 11, 15], 9))
print("two sum [3, 2, 4], 6 ->", two_sum([3, 2, 4], 6))

Output

duplicate in [1, 2, 3, 1]: yes
duplicate in [1, 2, 3, 4]: no
two sum [2, 7, 11, 15], 9 -> [0, 1]
two sum [3, 2, 4], 6 -> [1, 2]

Contains Duplicate and Two SumTry it yourself

function containsDuplicate(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

function twoSum(nums, target) {
  const position = new Map();          // number -> index where we saw it
  for (let i = 0; i < nums.length; i++) {
    const partner = target - nums[i];
    if (position.has(partner)) return [position.get(partner), i];
    position.set(nums[i], i);
  }
  return [];
}

const show = (v) => JSON.stringify(v).replaceAll(",", ", ");
console.log("duplicate in [1, 2, 3, 1]:", containsDuplicate([1, 2, 3, 1]) ? "yes" : "no");
console.log("duplicate in [1, 2, 3, 4]:", containsDuplicate([1, 2, 3, 4]) ? "yes" : "no");
console.log("two sum [2, 7, 11, 15], 9 ->", show(twoSum([2, 7, 11, 15], 9)));
console.log("two sum [3, 2, 4], 6 ->", show(twoSum([3, 2, 4], 6)));

Output

duplicate in [1, 2, 3, 1]: yes
duplicate in [1, 2, 3, 4]: no
two sum [2, 7, 11, 15], 9 -> [0, 1]
two sum [3, 2, 4], 6 -> [1, 2]

Common mistakes

Adding before checking. In Two Sum with [3, 3] and target 6 this still works, but with target 6 and [3] you'd "find" 3 + 3 using the same element twice.
Using a list as memory. x in list / list.includes(x) is O(n), so the whole thing becomes O(n²) again.
JavaScript objects as maps for numbers. Object keys become strings; prefer Map and Set.
Forgetting the space cost. Mention "O(n) extra space" when you explain your answer.

Practice

Solve these in the browser, in order:

Contains Duplicate (easy)
Two Sum (easy)
Longest Consecutive Sequence (medium): put everything in a set, then only start counting from numbers whose n - 1 is missing.

Key points

Pattern: one pass, ask memory a question, then remember the current item.
Set = "seen it?"; map = "seen it, and here's what I know about it".
Turns nested-loop searches (O(n²)) into O(n) time with O(n) space.
Check first, then add.