← All topics

Arrays & Hashing

The bar everyone starts on. Most array problems come down to trading time for space: a hash map turns an O(n) search into an O(1) lookup, at the cost of extra memory. Get comfortable reaching for a dict/set before reaching for a nested loop.

Easy reps

1. Two Sum

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. Exactly one solution exists.

def two_sum(nums, target):
    seen = {}  # value -> index
    for i, n in enumerate(nums):
        complement = target - n
        if complement in seen:
            return [seen[complement], i]
        seen[n] = i

Brute force checks every pair (O(n^2)). Walking the array once while remembering what you've already seen turns it into a single O(n) pass: at each index, ask the hash map whether its complement already showed up.

217. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array.

def contains_duplicate(nums):
    return len(nums) != len(set(nums))

A set drops duplicates by definition, so comparing its size to the original list's size answers the question in one line. Same idea as Two Sum: a hash-based structure replaces an O(n^2) comparison loop.

Level up

Same topic, no training wheels. Solve these on your own before you check the editorial.