Course4all
Join us on telegram
Home/dsa/Arrays & Hashing/Two Sum

Two Sum

Master this topic with zero to advance depth.

Two Sum

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.

Visual Representation

nums = [2, 7, 11, 15], target = 9 1. Complement = target - current 2. Scan through array: - 2: Complement = 9-2 = 7. Not in map. Store {2: 0} - 7: Complement = 9-7 = 2. FOUND in map at index 0! Return [0, 1]
Easy

Examples

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

Because nums[0] + nums[1] == 9, we return [0, 1].

Approach 1

Level I: Brute Force

Intuition

Try every possible pair of numbers in the array. This involves nested loops where the outer loop picks the first number and the inner loop looks for the second number that sums to the target.

⏱ O(N²)💾 O(1)

Detailed Dry Run

nums = [2, 7, 11], target = 9

  1. i=0 (2), j=1 (7): 2+7=9. Found! Return [0, 1]
java
class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target) return new int[]{i, j};
            }
        }
        return new int[]{};
    }
}
Approach 2

Level II: Sorting + Two Pointers

Intuition

If the array is sorted, we can use two pointers (left and right). If their sum is smaller than target, move left pointer right; if larger, move right pointer left. Note: Since we need indices, we must keep track of original positions.

⏱ O(N log N) for sorting.💾 O(N) to store indices.

Detailed Dry Run

nums = [3, 2, 4], target = 6

  1. Pairs with indices: [(3,0), (2,1), (4,2)]
  2. Sort: [(2,1), (3,0), (4,2)]
  3. L=0 (2), R=2 (4): sum=6. Found indices 1 and 2.
java
import java.util.*;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[][] pair = new int[nums.length][2];
        for(int i=0; i<nums.length; i++) { pair[i][0] = nums[i]; pair[i][1] = i; }
        Arrays.sort(pair, (a, b) -> Integer.compare(a[0], b[0]));
        int l = 0, r = nums.length - 1;
        while(l < r) {
            int sum = pair[l][0] + pair[r][0];
            if(sum == target) return new int[]{pair[l][1], pair[r][1]};
            if(sum < target) l++; else r--;
        }
        return new int[]{};
    }
}
Approach 3

Level III: HashMap (One-Pass)

Intuition

Trade space for time. As we iterate, we calculate the complement needed (target - current). If complement is already in map, we found the pair. Otherwise, store the current number's index in the map.

⏱ O(N)💾 O(N)

Detailed Dry Run

nums = [2, 7, 11], target = 9

  1. n=2, comp=7. Map: {2: 0}
  2. n=7, comp=2. Map contains 2 (idx 0). return [0, 1]
java
import java.util.*;
class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int comp = target - nums[i];
            if (map.containsKey(comp)) return new int[]{map.get(comp), i};
            map.put(nums[i], i);
        }
        return new int[]{};
    }
}
Next Question →Valid Anagram