Hashing — DSA Mastery

Two Sum — HashMap Approach

For each number, check if complement (target - num) is in the map. Step through to see how the hashmap builds up.

Target:

HASHMAP STATE (seen = {value: index})

Press Start to begin.

Frequency Counter

Type a word and see character frequencies counted with Counter.

Why HashMap? — The Core Trade-off

The Trade-off

Spend O(n) extra space to avoid O(n) time per lookup. In most interview problems, space is cheap — time matters.

Operation	dict / set	list
Lookup (`x in ...`)	O(1)	O(n)
Insert	O(1)	O(1) end / O(n) middle
Delete	O(1)	O(n)

Pro Tip

If you find yourself writing x in arr inside a loop, replace arr with a set. This drops O(n²) to O(n).

3 Hashing Patterns

Complement Lookup (Two Sum)

For each num, store it. Before storing, check if (target - num) exists. Check FIRST, then add — prevents pairing a number with itself.

Frequency Count

Use Counter or defaultdict(int) to count occurrences. Check if two strings are anagrams: their Counters must be equal.

Set for Existence

Use set when you only need "does this exist?" not how many times. Smaller memory than dict, same O(1) lookup.

Two Sum — Check THEN Add

def two_sum(arr, target):
    seen = {}  # value → index
    for i, num in enumerate(arr):
        needed = target - num
        if needed in seen:        # O(1) lookup
            return [seen[needed], i]
        seen[num] = i  # add AFTER checking!
    return []

Classic Bug

If you add to seen BEFORE checking, a number might match with itself. Always check first, then add.

Frequency Patterns

from collections import Counter, defaultdict

# Anagram check — O(n)
def is_anagram(s, t):
    return Counter(s) == Counter(t)

# Group anagrams
def group_anagrams(words):
    groups = defaultdict(list)
    for word in words:
        key = "".join(sorted(word))
        groups[key].append(word)
    return list(groups.values())

# Longest Consecutive Sequence — O(n)
def longest_consecutive(nums):
    s = set(nums)
    best = 0
    for n in s:
        if n - 1 not in s:  # start of sequence
            length = 1
            while n + length in s: length += 1
            best = max(best, length)
    return best

LeetCode Problems

EasyTwo SumComplement lookup
EasyValid AnagramCounter comparison
EasyContains DuplicateSet existence
MediumGroup AnagramsSorted key → group
MediumLongest Consecutive SequenceSet + start detection
MediumSubarray Sum Equals KPrefix sum + HashMap
HardMinimum Window SubstringSliding window + Counter

Hashing / HashMap

Why HashMap? — The Core Trade-off

3 Hashing Patterns

Two Sum — Check THEN Add

Frequency Patterns

LeetCode Problems