Two Sum

Problem

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.

Example:

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

Approach

The brute force approach is O(n²) — checking every pair. We can do better with a hash map.

Hash Map Solution

Intuition: For each number, check if target - num exists in our hash map. If it does, we found our pair!

Algorithm:

1. Create a hash map to store numbers we've seen and their indices
2. For each number in the array:
   • Calculate complement: target - current number
   • If complement exists in hash map, return both indices
   • Otherwise, add current number to hash map
3. Return result

Solution

import java.util.HashMap;
import java.util.Map;

class Solution {
  public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

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

      if (map.containsKey(complement)) {
        return new int[] {map.get(complement), i};
      }

      map.put(nums[i], i);
    }

    return new int[] {};
  }
}

Complexity Analysis

Time Complexity: O(n)

• We traverse the array once
• Hash map lookup and insertion are O(1)

Space Complexity: O(n)

• Worst case: store n-1 elements in hash map

Why This Works

The key insight: we only need to look backwards, not forwards.

When we're at index i, we check if target - nums[i] has already been seen. If it has, we found our pair. If not, we store nums[i] for future iterations.

Edge Cases

Solution solution = new Solution();

solution.twoSum(new int[] {1, 2}, 3); // [0, 1]
solution.twoSum(new int[] {-1, -2, -3, -4}, -6); // [1, 3]
solution.twoSum(new int[] {0, 4, 3, 0}, 0); // [0, 3]
solution.twoSum(new int[] {1000000, 2000000}, 3000000); // [0, 1]

Follow-up Questions

Q: What if the array is sorted? A: Use two pointers approach (left and right), O(1) space!

Q: What if we need all pairs that sum to target? A: Continue iteration instead of returning immediately.

Q: What if there's no solution? A: Return [-1, -1] or throw an error.

Related Problems

• 3Sum — Medium
• 4Sum — Medium
• Two Sum II — Medium