two sum

The classic opener. Everyone's first LeetCode problem, and honestly it's a great one to warm up with.

Problem

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

Brute Force

The naive approach is to check every pair. Two nested loops, O(n^2) time. It works but it's slow.

def twoSum(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 Approach

The key insight: for each number, we need target - num. If we've seen that complement before, we're done. One pass, O(n) time, O(n) space.

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

Takeaway

This problem teaches the most fundamental pattern in DSA: trading space for time. A hash map turns O(n^2) into O(n). You'll see this pattern everywhere.