Two Sum

Problem Description

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Examples

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Approach

The brute-force approach checks every pair in O(n^2) time. We can do much better with a hash map.

As we iterate through the array, for each element we calculate its complement (target - nums[i]). If the complement already exists in our hash map, we've found our pair. Otherwise, we store the current number and its index in the map.

This works because by the time we reach the second number of any valid pair, the first number is already stored in the map.

Solution

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>()

  for (let i = 0; i < nums.length; i++) {
    const complement= target - nums[i]

    if (map.has(complement)) {
      return [map.get(complement)!, i]
    }

    map.set(nums[i], i)
  }

  return []
}

Complexity Analysis

• Time: O(n) — single pass through the array
• Space: O(n) — hash map stores up to n elements

Key Takeaways

• When looking for pairs that satisfy a condition, think hash map.
• Trading space for time is often worthwhile — going from O(n^2) to O(n).
• The hash map pattern appears in many LeetCode problems (Three Sum, Four Sum, subarray sums, etc.).