Lesson 2, Arrays and hashing I

Arrays and hashing I

Why this lesson matters

If you are rusty, this is one of the best places to rebuild fast. A surprising number of interview questions become manageable once lookup is cheap.

Theme

This lesson is about a simple tradeoff:

spend extra memory so you do not repeat expensive searching.

That is the heart of many arrays and hashing questions.

The three most common moves

Seen set

Use a set when you only care whether something has appeared before.

Value to index map

Use a hash map when you need to find a matching partner quickly.

Frequency map

Use counts when the exact number of occurrences matters.

Worked example: Two Sum

Given an array nums and a target, return the indices of two numbers that add up to the target.

Brute force

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]

Runtime: O(n^2)

Optimize the repeated work

For each number, you really want to know whether the complement already appeared.

If the current number is num, the needed partner is target - num.

A hash map can store values we have seen and the index where we saw them.

Clean solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        seen = {}

        for i, num in enumerate(nums):
            need = target - num
            if need in seen:
                return [seen[need], i]
            seen[num] = i

Runtime: O(n) Space: O(n)

Worked example thinking

1. The brute force tries all partners.
2. The expensive part is searching for the partner.
3. A hash map turns that search into near-constant lookup.
4. So we scan once and remember what we have already passed.

Exercises

Do these in order:

1. #1 — Two Sum Focus: complement lookup.
2. #242 — Valid Anagram Focus: frequency maps.
3. #49 — Group Anagrams Focus: choosing a usable hash key.
4. #238 — Product of Array Except Self as a stretch Focus: learn that not every array problem is a hash problem.

Common mistake

Do not force hashing onto every array question.

Sometimes the right answer is sorting, two pointers, prefix sums, or plain iteration. The win here is not “always use a map”. The win is learning when fast lookup is the missing piece.

Tiny review prompts

Try to answer these from memory:

1. When do you use a set instead of a map?
2. What repeated work does the hash map remove in Two Sum?
3. What is the space tradeoff for the standard O(n) solution?

Next: Training roadmap