Course4all

Two Sum

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Arrays & Hashing.

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[]{};
    }
}

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
Next Question →Valid Anagram