# Two Sum

Arrays & Hashing Easy LeetCode #1

## 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.