LeetCode 1 Two Sum: From Brute Force to HashMap, Plus Every Variant

Two Sum is LeetCode problem number 1 and probably the most solved coding problem in the world. That is exactly why answering it well is harder than it looks: the interviewer has heard the HashMap answer hundreds of times and is waiting to see whether you can justify it, handle its edge cases, and adapt it when they change the constraints. This page covers the three approaches with tested C++, Java and Python, then every variant and follow-up worth preparing.

The Problem and the Questions to Ask First

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to target. LeetCode guarantees exactly one solution and says you may not use the same element twice; the answer can be returned in any order.

Example: nums = [2, 7, 11, 15], target = 9 returns [0, 1] because 2 + 7 = 9.

In an interview the guarantees are not always stated. Ask, because each answer changes the solution:

Asking these takes thirty seconds and is itself part of the signal, as described in the step-by-step method for approaching DSA problems.

Approach 1: Brute Force, O(n²)

Check every pair (i, j) with i < j.

def two_sum_brute(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

O(n²) time, O(1) space. With LeetCode's limit of 10⁴ elements it is about 5 × 10⁷ comparisons, which actually passes, but interviewers expect you to state it and move on. The useful observation is why it is slow: for each nums[i], the inner loop is searching for one specific value, target - nums[i]. Searching for a specific value is what hash tables are for.

Approach 2: One-Pass HashMap, O(n)

Keep a map from value to index of everything seen so far. For each element, the partner it needs is target - x. If that partner was already seen, you are done; otherwise remember x for future elements.

vector<int> twoSum(const vector<int>& nums, int target) {
    unordered_map<int, int> seen;              // value -> index
    for (int i = 0; i < (int)nums.size(); i++) {
        auto it = seen.find(target - nums[i]);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {};
}

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> seen = new HashMap<>();   // value -> index
    for (int i = 0; i < nums.length; i++) {
        Integer j = seen.get(target - nums[i]);
        if (j != null) return new int[]{j, i};
        seen.put(nums[i], i);
    }
    return new int[0];
}

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return [seen[need], i]
        seen[x] = i
    return []

Why one pass is enough: if the answer is the pair (i, j) with i < j, then when the loop reaches j, nums[i] is already in the map. So the pair is always found at its second element. The two-pass variant (fill the map, then scan) also works but needs an explicit seen[need] != i check to avoid self-pairing.

In Java, note Integer j = seen.get(...) with a null check rather than containsKey followed by get: one lookup instead of two, and no unboxing of a null. The Java Collections cheat sheet covers why comparing Integer values with == would be a bug here.

Dry Run and Edge Cases

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

Note the first row: a naive solution that pre-fills the map would return [0, 0] for this input. Edge cases to say aloud:

• [3, 3], target 6 returns [0, 1]: the first 3 is stored before the second looks it up.
• Negatives and zero: [-3, 4, 3, 90], target 0 returns [0, 2]; no special handling needed.
• Overflow: target - x can overflow a 32-bit int when both are near the limits. Under LeetCode's constraints (values and target within ±10⁹) the result stays within ±2 × 10⁹, just inside INT_MAX ≈ 2.147 × 10⁹, so int is safe there. Say that you checked; with unknown bounds, compute in 64-bit.
• No answer: returns an empty array; agree on the convention.

Approach 3: Sorting + Two Pointers

If the array were sorted, you could put one pointer at each end. If the sum is too small, move the left pointer right (the only way to increase it); too big, move the right pointer left. Each step discards one element for good, so the scan is O(n).

For LeetCode 1 you need original indices, so sort the indices by value:

def two_sum_sort_indices(nums, target):
    order = sorted(range(len(nums)), key=lambda i: nums[i])
    lo, hi = 0, len(order) - 1
    while lo < hi:
        s = nums[order[lo]] + nums[order[hi]]
        if s == target:
            return sorted([order[lo], order[hi]])
        if s < target:
            lo += 1
        else:
            hi -= 1
    return []

O(n log n) time and O(n) space for the index array, so it is strictly worse than hashing for this exact problem. Why learn it? Because it is the right tool when (a) the input is already sorted, (b) you need all unique pairs by value, (c) you are building up to 3Sum, or (d) memory is tight and you may sort in place.

Why two pointers never skips the answer

Suppose the answer is values at sorted positions (p, q). While lo < p and hi > q both still hold, the pointers can only move inward. If lo reaches p first, then every sum a[p] + a[hi] with hi > q is at least a[p] + a[q] = target, so if it is strictly greater, hi moves left until it hits q. Symmetric for hi reaching q first. Interviewers ask this proof surprisingly often; the two pointers guide uses the same argument for Container With Most Water.

Two Sum II: Input Array Is Sorted (LeetCode 167)

The array is sorted, indices are 1-based, and you must use O(1) extra space. Exactly the two-pointer scan:

public int[] twoSumSorted(int[] numbers, int target) {
    int lo = 0, hi = numbers.length - 1;
    while (lo < hi) {
        int s = numbers[lo] + numbers[hi];
        if (s == target) return new int[]{lo + 1, hi + 1};   // 1-indexed
        if (s < target) lo++;
        else hi--;
    }
    return new int[0];
}

Using a hash map here works but ignores the sortedness and uses O(n) memory, which interviewers will point out. Binary searching the partner for each element is O(n log n), better than brute force but worse than two pointers.

Counting All Pairs and Unique Pairs

Count all index pairs with sum = target

Store counts instead of a single index. Each new element pairs with every earlier occurrence of its complement.

from collections import Counter

def count_pairs(nums, target):
    seen = Counter()
    count = 0
    for x in nums:
        count += seen[target - x]
        seen[x] += 1
    return count
# [1, 1, 1, 1], target 2 -> 6 (every pair of the four 1s)
# [1, 5, 7, -1, 5], target 6 -> 3: (1,5), (7,-1), (1,5)

This is the same "count complements seen so far" idea that solves Subarray Sum Equals K with prefix sums and Count Number of Nice Subarrays; see hashing interview problems.

All unique value pairs

Sort, two pointers, and skip equal neighbours after each match:

def unique_pairs(nums, target):
    nums = sorted(nums)
    lo, hi = 0, len(nums) - 1
    out = []
    while lo < hi:
        s = nums[lo] + nums[hi]
        if s < target:
            lo += 1
        elif s > target:
            hi -= 1
        else:
            out.append((nums[lo], nums[hi]))
            lo += 1
            hi -= 1
            while lo < hi and nums[lo] == nums[lo - 1]:
                lo += 1
            while lo < hi and nums[hi] == nums[hi + 1]:
                hi -= 1
    return out
# [1, 1, 2, 45, 46, 46], target 47 -> [(1, 46), (2, 45)]

From Two Sum to 3Sum (LeetCode 15)

Find all unique triplets that sum to 0. Fix the first element nums[i]; you now need a Two Sum with target -nums[i] on the elements to its right. Sorting first gives you both the two-pointer inner loop and an easy way to skip duplicates.

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i = 0; i + 2 < n; i++) {
        if (nums[i] > 0) break;                            // smallest is positive: done
        if (i > 0 && nums[i] == nums[i - 1]) continue;      // skip duplicate anchors
        int lo = i + 1, hi = n - 1;
        while (lo < hi) {
            int s = nums[i] + nums[lo] + nums[hi];
            if (s < 0) lo++;
            else if (s > 0) hi--;
            else {
                res.push_back({nums[i], nums[lo], nums[hi]});
                lo++; hi--;
                while (lo < hi && nums[lo] == nums[lo - 1]) lo++;   // skip duplicate seconds
            }
        }
    }
    return res;
}

def three_sum(nums):
    nums.sort()
    res = []
    n = len(nums)
    for i in range(n - 2):
        if nums[i] > 0:
            break
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        lo, hi = i + 1, n - 1
        while lo < hi:
            s = nums[i] + nums[lo] + nums[hi]
            if s < 0:
                lo += 1
            elif s > 0:
                hi -= 1
            else:
                res.append([nums[i], nums[lo], nums[hi]])
                lo += 1
                hi -= 1
                while lo < hi and nums[lo] == nums[lo - 1]:
                    lo += 1
    return res

For [-1, 0, 1, 2, -1, -4] it returns [[-1, -1, 2], [-1, 0, 1]]; for [0, 0, 0, 0], [[0, 0, 0]]. Both versions were checked against a brute-force set of triplets on thousands of random arrays. Time O(n²), extra space O(1) beyond the output and sort.

Why not a hash map inside 3Sum? It works in O(n²) too, but deduplicating triplets then needs a set of sorted tuples, which is messier and slower in practice. 4Sum (LC 18) adds one more fixed loop for O(n³); the general kSum recurses down to a two-pointer Two Sum, with O(n^k-1) time. Related: 3Sum Closest (LC 16) uses the same scan while tracking the closest sum.

Other Two Sum Variants Worth Knowing

Two Sum III: Data Structure Design (LC 170)

Support add(number) and find(value) (does any pair sum to value?). Store counts in a hash map; add is O(1) and find scans distinct keys in O(n), being careful that a pair of equal numbers needs a count of at least 2.

from collections import Counter

class TwoSum:
    def __init__(self):
        self.count = Counter()

    def add(self, number):
        self.count[number] += 1

    def find(self, value):
        for x, c in self.count.items():
            y = value - x
            if y != x and y in self.count:
                return True
            if y == x and c > 1:
                return True
        return False

The interesting discussion is the trade-off: if find is called far more often than add, precompute all pair sums into a set on each add (O(n) add, O(1) find). Saying "it depends on the read/write ratio" is exactly the kind of judgment interviewers look for.

Two Sum IV: Input Is a BST (LC 653)

Either traverse with a hash set (O(n) time and space), or do an inorder traversal to get a sorted list and use two pointers, or, for O(h) space, run two BST iterators (one ascending, one descending) as the two pointers. The iterator version is a strong answer for senior candidates.

Closest pair, less than K, and difference

• Pair sum closest to target: sort + two pointers, track the best absolute difference.
• Two Sum Less Than K (LC 1099): sort + two pointers, record sums below K.
• Pair with difference k: hash set lookup of x + k and x - k, or sort and move two pointers in the same direction (K-diff Pairs, LC 532).
• Count pairs with sum ≤ target: sort, two pointers; when a[lo] + a[hi] <= target, all pairs (lo, lo+1..hi) qualify, so add hi - lo and move lo.

Follow-Up Questions Interviewers Actually Ask

Other follow-ups you should have a one-line answer for:

• "Return all pairs": output can be Θ(n²) (all equal values), so no algorithm beats that bound; clarify unique values vs index pairs.
• "Floating-point numbers": exact-match hashing fails with rounding; sort and use two pointers with a tolerance.
• "Multiple queries with different targets": sort once (O(n log n)), then each query is an O(n) two-pointer scan, or O(n) with a hash set per query.
• "Distributed across machines": same hash-partitioning idea as the 10-billion case, one partition pair per worker.

Common Two Sum Mistakes

1. Inserting before looking up, which lets an element pair with itself ([3, 2, 4], target 6 returns [0, 0]).
2. Sorting the array in place and returning indices of the sorted array.
3. Storing the map as index to value instead of value to index; then lookups by value are O(n).
4. Two lookups per element (containsKey then get); fine for correctness, but say why you used a single get/find.
5. Forgetting 1-based indices in Two Sum II.
6. 3Sum duplicates: skipping duplicates at the wrong time (before recording the first match) loses valid triplets like [-1, -1, 2].
7. Not stating complexity for both time and space, and not explaining why one pass suffices.

Two Sum is also the first problem on every major list compared in Blind 75 vs NeetCode 150 vs Striver. Next in the two-pointer family, try Container With Most Water.

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.