0x20Lesson 3 of 13

Trade memory for speed with hash maps

Use dictionaries and sets to replace nested loops with lookups.

20 min 5-question quiz 1 code exercise

By the end of this lesson you can

Recognize problems that a hash map speeds up.
Solve Two Sum in one pass.
Count frequencies with a dictionary.

The hash map (a Python dict) is the most useful data structure in coding interviews. It answers “have I seen this before?” and “where?” in O(1) average time. Whenever your brute force searches the input again inside a loop, ask whether a dictionary could remember what the inner loop is looking for.

Patterns that use hashing

Complement lookup: for each value, check whether the value you need (target - num) was already seen. This is Two Sum.
Frequency counting: collections.Counter or dict.get(key, 0) + 1 for anagrams, majority element, and “first unique character.”
Grouping: map a canonical key to a list, such as sorted letters → words for grouping anagrams.
Seen set: detect duplicates or cycles.

solution.py

1def two_sum(nums, target):
2    seen = {}  # value -> index
3    for i, num in enumerate(nums):
4        if target - num in seen:
5            return [seen[target - num], i]
6        seen[num] = i
7    return None
8
9print(two_sum([2, 7, 11, 15], 9))
10print(two_sum([3, 2, 4], 6))

Output

[0, 1]
[1, 2]

The brute force checks every pair: O(n²) time, O(1) space. The dictionary version makes one pass: O(n) time, O(n) space. Notice the order - check for the complement before storing the current number, so a number is never paired with itself.

Key takeaways

Reach for a dict or set when an inner loop is searching for something.
Check for the complement before storing the current item.
Hashing trades O(n) memory for O(1) average lookups.

Lesson quiz

5 questions · pass with 4 correct · up to 50 XP

Passing this quiz completes the lesson and keeps your streak going. Questions you miss come back in review sessions later.

Practice: solve interview problems

Solve a classic interview problem in Python and run it against test cases. Aim for the optimal complexity, then check the edge cases. Exercises run locally in your browser.

Exercise 1

Solve Two Sum

+25 XP

Read a line of integers and then a target. Exactly one pair of different positions adds up to the target. Print their indices, smaller first, separated by a space. Use a dictionary for an O(n) solution.

Classic example
Not the first element
Duplicate values

main.py

Loading editor…

Python runs in a sandboxed browser worker with a 60 second time limit. Its runtime loads from the Pyodide CDN; your code stays in this browser.

Questions about this lesson

Stuck? Ask. Figured something out? Share it. Explaining is one of the best ways to learn.

Loading posts…