Two Sum

Problem

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

Each input has exactly one solution, and you may not use the same element twice.

Approach 1: Brute Force

Check every pair of numbers.

def two_sum(nums, target)
  (0...nums.length).each do |i|
    (i + 1...nums.length).each do |j|
      return [i, j] if nums[i] + nums[j] == target
    end
  end
end

Time: O(n^2) – nested loop over all pairs.

Space: O(1) – no extra data structures.

Approach 2: Hash Map (Optimal)

Store each number’s index in a hash. For each element, check if its complement (target - num) already exists in the hash.

def two_sum(nums, target)
  seen = {}
  nums.each_with_index do |num, i|
    complement = target - num
    return [seen[complement], i] if seen.key?(complement)
    seen[num] = i
  end
end

Time: O(n) – single pass through the array. Hash lookups are O(1) average.

Space: O(n) – the hash stores up to n entries.

Key Takeaway

When looking for pairs that satisfy a condition, a hash map lets you trade space for time by turning an O(n) inner search into O(1) lookup. This “complement lookup” pattern applies to any problem where you need to find two elements with a target relationship.