Skip to content
Hello Python
2/7

Hashing & Sets

Topic 2 of 7, with 3 concept checks. Turning O(n^2) lookups into O(1) with the right data structure

Trade repeated scans for constant-time lookup

Remembered state

Decide which key represents previously seen information, what value must be stored, and whether lookup happens before insertion in common hashing interview patterns.

Core lesson 01

Whenever a brute-force solution has a nested loop searching for something (a complement, a duplicate, a previously-seen value), storing what you've seen so far in a dict or set turns that inner search into an O(1) average lookup, collapsing O(n^2) to O(n).

The pattern is almost always the same: iterate once, and at each step ask 'have I seen the thing I need already?' by checking a hash-backed structure built incrementally, then add the current element before moving on. This single-pass-with-memory approach is one of the most common transformations in interview problems.

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

What to remember

What's the core insight that makes hash-map problems solvable in O(n) instead of O(n^2)?

Common footguns

  • Checking membership and inserting in the wrong order for problems where the current element could pair with itself (e.g. target = 2*num) - decide deliberately whether to check before or after inserting.

Core lesson 02

Use collections.Counter whenever the problem cares about HOW MANY times something appears - anagrams, frequency thresholds, majority elements - not just whether it appears at all.

A set answers 'is x present?' A Counter answers 'how many x are there?' - necessary whenever comparing multiset structure (two strings are anagrams if their Counters are equal) or ranking by frequency (top-k). Counter also supports arithmetic (subtraction, intersection via &) convenient for these problems.

Python example
from collections import Counter

def is_anagram(s1, s2):
    return Counter(s1) == Counter(s2)

def most_common_k(nums, k):
    return [num for num, _ in Counter(nums).most_common(k)]

What to remember

When do you need a Counter/frequency dict instead of a plain set?

Common footguns

  • Using a set to check 'anagram-ness' by comparing unique characters only - misses cases with different character counts, like 'aab' vs 'abb' (same set of characters, not anagrams).

Core lesson 03

For 'group by' problems, compute a hashable signature for each item (e.g. its sorted characters for anagrams) and use it as a dict key, appending each original item to that key's list.

Grouping problems (group anagrams, group by remainder, group by pattern) all follow the same shape: define a function mapping an item to a canonical key representing its group, then build a dict from that key to a list of original items sharing it. The cleverness is entirely in choosing the right key function - the dict mechanics are always the same.

Python example
from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = ''.join(sorted(word))   # canonical signature
        groups[key].append(word)
    return list(groups.values())

What to remember

How do you use a hash map to solve 'group items by some computed key' problems?

Common footguns

  • Using an expensive or non-canonical key (e.g. an unsorted string) that doesn't actually group equivalent items together correctly.

Python lab

Browser Python lab

Runtime · idle

Python loads on your first run. Your code stays in this browser.

Best practices

  • Default to a hash map/set whenever you catch yourself writing a nested loop to check 'have I seen this before?'.
  • Use Counter for anything involving frequency, not just presence.
  • For grouping problems, spend your effort choosing the right canonical key function - the dict logic itself is always the same.
  • Remember dict/set operations are O(1) AVERAGE, not worst-case guaranteed.

References

Python Docs — collectionsNeetCode — Arrays & Hashing

Apply the concept in Interview practice

Group AnagramsmediumLeetCode #49 · O(n·k log k) time

Key a dict by the sorted-tuple of each word's letters, appending each original word to its group.

Open problem
Top K Frequent ElementsmediumLeetCode #347 · O(n log k) time

Count with Counter, then use a heap or bucket sort by frequency to get the top k.

Open problem
Valid SudokumediumLeetCode #36 · O(1) - fixed 9x9 board

Use a set per row, per column, and per 3x3 box; for each filled cell, check whether its value already exists in the corresponding row/column/box set.

Open problem
Longest Consecutive SequencemediumLeetCode #128 · O(n) time

Put all numbers in a set; only start counting a sequence from numbers whose predecessor (num-1) is NOT in the set, then count upward.

Open problem
Subarray Sum Equals KmediumLeetCode #560 · O(n) time

Track running prefix sums in a dict counting how many times each sum has occurred; at each step check if (running_sum - k) has been seen before.

Open problem

Concept checks

Q01

What's the core insight that makes hash-map problems solvable in O(n) instead of O(n^2)?

Q02

When do you need a Counter/frequency dict instead of a plain set?

Q03

How do you use a hash map to solve 'group items by some computed key' problems?