Foundational Data Structures & Algorithms

TL;DR

You'll learn the two patterns that solve a huge chunk of LeetCode's "Easy" and "Medium" array/string problems: hash maps for instant lookup, and two pointers for sorted-data scanning. You'll see when each one turns an O(n²) brute force into O(n), with real code and a worked trace. You'll also learn the bugs that make these patterns fail silently in interviews.

1. The Mental Model

A hash map trades memory for speed: you remember what you've already seen so you never search again. Two pointers trade a second loop for smart movement: instead of checking every pair, you move inward based on what you learn. Both patterns exist to kill the inner loop — that's the thing to notice every time you write nested for loops.

2. The Core Material

2.1 Hash Maps — remember, don't re-search

Photo by Brett Jordan on Pexels

A hash map (Python dict) gives you O(1) average-time lookup, insert, and delete. The brute-force instinct for "does this pair exist?" is a nested loop — O(n²). The hash map instinct is: loop once, and at each step ask "have I seen what I need already?"

Classic example: Two Sum. Given nums and target, find indices of two numbers that add up to target.

def two_sum(nums: list[int], target: int) -> list[int]:
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Why this works: at each index i, you only need to know if target - num showed up earlier. You don't need to search the rest of the array — you need to remember the past. That's the whole trick. Time: O(n). Space: O(n) for the map.

The deeper pattern behind this: frequency counting. Anytime a problem says "duplicate", "anagram", "most frequent", or "group by", reach for dict or collections.Counter.

from collections import Counter

def is_anagram(s: str, t: str) -> bool:
    return Counter(s) == Counter(t)

Counter is a dict subclass that counts hashable items for you — no manual if key in d boilerplate.

2.2 Two Pointers — move with purpose, not brute force

Photo by Andrey Matveev on Pexels

Two pointers works when your data is sorted (or can be treated that way) and you're searching for a pair, triplet, or boundary. Instead of trying every (i, j) pair — O(n²) — you place one pointer at each end and move the one that's "wrong" in a known direction.

Classic example: given a sorted array, find two numbers that sum to target.

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        current = nums[left] + nums[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1   # need a bigger sum, move left up
        else:
            right -= 1  # need a smaller sum, move right down
    return []

The logic that makes this O(n) instead of O(n²): because the array is sorted, if nums[left] + nums[right] is too small, increasing right can never help (it's already the biggest available). The only useful move is left += 1. Every step eliminates exactly one candidate permanently — that's why the pointers only ever move toward each other, never back out, giving a total of at most n steps.

2.3 Sliding Window — two pointers that both move forward

Photo by Ruben Boekeloo on Pexels

Sliding window is the same "shrink the search space" idea applied to subarrays/substrings, where both pointers move rightward over time instead of toward each other. Classic use: "longest substring without repeating characters."

def length_of_longest_substring(s: str) -> int:
    seen = set()
    left = 0
    longest = 0
    for right in range(len(s)):
        while s[right] in seen:
            seen.remove(s[left])
            left += 1
        seen.add(s[right])
        longest = max(longest, right - left + 1)
    return longest

Here right always expands the window; left only contracts it when a duplicate forces you to. Each character is added to seen once and removed at most once, so total work is O(n) even though there's a while loop inside a for loop — that nested-loop look is deceptive; amortized, it's still linear.

flowchart TD
    A["Problem: find pair/substring with a property"] --> B{"Is data sorted or sortable?"}
    B -->|Yes, pair/triplet sum| C["Two Pointers: left & right converge"]
    B -->|No, need O(1) lookup of seen values| D["Hash Map: store value->index or Counter"]
    A --> E{"Is it a contiguous subarray/substring?"}
    E -->|Yes| F["Sliding Window: left & right both move forward"]
    C --> G["O(n) time, O(1) extra space"]
    D --> H["O(n) time, O(n) extra space"]
    F --> I["O(n) time, O(k) space for window state"]

3. Worked Example

Let's combine both patterns on a real problem: 3Sum — find all unique triplets in nums that sum to zero.

Brute force is O(n³) (three nested loops). The standard fix: sort the array (O(n log n)), fix one number, then use two pointers on the rest — O(n²) total.

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    n = len(nums)

    for i in range(n - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip duplicate "anchor" values
        if nums[i] > 0:
            break  # smallest value is positive, no triplet can sum to 0

        left, right = i + 1, n - 1
        while left < right:
            total = nums[i] + nums[left] + nums[right]
            if total == 0:
                result.append([nums[i], nums[left], nums[right]])
                left += 1
                right -= 1
                while left < right and nums[left] == nums[left - 1]:
                    left += 1  # skip duplicate left values
                while left < right and nums[right] == nums[right + 1]:
                    right -= 1  # skip duplicate right values
            elif total < 0:
                left += 1
            else:
                right -= 1

    return result

Trace it on nums = [-1, 0, 1, 2, -1, -4]:
1. Sorted: [-4, -1, -1, 0, 1, 2].
2. i=0, nums[i]=-4. Pointers at left=1 (-1), right=5 (2). Sum = -4-1+2=-3 < 0 → left += 1. Sum = -4+(-1)+2=-3<0 → left+=1. Sum=-4+0+2=-2<0→left+=1. Sum=-4+1+2=-1<0→left+=1, now left==right, loop ends. No triplet with -4.
3. i=1, nums[i]=-1. left=2 (-1), right=5 (2). Sum=-1-1+2=0 → found [-1,-1,2]. Move both pointers inward, skip duplicates. Continue: left=3 (0), right=4 (1). Sum=-1+0+1=0 → found [-1,0,1].
4. i=2, nums[i]=-1, but equals nums[i-1] → skip (anti-duplicate rule).
5. i=3, nums[i]=0 > 0? No, 0 isn't >0, so continue. left=4,right=5. Sum=0+1+2=3>0→right-=1, now left==right, stop.

Result: [[-1,-1,2], [-1,0,1]] — correct, and achieved in O(n²) instead of O(n³).

4. Production Pitfalls & Best Practices

4.1 Real-World Best Practices

• Sort first when a problem mentions "pair", "triplet", or "closest sum" — it unlocks two pointers and usually beats a hash-map approach on space.
• Use collections.Counter instead of manual dict counting — fewer lines, fewer off-by-one bugs, and it supports +, -, &, | between counters directly.
• Use dict.get(key, default) or setdefault instead of if key in d: ... else: ... when you just need a fallback value — cleaner and one less branch to get wrong.
• Prefer set over list for membership tests — x in my_list is O(n); x in my_set is O(1) average. This single swap fixes a lot of "TLE" (time limit exceeded) submissions.
• When skipping duplicates in two-pointer code, always skip on the value, not the index — compare nums[left] == nums[left-1], not positions.
• Precompute what you can — if you'll query "does X exist" many times, build the hash map/set once before the main loop, not inside it.

4.2 Common Bugs & Anti-Patterns

Bug 1 — forgetting the sorted-array precondition for two pointers:

# BAD: pointers assume sorted order, but nums is unsorted
def pair_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        ...  # logic is wrong because moving pointers has no guaranteed effect

# FIXED: sort first (or use hash map if original indices matter)
def pair_sum(nums, target):
    nums = sorted(nums)
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return True
        left += 1 if s < target else -1 and (right := right - 1)

(Better: write the if/elif/else fully as shown in Section 2.2 — avoid clever one-liners in interviews.)

Bug 2 — mutating a dict while iterating over it:

# BAD: RuntimeError: dictionary changed size during iteration
for key in my_dict:
    if condition(key):
        del my_dict[key]

# FIXED: iterate over a snapshot of the keys
for key in list(my_dict.keys()):
    if condition(key):
        del my_dict[key]

Bug 3 — using mutable default values in dict.setdefault incorrectly for counting:

# BAD: overwrites instead of accumulating
counts = {}
for word in words:
    counts[word] = 1  # always resets to 1

# FIXED
counts = {}
for word in words:
    counts[word] = counts.get(word, 0) + 1

Bug 4 — sliding window that forgets to shrink, causing wrong window size:

# BAD: left never advances, window only grows (wrong for "no repeats" problems)
def length_of_longest_substring(s):
    seen = set()
    longest = 0
    for right in range(len(s)):
        seen.add(s[right])
        longest = max(longest, len(seen))
    return longest  # doesn't actually track a contiguous window

# FIXED: see Section 2.3 — shrink with a while loop whenever a duplicate appears

4.3 When to Use What (Decision Matrix)

5. Now Try It

Write group_anagrams(words: list[str]) -> list[list[str]] that groups strings which are anagrams of each other, e.g. ["eat","tea","tan","ate","nat","bat"] → [["eat","tea","ate"],["tan","nat"],["bat"]] (order within/between groups doesn't matter). Use a dict where the key is each word's sorted tuple of characters — this is the hash-map "signature" trick. Aim for O(n * k log k) where k is max word length. Test it on the example above in your Python REPL right now.

Success looks like: your function returns all three correct groups (in any order) and runs without errors on the sample input.