Set Pattern

Why this pattern matters for LeetCode

Beginners write nested loops to detect duplicates: for each element, scan everything before it. That is O(n²) and times out on large inputs. The Set pattern is O(n): loop once, mark each value as you see it, and check instantly whether you've seen it before. The key insight is that Set membership checks don't get slower as the Set grows — they're always O(1) regardless of how many items you've stored.

What the Set pattern is

A Set remembers what you've seen and answers 'have I seen this before?' in constant time — no matter how many things it's already tracking. Every time you encounter a value, check if it's in the Set. If yes, you've found a duplicate (or a cycle, or a repeated state). If no, add it and move on. The difference from an array: .has() on a Set is O(1); .includes() on an array is O(n).

Reach for Set when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Set

• ✓Detecting any duplicate in a list (Contains Duplicate)
• ✓Tracking visited nodes in a graph or linked list to detect cycles
• ✓Building a unique collection from a list with duplicates
• ✓Checking if an element from one array exists in another array in O(1)
• ✓Detecting a repeated state in a simulation (Happy Number cycle detection)

When NOT to use Set

• ✕You need to store data alongside each element — use a Map instead
• ✕You need to count how many times each element appears — use a Frequency Map
• ✕You need to maintain insertion order and retrieve by index — use an array
• ✕The data has a small integer range — a boolean array may be more cache-friendly

Better alternative: In those cases, a Hash Map or Frequency Map gives you the same O(1) lookup plus the extra data you need.

JavaScript code template

Contains Duplicate — O(n) time, O(n) space

const seen = new Set();

for (const num of nums) {
  if (seen.has(num)) {
    return true;    // already on the clipboard — duplicate found
  }
  seen.add(num);   // first time seeing this number — mark it
}

return false;

One pass through the array. For each number, check the Set first. If it's there, return true immediately. If not, add it and continue. No inner loop, no re-scanning. The Set check is O(1) every single time, so the whole loop is O(n).

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Create an empty Set to track what you've seen.
2. 2Loop through the input one element at a time.
3. 3Before adding anything, call .has() to check if the current value is already in the Set.
4. 4If .has() returns true, you've found a duplicate — return or record the result immediately.
5. 5If .has() returns false, call .add() to mark this value as seen.
6. 6At the end of the loop, return the default result (false for no duplicate found).

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Contains Duplicate

  Classic Set problem: check if any number already appeared as you scan through the array.

  Free→
• Longest Consecutive Sequence

  Load all numbers into a Set, then try to start sequences only from numbers with no predecessor.

  Premium→
• Happy Number

  Detect a cycle in the digit-sum sequence — if a result repeats, you're in a loop.

  Premium→
• Linked List Cycle

  Track visited nodes in a Set — if you see the same node twice, there's a cycle.

  Premium→

Coming soon

• Valid Sudoku

  Track seen values per row, column, and box simultaneously using Sets.

  Coming soon
• Intersection of Two Arrays

  Convert one array to a Set, then check each element of the other against it.

  Coming soon

Common mistakes beginners make

• ✕Using an array instead of a Set: arr.includes(num) scans the whole array every time, which is exactly the O(n²) problem you started with.
• ✕Forgetting to call .add() after checking — if you never put things into the Set, it's always empty and .has() always returns false.
• ✕Using a Set when you actually need counts — if the problem asks 'how many times does X appear,' you need a Frequency Map.
• ✕Reaching for a Map out of habit — a Map stores a key and a value. If all you need to know is whether something was seen, a Set is simpler.

Set vs Hash Map vs Frequency Map

Choose the right tool for the job.

Time and space complexity

You visit each element exactly once (O(n) time). Each .has() and .add() call is O(1) average. In the worst case you store every element in the Set (O(n) space). If all elements are unique, you store all n of them before returning false.

Frequently asked questions

When should I use a Set instead of a Map?

Use a Set when you only care whether something has been seen — you don't need to retrieve any data about it. Use a Map when you also need to store something alongside each key, like an index or a count.

Why does Contains Duplicate use a Set instead of sorting the array?

Sorting works and is O(n log n). A Set is O(n) — strictly faster. Sorting also modifies the array, which might matter. The Set approach gives you an early exit the moment you find a duplicate, rather than waiting until after a full sort.

Is Set.has() really O(1)?

Yes, on average. JavaScript Sets use hash tables internally, so membership checks are O(1) average case — the same as Map.has(). This is fundamentally different from Array.includes(), which scans linearly.

What's the difference between a Set and a Frequency Map?

A Set tells you a value appeared at least once. A Frequency Map tells you exactly how many times it appeared. If the problem says 'does a duplicate exist,' use a Set. If it says 'how many times does each value appear,' use a Frequency Map (a plain object or Map with counts as values).