Hash Maps

O(1) lookups that power everything from databases to frequency counting

A hash map (dict in Python) stores key-value pairs and provides O(1) average-case lookup, insert, and delete.
How it works: A hash function converts a key to an index in an array. Python's dict is a sophisticated hash map with collision handling built in.

The classic: two sum with a hash mappython

def two_sum(nums, target):
    """Find two indices that sum to target. O(n) time, O(n) space."""
    seen = {}  # value → index

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:          # O(1) lookup
            return [seen[complement], i]
        seen[num] = i                   # Store for future lookups

    return []

print(two_sum([2, 7, 11, 15], 9))  # → [0, 1]

Nested loops: O(n²)⚠ Works but messy

# O(n²) brute force
def two_sum_slow(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

Hash map: O(n)✓ Pythonic

# O(n) with hash map
def two_sum_fast(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        comp = target - num
        if comp in seen:
            return [seen[comp], i]
        seen[num] = i

💡

Trading O(n) space for O(n) time improvement, hash maps make this trade constantly

🤔Quick Check

What is the worst-case time complexity of a hash map lookup?

Practice Exercises

0/1 solved

Exercise 1 of 1medium

⏱ 00:00

Group Anagrams

Group strings that are anagrams of each other.
Expected output: [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]

solution.py

1 / 1

Solve all 1 exercise to unlock completion

Previous Next