HashMap Tricks: 4 Interview Problems Where Dict Beats Array

HashMap Tricks: 4 Problems Where Dict Beats Array in Python

You're 20 minutes into a coding interview. The brute force solution is working, but the interviewer just asked, "Can you do better than $O(n^2)$?" You reach for nested loops, maybe a sorted array. But the real answer is often simpler: swap your list for a dictionary.

HashMaps (Python's dict) turn $O(n)$ searches into $O(1)$ lookups. That's the theory. In practice, knowing when to use them separates candidates who pass from those who don't. Here are four problems where dictionaries outperform arrays, with the exact mistakes I'd make under pressure.

Problem 1: Two Sum — The Dictionary Wake-Up Call

This is the classic. Given an array of integers and a target sum, find two numbers that add up to the target.

Most people start here:

def two_sum_brute(nums, target):
    # Check every pair
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

# Test
nums = [2, 7, 11, 15]
print(two_sum_brute(nums, 9))  # [0, 1]

Time complexity: $O(n^2)$. For n=10000, that's 100 million comparisons. The interviewer is already writing notes.

The dict trick: instead of searching the array for target - nums[i], store what you've seen in a HashMap. When you hit a number, check if its complement exists.

python
def two_sum_hash(nums, target):
    seen = {}  # value -> index

---

*Continue reading the full article on [TildAlice](https://tildalice.io/hashmap-tricks-dict-beats-array-python-interview/)*