Common Hashing Problems

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 3 Time to complete: ~30 minutes

Two Sum
Group Anagrams
Longest Consecutive Sequence
Subarray Sum Equals K
Try It Yourself
Summary & Next Steps

1. Two Sum

Problem: Given a list of numbers and a target, return the indices of two numbers that add up to the target.

Brute force — O(n²):

def two_sum_brute(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):     # nested loop over the same list
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

Hash map — O(n):

def two_sum(nums, target):
    seen = {}                              # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:              # O(1) average lookup
            return [seen[complement], i]
        seen[num] = i
    return []
 
print(two_sum([2, 7, 11, 15], 9))     # [0, 1] → 2 + 7 == 9

Why this works: instead of checking every pair (the brute-force nested loop), you check whether the number you'd need to complete the pair has already been seen — a single pass, O(1) lookups. This is the canonical example of hashing collapsing O(n²) to O(n), and it's worth internalizing as a template: "for each item, check whether its complement/partner has already been seen" solves an enormous number of array problems.

2. Group Anagrams

Problem: Given a list of strings, group the ones that are anagrams of each other.

def group_anagrams(strs):
    groups = {}
    for s in strs:
        key = "".join(sorted(s))            # canonical form: same for all anagrams
        groups.setdefault(key, []).append(s)
    return list(groups.values())
 
print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

Complexity: Sorting each string of length k costs O(k log k), done for all n strings → O(n × k log k) time, O(n × k) space. The key insight is using the sorted string as a hash key — any two anagrams produce the identical sorted string, so they land in the same bucket. dict.setdefault(key, []) avoids a manual if key not in groups check.

3. Longest Consecutive Sequence

Problem: Given an unsorted list of integers, find the length of the longest run of consecutive integers (e.g., [100, 4, 200, 1, 3, 2] → the run 1, 2, 3, 4 has length 4).

A sort-based approach is O(n log n). The set-based approach is O(n):

def longest_consecutive(nums):
    num_set = set(nums)          # O(n) — enables O(1) membership checks
    longest = 0
 
    for num in num_set:
        if num - 1 not in num_set:      # only start counting from the BEGINNING of a run
            length = 1
            while num + length in num_set:
                length += 1
            longest = max(longest, length)
 
    return longest
 
print(longest_consecutive([100, 4, 200, 1, 3, 2]))    # 4

Why this is O(n), not O(n²): it looks like nested loops (for + while), but the while loop only ever runs for numbers that are the start of a run (num - 1 not in num_set). Every number is visited by the inner while loop at most once across the entire function, so the total work across all iterations is O(n), not O(n²) — the same kind of amortized-cost reasoning worth double-checking with Module 1 Chapter 6's checklist whenever a loop's total iterations aren't obvious at a glance.

4. Subarray Sum Equals K

Problem: Given a list of integers and a target k, count how many contiguous subarrays sum to exactly k.

def subarray_sum(nums, k):
    count = 0
    prefix_sum = 0
    sum_counts = {0: 1}          # empty prefix (sum 0) has occurred once
 
    for num in nums:
        prefix_sum += num
        # if (prefix_sum - k) has occurred before, the subarray between
        # that point and here sums to exactly k
        count += sum_counts.get(prefix_sum - k, 0)
        sum_counts[prefix_sum] = sum_counts.get(prefix_sum, 0) + 1
 
    return count
 
print(subarray_sum([1, 1, 1], 2))     # 2 → [1,1] (indices 0-1) and [1,1] (indices 1-2)

Why this works: if the running total (prefix_sum) up to index j minus the running total up to some earlier index i equals k, then the elements between i and j sum to k. Instead of recomputing sums for every pair of indices (O(n²)), you hash each prefix sum as you compute it once, and look up how many times prefix_sum - k has occurred so far — O(n) time, O(n) space.

5. Try It Yourself

# (a) Contains Duplicate — return True if any value appears at least twice
def contains_duplicate(nums):
    ...
 
# (b) Intersection of Two Arrays — return the unique elements common to both
def intersection(nums1, nums2):
    ...

Answers (click to expand)

def contains_duplicate(nums):
    seen = set()
    for num in nums:
        if num in seen:          # O(1) average
            return True
        seen.add(num)
    return False
    # O(n) time, O(n) space
 
def intersection(nums1, nums2):
    return list(set(nums1) & set(nums2))
    # O(n + m) time, O(n + m) space — Chapter 2's set intersection operator

6. Summary & Next Steps

Key Takeaways

"For each item, check whether its complement has already been seen" (Two Sum) is a template that generalizes to many array/hashing problems.
Sorting a string (or any collection) to produce a canonical form is a common way to turn "are these equivalent under reordering" into a hashable key (Group Anagrams).
A while loop nested inside a for loop isn't automatically O(n²) — if the total work across all iterations of the outer loop is bounded by n, the whole thing is O(n) (Longest Consecutive Sequence).
The prefix-sum + hash-map combination turns "count subarrays with property X" problems from O(n²) into O(n).

Concept Check

Why does the Two Sum hash-map solution only need one pass over the list?
Why is longest_consecutive's nested loop structure still O(n) overall?
In Subarray Sum Equals K, what does sum_counts.get(prefix_sum - k, 0) represent?

Next Module

→ Module 9: Graphs

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index