Crack Interview Problems with Hash Maps

Solve 4 classic interview patterns using Python hash maps and sets.

Introduction

30 Second Summary

Ever lost your keys and had to check every pocket, every drawer, every surface in your home? That frantic one-by-one search is exactly how inefficient code works when it uses nested loops to find things.

In this project, you will build four Python solutions that replace slow, brute-force searching with hash maps. These are the same patterns that appear in roughly 30% of easy and medium coding interview problems.

What You'll Build

A collection of Python solution files, each implementing a different hash map interview pattern from scratch with brute-force comparisons, optimized solutions, and test cases you run to verify correctness.

By the end of this project, you'll have:

  • Four solved problems spanning duplicate detection, frequency counting, complement lookup, and grouping by key.
  • A mental model for recognizing when a hash map replaces a nested loop, turning O(n^2) into O(n).
  • Reusable Python syntax drilled in (dict, set, enumerate, Counter, defaultdict) that transfers directly to interview whiteboards.
  • Secret Mission: Tackle the prefix sum + hash map pattern to count subarrays with a target sum.

Are there any prerequisites?

You need basic Python familiarity: variables, loops, functions, and strings. No prior algorithm or interview prep experience is needed.

Before We Start

Before writing any algorithm code, you need a workspace where you can write and run Python files.

In this step, you'll create a project folder, confirm Python is working, and run your first test file to make sure everything is connected.

In this step, get ready to:
  • Create a project folder on your Desktop.
  • Verify Python 3 runs correctly.
  • Create and run your first Python file in Cursor.
Create the project folder and verify Python works

You need a dedicated folder to hold your solution files and a working Python installation to run them.

  • Press Cmd+Space (macOS) or the Windows key (Windows) to open your search bar.
  • Type Terminal and press Enter to open it.
  • Move to your Desktop by running this command:
cd ~/Desktop
  • Create your project folder and move into it by running these commands:
mkdir hashmap-patterns
cd hashmap-patterns
  • Confirm the folder was created by running:
ls ~/Desktop

You should see hashmap-patterns in the output.

  • Verify Python is working by running:
python3 --version

You should see a version number printed, like Python 3.11.x or similar.

Not seeing a version number?

Make sure you're typing python3 (with the 3), not just python. On some systems, python without the 3 either points to an older version or doesn't exist.

If you see command not found, Python 3 may not be installed. Visit the official Python downloads page to install it.

Still stuck? Help me troubleshoot my Python 3 installation

  • Open this folder in Cursor by running:
cursor .

Cursor opens with the hashmap-patterns folder loaded in the Explorer sidebar on the left.

Cursor didn't open?

If cursor is not recognized as a command, open Cursor manually. Press Cmd+Space (macOS) or the Windows key (Windows), type Cursor, and press Enter.

Then click File in the top menu bar, click Open Folder, and select the hashmap-patterns folder on your Desktop.

Need more help? Help me open my project folder in Cursor

  • Create your first file. In Cursor's Explorer sidebar on the left, hover over the HASHMAP-PATTERNS heading.
  • Click the new file icon (a page with a small +).
  • Type foundations.py and press Enter.

The file opens in the editor pane, ready for you to write code.

Write and run a smoke test

A smoke test is a quick check that confirms your file can actually run. If this one line prints successfully, your entire setup is working.

  • In foundations.py, type the following code:
print("Hello, hashmap-patterns!")

What does this code do?

This single line calls Python's built-in print() function to output text to the terminal. If you see the message printed, it proves Python can find and execute your file.

  • Save foundations.py by pressing Cmd+S (macOS) or Ctrl+S (Windows).
  • Open the integrated terminal in Cursor by pressing Ctrl+` (backtick key, same shortcut on both macOS and Windows).
  • Run the file with this command:
python3 foundations.py

You should see Hello, hashmap-patterns! printed in the terminal.

Seeing an error instead?

If you see No such file or directory, make sure your terminal is inside the hashmap-patterns folder. Run pwd to check your current location. If you're in the wrong place, run cd ~/Desktop/hashmap-patterns first.

If you see a SyntaxError, double-check that your quotes match. The opening and closing quotes around the string must be the same type (both double quotes or both single quotes).

Need help? Help me debug why python3 foundations.py isn't working

Understand the project structure

Now that your workspace is set up, here's how the project is organized.

How are the files structured?

You'll create one file per hash map pattern: foundations.py, frequency.py, complement.py, and grouping.py.

Each file follows the same template: a problem description at the top, a brute-force solution, the optimized hash map solution, and test cases you run to verify correctness.

✔️ Awesome, I've got everything!

Great. Double check that you've saved foundations.py and that Hello, hashmap-patterns! printed in your terminal.

ⓧ I'd like to double check the full code

Here's what foundations.py should look like at this point:

print("Hello, hashmap-patterns!")

Your workspace is ready. Next up, you'll write your first real algorithm solution using a set to detect duplicates in a list.

Set Up Your Project Files

Your smoke test confirmed Python runs correctly in your project folder. Now it is time to set up the actual file structure you will use throughout this project.

Each hash map pattern gets its own dedicated file. This keeps solutions isolated so you can focus on one technique at a time, just like you would tackle one problem at a time in a real interview.

In this step, get ready to:
  • Create four pattern files, one for each hash map technique.
  • Understand the template structure each file will follow.
Create one file per pattern

You will build four files total. Each one focuses on a single hash map interview pattern.

  • foundations.py — Duplicate detection using sets.
  • frequency.py — Anagram checking using frequency counting.
  • complement.py — Pair finding using complement lookup.
  • grouping.py — Word categorization using grouping by key.

First, replace the smoke test in foundations.py with its pattern label. The smoke test did its job. Now the file needs to reflect its real purpose.

  • In Cursor, click on foundations.py in the Explorer sidebar to open it.
  • Select all the existing content by pressing Cmd+A (macOS) or Ctrl+A (Windows).
  • Replace it by typing this comment:
# Pattern: Duplicate Detection using Sets
  • Save the file with Cmd+S (macOS) or Ctrl+S (Windows).

Now create the remaining three pattern files. Each gets a placeholder comment labeling its pattern.

  • In the Explorer sidebar, hover over the hashmap-patterns folder name and click the New File icon (a page with a + symbol).
  • Type frequency.py and press Enter.
  • Type this comment into the new file:
# Pattern: Frequency Counting - Anagram Check
  • Save frequency.py.
  • Repeat the same process to create complement.py with this comment:
# Pattern: Complement Lookup - Pair Sum
  • Save complement.py.
  • Create one more file called grouping.py with this comment:
# Pattern: Grouping by Key - Group Anagrams
  • Save grouping.py.
  • Confirm all four files exist by running this command in your Terminal:
ls

You should see complement.py, foundations.py, frequency.py, and grouping.py listed in the output.

Missing a file?

Check the Explorer sidebar in Cursor. If a file is missing, hover over the folder name and click the New File icon to create it. Make sure the filename ends in .py with no extra spaces.

Help me check my project files are set up correctly.

Understand the solution template

Every file you build in this project follows the same four-part template. This structure mirrors how you would present a solution in a real interview.

  • Problem docstring at the top. This describes the problem, gives examples, and states the time/space complexity.
  • Brute-force solution first. This is the naive approach that works but is slow.
  • Optimized hash map solution second. This replaces the brute-force inner loop with an O(1) lookup.
  • Test cases at the bottom. These prove your solution works by printing results you can verify.

Why write the brute-force solution too?

Interviewers often ask you to start with the obvious approach and then improve it. Writing both solutions trains you to explain the performance jump from O(n²) to O(n).

It also gives you a fallback. If you blank on the optimized version under pressure, the brute-force approach still demonstrates problem-solving ability.

✔️ Awesome, I've got everything!

Great. Double check you have saved all four files.

⨯ I'd like to double check the full code

Here is what each file should contain at this point:

# Pattern: Duplicate Detection using Sets
# Pattern: Frequency Counting - Anagram Check
# Pattern: Complement Lookup - Pair Sum
# Pattern: Grouping by Key - Group Anagrams

Your project structure is locked in. Next up, you will fill foundations.py with your first real solution and learn how a simple set turns an O(n²) problem into an O(n) one.

Detect Duplicates with Hash Sets

Your project folder is ready and Python is confirmed working. Now it's time to write your first algorithm solution.

The most common pattern in hash map interview problems is using a set for fast membership checking. In this step, you'll solve the classic "contains duplicate" problem two ways: first with brute force, then with a hash set that cuts the time complexity from O(n²) to O(n).

In this step, get ready to:
  • Learn how Python dicts and sets provide O(1) lookups.
  • Implement a brute-force duplicate detector with nested loops.
  • Implement an optimized solution using a hash set.
Learn the core syntax: dict and set

Before writing any solution, you need to understand the two data structures that make hash map patterns work in Python.

A Python dict stores key-value pairs. You create one with {}, access values with d[key], and safely access with d.get(key, default) to avoid errors on missing keys.

A Python set stores unique values with no duplicates. You create one with set(), add elements with .add(), and check if something exists with the in keyword.

Why are sets and dicts faster than lists?

Using in on a set or dict is O(1) on average. That means checking membership takes the same amount of time whether you have 10 items or 10 million.

Using in on a list is O(n). Python has to scan every element one by one. This difference is the key insight behind every pattern in this project.

Implement the brute-force solution

The problem: given a list of integers, return True if any value appears at least twice. Return False if every element is distinct.

The brute-force approach compares every possible pair of elements using nested loops. For each element, you scan every other element to see if there's a match. This works, but it's O(n²) because doubling the input quadruples the comparisons.

  • In Cursor, open foundations.py from the sidebar.
  • Select all the existing content and replace it with the following code:
"""
Hash Map Foundations: Detecting Duplicates
==========================================
Problem: Given a list of integers, return True if any value appears
at least twice in the list, and False if every element is distinct.

Example:
    has_duplicate([1, 2, 3, 1]) -> True
    has_duplicate([1, 2, 3, 4]) -> False

Pattern: Use a HashSet for O(1) membership checks.
Time: O(n) | Space: O(n)
"""


def has_duplicate_brute(nums):
    """Brute force: compare every pair. O(n^2) time, O(1) space."""
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False

What does this code do?

The docstring at the top documents the problem, examples, and the target complexity. This is a habit worth building for interviews because it shows structured thinking.

  • for i in range(len(nums)) picks each element as the first item in a pair.
  • for j in range(i + 1, len(nums)) picks every element after i as the second item, avoiding repeat comparisons.
  • If any pair matches, return True immediately. If no pair ever matches, fall through to return False.
  • Save foundations.py.
  • Run the file to confirm there are no syntax errors by running this command in your terminal:
python3 foundations.py

You should see no output and no errors. The function is defined but nothing calls it yet.

Seeing a SyntaxError?

  • Check that the triple-quoted docstring has matching """ at the start and end. A missing quote breaks everything below it.
  • Make sure the for and if lines inside the function use consistent indentation (4 spaces per level).
  • Confirm the old placeholder comment is fully replaced. Leftover text can cause unexpected errors.

Why is my foundations.py showing a SyntaxError when I run it?

Implement the hash map solution

The brute-force solution works, but it's slow. For every element, it scans the entire rest of the list. A hash set eliminates that inner loop entirely.

The logic: as you walk through the list, check if the current number is already in your seen set. If yes, you found a duplicate. If no, add it to the set and move on. One pass through the list, one O(1) lookup per element.

  • Add the following code below has_duplicate_brute in foundations.py:

def has_duplicate(nums):
    """Optimal: use a set for O(1) lookups. O(n) time, O(n) space."""
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False


# Test cases
print("=== Duplicate Detection ===")
print(has_duplicate([1, 2, 3, 1]))   # True
print(has_duplicate([1, 2, 3, 4]))   # False
print(has_duplicate([]))              # False
print(has_duplicate([1]))             # False
print(has_duplicate([1, 1]))          # True

What does this code do?

  • seen = set() creates an empty set to track numbers you've already visited.
  • if num in seen checks membership in O(1) time. This replaces the entire inner loop from the brute-force version.
  • seen.add(num) records the current number so future iterations can find it.
  • The test cases call has_duplicate with various inputs (duplicates, no duplicates, empty list, single element) so you can verify correctness.

Why is this O(n) instead of O(n²)?

The brute-force version has a loop inside a loop. For each of n elements, it checks up to n other elements. That's n × n = O(n²) total work.

The set version does one pass through the list. Each in check and each .add() is O(1). So n elements × O(1) per element = O(n) total. The tradeoff is space: you store up to n items in the set.

  • Save foundations.py.
  • Run the tests by running this command in your terminal:
python3 foundations.py

You should see this output:

=== Duplicate Detection ===
True
False
False
False
True

Every result matches the expected comment next to each test case. Your first interview pattern is working.

Output doesn't match?

  • If you see None in the output, check that both return True and return False are present inside the function. A missing return means Python returns None by default.
  • If you see a NameError for has_duplicate, make sure the function definition appears above the test cases that call it.
  • Verify that seen.add(num) is inside the for loop (indented one level in) and not inside the if block.

My has_duplicate function is returning wrong results. Help me debug it.

✔️ Awesome, I've got everything!

Great. Double check you've saved foundations.py and that all five test outputs match.

ⓧ I'd like to double check the full code

Here's the complete foundations.py file. Make sure yours matches exactly:

"""
Hash Map Foundations: Detecting Duplicates
==========================================
Problem: Given a list of integers, return True if any value appears
at least twice in the list, and False if every element is distinct.

Example:
    has_duplicate([1, 2, 3, 1]) -> True
    has_duplicate([1, 2, 3, 4]) -> False

Pattern: Use a HashSet for O(1) membership checks.
Time: O(n) | Space: O(n)
"""


def has_duplicate_brute(nums):
    """Brute force: compare every pair. O(n^2) time, O(1) space."""
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] == nums[j]:
                return True
    return False


def has_duplicate(nums):
    """Optimal: use a set for O(1) lookups. O(n) time, O(n) space."""
    seen = set()
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False


# Test cases
print("=== Duplicate Detection ===")
print(has_duplicate([1, 2, 3, 1]))   # True
print(has_duplicate([1, 2, 3, 4]))   # False
print(has_duplicate([]))              # False
print(has_duplicate([1]))             # False
print(has_duplicate([1, 1]))          # True

You've just implemented the foundational hash map pattern: replacing a nested loop with an O(1) set lookup. Next up, you'll apply this same principle to character frequency counting and solve the classic anagram problem.

Count Character Frequencies for Anagram Checks

Your duplicate detection solution in foundations.py proved the core insight: a hash-based data structure turns O(n) scans into O(1) lookups. Now you will apply that same principle to a new problem shape: comparing character frequencies between two strings.

Frequency counting is one of the most common interview patterns. The challenge is simple to state ("are these two strings anagrams?") but brute-force approaches fall apart once you think about all possible character orderings. A dictionary solves this elegantly by tallying characters in a single pass.

In this step, get ready to:
  • Learn the dict.get() counting pattern and Counter shortcut.
  • Implement a manual frequency counter that detects anagrams.
  • Implement the one-line Counter version and verify both solutions pass test cases.
Learn the frequency counting tools

Before writing the anagram solution, you need three Python tools in your toolkit.

What is dict.get()?

The dict.get(key, default) method returns the value for a key if it exists, or returns default instead of raising a KeyError. This makes it perfect for counting because you can write count.get(char, 0) + 1 to safely increment from zero.

Without .get(), you would need an if key in dict check before every access. The .get() pattern collapses that into one clean line.

What is Counter?

Python's collections.Counter is a dict subclass built specifically for counting hashable objects. Passing any iterable (like a string) to Counter(iterable) produces a dictionary of element counts.

Two Counters can be compared directly with == to check if their frequencies match. This turns an entire anagram check into a single expression.

What does all() do?

The all(iterable) built-in returns True if every element in the iterable is truthy. You will use it to verify that every character count in your dictionary has been decremented back to zero.

Implement manual frequency counting

The problem: given two strings s and t, return True if t is an anagram of s (same characters, same counts). Your first solution builds the frequency dictionary by hand so you understand what happens under the hood.

  • Open frequency.py in Cursor.
  • Select all existing content and replace it with the following code:
"""
Pattern 1 - Frequency Counting: Valid Anagram
=============================================
Problem: Given two strings s and t, return True if t is an anagram of s
(uses the exact same characters, same number of times), and False otherwise.

Example:
    is_anagram("listen", "silent") -> True
    is_anagram("hello", "world") -> False

Pattern: Count character frequencies and compare.
Time: O(n) | Space: O(1) since alphabet is fixed at 26 letters
"""
from collections import Counter


def is_anagram_manual(s, t):
    """Using a dictionary to count characters manually."""
    if len(s) != len(t):
        return False

    count = {}
    for char in s:
        count[char] = count.get(char, 0) + 1
    for char in t:
        count[char] = count.get(char, 0) - 1

    return all(v == 0 for v in count.values())

What does this code do?

The early exit if len(s) != len(t): return False catches the obvious non-anagram case immediately. If the strings are different lengths, they cannot possibly be anagrams.

The first loop builds a frequency count for every character in s. The second loop decrements counts for each character in t. If the strings are anagrams, every count ends at exactly zero.

The all(v == 0 for v in count.values()) expression checks that every single count is zero in one pass. If any character appeared more in one string than the other, its count would be non-zero and all() returns False.

  • Save frequency.py.

Seeing a syntax error?

Make sure the from collections import Counter line sits between the closing """ of the docstring and the first def line.

Check that the return all(v == 0 for v in count.values()) line is indented inside the function, not at the top level.

help me fix a syntax error in my frequency counting function

Implement the Counter shortcut and run tests

The manual approach shows interviewers you understand the mechanics. Python's Counter class does the same work in a single expression, which shows Python fluency. Knowing both gives you flexibility during interviews.

  • Add the following code below your is_anagram_manual function in frequency.py:

def is_anagram(s, t):
    """Using collections.Counter for concise frequency counting."""
    return Counter(s) == Counter(t)


# Test cases
print("=== Anagram Check (Manual) ===")
print(is_anagram_manual("listen", "silent"))   # True
print(is_anagram_manual("hello", "world"))     # False
print(is_anagram_manual("anagram", "nagaram")) # True
print(is_anagram_manual("rat", "car"))         # False

print("\n=== Anagram Check (Counter) ===")
print(is_anagram("listen", "silent"))   # True
print(is_anagram("hello", "world"))     # False
print(is_anagram("anagram", "nagaram")) # True
print(is_anagram("rat", "car"))         # False

What does this code do?

The is_anagram function compares Counter(s) == Counter(t) directly. Counter builds the frequency dictionary for you, and the == comparison checks that both dictionaries have identical keys and values.

The test cases exercise both solutions against the same inputs. True anagrams like "listen"/"silent" should return True. Non-anagrams like "hello"/"world" should return False.

When should I use which approach in interviews?

Use the manual dict.get() approach when the interviewer asks you to implement frequency counting from scratch, or when the problem requires modifying counts in a specific order.

Use Counter when the interviewer values concise Python solutions, or when frequency counting is just one step in a larger problem. Showing both demonstrates that you understand the mechanics AND know your standard library.

  • Save frequency.py.
  • Run your tests by entering this command in the terminal:
python3 frequency.py
  • You should see both test sections print with True/False values matching the comments.

What should I see?

Your terminal output should show two sections: "=== Anagram Check (Manual) ===" printing True, False, True, False, followed by "=== Anagram Check (Counter) ===" printing the same True, False, True, False pattern. Both solutions produce identical results because they solve the same problem with different tools.

Getting unexpected False values?

Check that your first loop uses + 1 and your second loop uses - 1. Swapping these produces the wrong result for every test case.

Make sure the from collections import Counter line is at the top of the file, not inside a function.

help me debug my anagram function

✔️ Awesome, I've got everything!

Great. Make sure you have saved frequency.py and confirmed both test sections print correctly.

ⓧ I'd like to double check the full code

Here is the complete frequency.py for comparison:

"""
Pattern 1 - Frequency Counting: Valid Anagram
=============================================
Problem: Given two strings s and t, return True if t is an anagram of s
(uses the exact same characters, same number of times), and False otherwise.

Example:
    is_anagram("listen", "silent") -> True
    is_anagram("hello", "world") -> False

Pattern: Count character frequencies and compare.
Time: O(n) | Space: O(1) since alphabet is fixed at 26 letters
"""
from collections import Counter


def is_anagram_manual(s, t):
    """Using a dictionary to count characters manually."""
    if len(s) != len(t):
        return False

    count = {}
    for char in s:
        count[char] = count.get(char, 0) + 1
    for char in t:
        count[char] = count.get(char, 0) - 1

    return all(v == 0 for v in count.values())


def is_anagram(s, t):
    """Using collections.Counter for concise frequency counting."""
    return Counter(s) == Counter(t)


# Test cases
print("=== Anagram Check (Manual) ===")
print(is_anagram_manual("listen", "silent"))   # True
print(is_anagram_manual("hello", "world"))     # False
print(is_anagram_manual("anagram", "nagaram")) # True
print(is_anagram_manual("rat", "car"))         # False

print("\n=== Anagram Check (Counter) ===")
print(is_anagram("listen", "silent"))   # True
print(is_anagram("hello", "world"))     # False
print(is_anagram("anagram", "nagaram")) # True
print(is_anagram("rat", "car"))         # False

You now have two frequency counting approaches locked in. Next up, you will tackle the complement lookup pattern, where a single hash map replaces the classic nested-loop pair search.

Find Pair Sums with Complement Lookup

Your frequency counting skills are locked in. You can now compare character distributions across strings in O(n) time.

Now you are tackling one of the most famous interview questions of all time: finding two numbers in a list that add up to a target sum. The brute-force approach checks every pair, which is O(n²). The complement lookup pattern flips the question on its head: instead of asking "does any other number complete this pair?", you ask "have I already seen the number that would complete this pair?"

In this step, get ready to:
  • Learn the complement lookup pattern and the "check then insert" technique.
  • Implement both a brute-force and an optimized hash map solution for pair sum.
  • Trace through examples step by step to see why the pattern handles edge cases.
Learn the complement pattern

The complement pattern is a mental shift. Instead of searching forward through the list for a matching partner, you remember what you have already seen and check whether the missing piece has shown up before.

  • The complement of the current number is target - current_number. If the complement already exists in your hash map, you have found your pair.
  • enumerate(iterable) returns (index, value) pairs as you loop. This gives you both the position and the value in a single pass.
  • The order of operations matters: check if the complement exists BEFORE inserting the current number. This prevents an element from matching with itself.

Why check before insert?

If you insert first and check second, a number could find itself in the hash map and report a false match. For example, with input [3, 3] and target 6, the first 3 would match itself if you inserted before checking.

By checking first, the first 3 sees an empty map and gets inserted. The second 3 then finds its complement already in the map. Correct behavior.

Implement brute force, then the hash map solution

Time to open complement.py and replace its placeholder with real code. You will write two versions of the same solution: the brute-force approach first, then the optimized complement lookup.

  • In Cursor, open complement.py from the Explorer sidebar.
  • Select all the placeholder text and replace it with the following docstring and brute-force function:
"""
Pattern 2 - Complement Lookup: Pair Sum
=======================================
Problem: Given a list of integers and a target sum, return the indices
of the two numbers that add up to the target. Assume exactly one
solution exists, and you may not use the same element twice.

Example:
    pair_sum([2, 7, 11, 15], 9) -> [0, 1]
    pair_sum([3, 2, 4], 6) -> [1, 2]

Pattern: For each element, check if its complement (target - current)
has already been seen. Store value -> index in a hash map.
Time: O(n) | Space: O(n)
"""


def pair_sum_brute(nums, target):
    """Brute force: check every pair. O(n^2) time."""
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

What does this code do?

The docstring frames the problem: given a list and a target, find the indices of two numbers that sum to the target.

  • pair_sum_brute uses two nested loops to check every possible pair. The outer loop picks the first number, the inner loop picks the second.
  • If nums[i] + nums[j] == target, the pair is found and their indices are returned. This is O(n²) because every element is compared against every other element.
  • Now add the optimized hash map solution below pair_sum_brute:

def pair_sum(nums, target):
    """Optimal: hash map for complement lookup. O(n) time, O(n) space."""
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

What does this code do?

  • seen = {} creates a dictionary that maps each number's value to its index. This is your "memory" of what you have already passed.
  • for i, num in enumerate(nums) gives you both the index (i) and the value (num) on each iteration.
  • complement = target - num calculates the value you need to complete the pair. Then if complement in seen checks if that value was encountered earlier. This lookup is O(1).
  • seen[num] = i records the current number AFTER checking. This is the "check then insert" pattern that prevents self-matching.
  • Save complement.py.

Seeing a syntax error?

  • Make sure there is a blank line between the end of pair_sum_brute and the start of pair_sum. Python needs blank lines between top-level function definitions.
  • Check that the for loop and if statement inside pair_sum are indented with 4 spaces, not tabs.

Help me debug a syntax error in my pair_sum function

Trace through examples and test

Before running the code, let's trace through an example by hand. This builds the intuition for how the hash map state evolves on each iteration.

Tracing pair_sum([2, 7, 11, 15], 9)

  • Iteration 0: num = 2, complement = 9 - 2 = 7. Is 7 in seen? No. Insert seen = {2: 0}.
  • Iteration 1: num = 7, complement = 9 - 7 = 2. Is 2 in seen? YES. Return [seen[2], 1] which is [0, 1].

The function finds the answer in just 2 iterations. The brute-force version would have also found it in the first comparison, but for larger lists the difference is dramatic: O(n) vs O(n²).

  • Add the test cases at the bottom of complement.py:

# Test cases
print("=== Pair Sum ===")
print(pair_sum([2, 7, 11, 15], 9))  # [0, 1]
print(pair_sum([3, 2, 4], 6))       # [1, 2]
print(pair_sum([3, 3], 6))          # [0, 1]

Why test [3, 3] with target 6?

This edge case proves the "check then insert" order works. Both numbers are 3, and 3 + 3 = 6. The first 3 gets inserted at index 0. The second 3 computes complement 6 - 3 = 3, finds it in seen, and returns [0, 1].

  • Save complement.py.
  • Run your tests by entering this command in the terminal:
python3 complement.py
  • You should see this output:
=== Pair Sum ===
[0, 1]
[1, 2]
[0, 1]

Getting an empty list or wrong indices?

  • If you see [] instead of indices, check that your complement calculation uses subtraction: target - num, not addition.
  • Verify that you are calling pair_sum (the optimized function) in your print statements, not pair_sum_brute.
  • Make sure seen[num] = i comes AFTER the if complement in seen check. Inserting before checking breaks the logic.

Help me figure out why my pair_sum function returns wrong results

✔️ Awesome, I've got everything!

Great. Double check you have saved complement.py and all three test cases print the correct indices.

ⓧ I'd like to double check the full code

Here is the complete complement.py for comparison:

"""
Pattern 2 - Complement Lookup: Pair Sum
=======================================
Problem: Given a list of integers and a target sum, return the indices
of the two numbers that add up to the target. Assume exactly one
solution exists, and you may not use the same element twice.

Example:
    pair_sum([2, 7, 11, 15], 9) -> [0, 1]
    pair_sum([3, 2, 4], 6) -> [1, 2]

Pattern: For each element, check if its complement (target - current)
has already been seen. Store value -> index in a hash map.
Time: O(n) | Space: O(n)
"""


def pair_sum_brute(nums, target):
    """Brute force: check every pair. O(n^2) time."""
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []


def pair_sum(nums, target):
    """Optimal: hash map for complement lookup. O(n) time, O(n) space."""
    seen = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []


# Test cases
print("=== Pair Sum ===")
print(pair_sum([2, 7, 11, 15], 9))  # [0, 1]
print(pair_sum([3, 2, 4], 6))       # [1, 2]
print(pair_sum([3, 3], 6))          # [0, 1]

You now have three patterns in your toolkit: duplicate detection with sets, frequency counting with dicts, and complement lookup with a value-to-index map. Next up, you will learn the grouping pattern to categorize words by a shared key.

Group Anagrams by Canonical Key

Your complement lookup pattern showed how a single hash map replaces a nested loop for pair finding. Now you'll tackle a different category of problem: grouping related items together.

When items share a hidden relationship (like two words being anagrams of each other), the trick is to compute a canonical key that all related items produce. In this step, you'll use defaultdict and sorted to group anagrams by their sorted character signature.

In this step, get ready to:
  • Learn how defaultdict(list) auto-initializes dictionary values.
  • Implement group_anagrams(strs) using a sorted tuple as the canonical key.
  • Run test cases and understand the general grouping pattern.
Learn the grouping tools

Before writing the solution, you need two tools from Python's standard library that make grouping elegant.

What is defaultdict?

A regular dict raises a KeyError when you access a missing key with bracket notation. defaultdict(list) solves this by automatically creating an empty list for any missing key the first time you access it.

This means groups[key].append(word) works even if key has never been seen before. No need to check if key in groups first.

Why tuple(sorted(word)) as a key?

Two words are anagrams if they contain the same characters in any order. Sorting both words produces identical character sequences. For example, sorted("eat") and sorted("tea") both produce ['a', 'e', 't'].

You wrap the sorted list in tuple() because lists are not hashable and cannot be used as dictionary keys. Tuples containing only hashable elements can be used as keys.

  • In Cursor, open grouping.py and replace the placeholder comment with this docstring and import:
"""
Pattern 3 - Grouping by Key: Group Anagrams
============================================
Problem: Given a list of strings, group the anagrams together.
Two strings are anagrams if they contain the same characters
in any order. Return a list of groups (order doesn't matter).

Example:
    group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    -> [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Pattern: Derive a canonical key that all group members share,
then bucket items by that key using a defaultdict(list).
Time: O(n * k log k) where n = number of words, k = max word length
Space: O(n * k)
"""
from collections import defaultdict

What does this code do?

  • The docstring documents the problem, example input/output, the pattern name, and the time/space complexity.
  • from collections import defaultdict imports the auto-initializing dictionary you'll use to bucket words into groups.
  • Save grouping.py.
Implement the grouping solution

The problem is: given a list of strings, group all anagrams together and return a list of groups. The core idea is to derive a canonical key that every anagram of the same word produces, then collect words into buckets by that key.

  • Below the import line in grouping.py, add the group_anagrams function:


def group_anagrams(strs):
    """Use sorted character tuple as a canonical key to group anagrams."""
    groups = defaultdict(list)
    for word in strs:
        key = tuple(sorted(word))
        groups[key].append(word)
    return list(groups.values())

What does this code do?

  • groups = defaultdict(list) creates a dictionary where every new key automatically starts with an empty list.
  • tuple(sorted(word)) produces the canonical key. All anagrams of the same word sort to the same tuple.
  • groups[key].append(word) drops each word into the bucket for its canonical key.
  • list(groups.values()) returns the final grouped result as a list of lists.
  • Save grouping.py.

Why is this O(n * k log k)?

You iterate through n words (O(n)). For each word, you sort its k characters (O(k log k)). The hash map lookup and append are O(1) on average. Total: O(n * k log k).

Test and discuss alternative keys

Now you'll add test cases that exercise the function with a realistic word list and edge cases.

  • Add the following test cases at the bottom of grouping.py:


# Test cases
print("=== Group Anagrams ===")
result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
for group in result:
    print(sorted(group))
# ['ate', 'eat', 'tea']
# ['nat', 'tan']
# ['bat']

print()
print(group_anagrams([""]))
print(group_anagrams(["a"]))

What does this code do?

  • The main test groups six words into three anagram families.
  • sorted(group) alphabetizes each group before printing so the output is deterministic regardless of insertion order.
  • The edge cases test an empty string and a single character.
  • Save grouping.py and run the tests by executing this in your terminal:
python3 grouping.py
  • You should see three sorted groups printed, followed by the edge case results:
=== Group Anagrams ===
['ate', 'eat', 'tea']
['nat', 'tan']
['bat']

[['']]
[['a']]

Seeing a NameError or empty output?

  • Make sure the from collections import defaultdict line is at the top of the file, before the function definition.
  • Check that your test cases are outside and below the function body (not indented inside it).
  • Verify the function is named exactly group_anagrams (with an underscore) to match the test call.

Help me debug my group_anagrams function

What about a count tuple instead of sorting?

An alternative canonical key is a 26-element tuple where each position holds the count of that letter. This runs in O(k) per word instead of O(k log k) from sorting.

In interviews, the sorting approach is usually fine and easier to explain. Mention the count-tuple alternative to show you know the optimization exists.

The general pattern is always the same: derive a canonical key that all group members share, then bucket by that key.

✔️ Awesome, I've got everything!

Great. Double check you've saved grouping.py and all tests print the expected output.

ⓧ I'd like to double check the full code

Here is the complete grouping.py file:

"""
Pattern 3 - Grouping by Key: Group Anagrams
============================================
Problem: Given a list of strings, group the anagrams together.
Two strings are anagrams if they contain the same characters
in any order. Return a list of groups (order doesn't matter).

Example:
    group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
    -> [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

Pattern: Derive a canonical key that all group members share,
then bucket items by that key using a defaultdict(list).
Time: O(n * k log k) where n = number of words, k = max word length
Space: O(n * k)
"""
from collections import defaultdict


def group_anagrams(strs):
    """Use sorted character tuple as a canonical key to group anagrams."""
    groups = defaultdict(list)
    for word in strs:
        key = tuple(sorted(word))
        groups[key].append(word)
    return list(groups.values())


# Test cases
print("=== Group Anagrams ===")
result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
for group in result:
    print(sorted(group))
# ['ate', 'eat', 'tea']
# ['nat', 'tan']
# ['bat']

print()
print(group_anagrams([""]))
print(group_anagrams(["a"]))

Secret mission

Count Subarrays with the Prefix Sum Pattern

This is the pattern that looks scary but is elegant once you see it. It combines a running total with a hash map to find subarrays with a target sum in O(n). Can you layer prefix sums on top of the complement lookup pattern you already know?

Clean Up Your Resources

Clean Up Your Resources

This project runs entirely locally, so there are no ongoing costs. Decide whether to keep your files for future practice or delete them.

Resources you used:

  • The hashmap-patterns folder on your Desktop containing foundations.py, frequency.py, complement.py, grouping.py, and prefix_sum.py.

Keep everything running

No action needed. Choose this if you plan to revisit these solutions for interview practice or want to extend them with new problems.

  • Your hashmap-patterns folder stays on your Desktop, ready to open in Cursor anytime.
  • You can add new pattern files (sliding window, binary search) to the same folder as you learn more.

Pause - I'll come back to this later

Since this project uses only local files with no running processes, there is nothing to pause. Your files will sit quietly on disk until you return.

  • Close the hashmap-patterns folder in Cursor to free up editor memory.
  • When you come back, reopen the folder in Cursor and pick up where you left off.

Delete - I don't want to use this again

Remove all project files from your machine.

  • Close the hashmap-patterns folder in Cursor.
  • Delete the project folder by running this command in your terminal:

macOS

rm -rf ~/Desktop/hashmap-patterns

Windows

rmdir /s /q %USERPROFILE%\Desktop\hashmap-patterns
  • Confirm deletion by running ls ~/Desktop (macOS) or dir %USERPROFILE%\Desktop (Windows). You should no longer see hashmap-patterns in the output.

Nice Work!

Nice Work!

You just built four complete hash map solutions from scratch, each one replacing a brute-force nested loop with an O(n) lookup. These are the exact patterns that show up in coding interviews over and over again.

You've learned how to:

  • Implement the four most common hash map interview patterns (duplicate detection with sets, frequency counting with Counter, complement lookup with enumerate, and grouping by canonical key with defaultdict).
  • Recognize when a problem's brute-force O(n²) nested loop can be replaced by a single-pass O(n) hash map lookup.
  • Write and run test cases that verify correctness, trace through examples step by step, and compare brute-force output against optimized output.
  • Secret Mission: Built prefix_sum.py combining running totals with hash map lookups to count target-sum subarrays in O(n).

Ready to quiz yourself?