Two Sum

Difficulty: Easy

Problem

Given an array of integers 'nums' and an integer 'target', return the indices of the two numbers that add up to the target. You may assume that each input has exactly one solution, and you may not use the same element twice.

Example

Input: nums = [2, 11, 7, 15], target = 9
Output: [0, 2]
Explanation: Because nums[0] + nums[2] = 2 + 7 = 9, we return [0, 2].

Brute-force approach

Check every possible pair of numbers to see if they add up to the target.

Steps

  1. Pick the first number
  2. Compare it with every other number
  3. Check if their sum equals target
  4. Repeat for all numbers

Time complexity: O(n²) · Space complexity: O(1)

Trade-offs

  • Very slow for large arrays
  • n² comparisons needed
  • Inefficient for repeated lookups

Optimal approach

Key insight: For each number, we need target - number. If we've seen it before, we found our pair!

Use a hash map to remember numbers we've seen, so we can find complements in O(1) time.

Steps

  1. Look at current number
  2. Calculate complement (target - current)
  3. Check if complement is in hash map
  4. If not, store current number and its index

Time complexity: O(n) · Space complexity: O(n)