What is the brute force approach and complexity for Two Sum?

Check all pairs (i, j) with i < j with time complexity O(N²) and space complexity O(1).

What is the optimal approach and complexity for Two Sum?

For each x, look up target − x in a map of earlier values; then store x with optimal time complexity O(N) and space complexity O(N).

How do you identify the pattern for Two Sum?

Look for key signals in the prompt: "two numbers that add up to target" indicates Once you pick one number, the other is fixed: `target − x`. That is a complement lookup.; "return their indices" indicates You must keep original positions. Store `value → index` in the map, and don't sort plain values.; "array is not sorted" indicates Two pointers need sorted order. Without it, use a hash map.; "can't use the same element twice" indicates Look up before inserting, so the map only holds earlier elements..

Two Sum

Q: What is the optimal approach and complexity for Two Sum?

For each x, look up target − x in a map of earlier values; then store x with optimal time complexity O(N) and space complexity O(N).

Q: How do you identify the pattern for Two Sum?

Look for key signals in the prompt: "two numbers that add up to target" indicates Once you pick one number, the other is fixed: `target − x`. That is a complement lookup.; "return their indices" indicates You must keep original positions. Store `value → index` in the map, and don't sort plain values.; "array is not sorted" indicates Two pointers need sorted order. Without it, use a hash map.; "can't use the same element twice" indicates Look up before inserting, so the map only holds earlier elements..

Easy·LeetCode #1Basic Anchor

LeetCode

Jump:

30-Second Mental ModelHash Map — Complement Lookup (value → index)

Complexity:O(N²)→O(N)

Key Insight

Walk the array once. Standing on nums[i], its partner must be target − nums[i]. Keep a map value → index of the elements already passed. If the partner is in the map, we are done. If not, store nums[i] and move on.

Core Validity Invariant

nums[i] has a partner exactly when target − nums[i] is already in seen. Because seen only holds elements before i, the partner is always a different position.

Problem

You are given an integer array nums and an integer target.

Find two different positions i and j such that nums[i] + nums[j] == target, and return those two indices. Exactly one such pair exists. You may not use the same element twice, but two different elements may hold the same value. The indices can be returned in any order.

Input

An integer array nums and an integer target.

Output

A list of two indices [i, j] with i ≠ j and nums[i] + nums[j] == target.

Example 1

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

Output: [0, 1]

nums[0] + nums[1] = 2 + 7 = 9.

Example 2

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

Output: [1, 2]

2 + 4 = 6. Note that 3 + 3 is not allowed: there is only one 3, and it can't be used twice.

Example 3

Input: nums = [3, 3], target = 6

Output: [0, 1]

Two different elements with the same value are fine.

Constraints

• 2 ≤ nums.length ≤ 10^4
• −10^9 ≤ nums[i] ≤ 10^9
• −10^9 ≤ target ≤ 10^9
• Exactly one valid answer exists.

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
If I stand on nums[i], which exact value would its partner need to have?
2.
Do I need to search the whole array for that partner, or only the part I have already walked past?
3.
The answer asks for indices. What happens to the indices if I sort the array?
4.
How do I make sure an element is not used as its own partner, while [3, 3] with target 6 still works?
5.
Can target − nums[i] overflow an int?

Brute force approach

Idea

An answer is just a pair of positions. Try every pair i < j and return the first one whose values add up to target.

Thinking process

1
The answer is two positions, so the simplest thing is to try all pairs.
2
Start j at i + 1. That way an element is never paired with itself, and each pair is checked once.
3
Add the two values and compare with target.
4
Return as soon as a pair works — the problem promises exactly one.

Code & Implementation

brute.cpp

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();

        // Try every pair (i, j) with i < j, so an element is never paired with itself.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // long long: two values near 10^9 overflow an int when added.
                if ((long long)nums[i] + nums[j] == target) {
                    return {i, j};
                }
            }
        }
        return {};  // never reached: the problem promises one answer
    }
};

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;

        // Try every pair (i, j) with i < j, so an element is never paired with itself.
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                // long cast: two values near 10^9 overflow a 32-bit int when added.
                if ((long) nums[i] + nums[j] == target) {
                    return new int[] { i, j };
                }
            }
        }
        return new int[0]; // never reached: the problem promises one answer
    }
}

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        n = len(nums)

        # Try every pair (i, j) with i < j, so an element is never paired with itself.
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] == target:
                    return [i, j]

        return []  # never reached: the problem promises one answer

export function twoSum(nums: number[], target: number): number[] {
    const n = nums.length;

    // Try every pair (i, j) with i < j, so an element is never paired with itself.
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return []; // never reached: the problem promises one answer
}

Complexity

Time O(N²)Space O(1)

About n²/2 pair checks: 5·10^7 for n = 10^4. That passes here, but the same idea fails as soon as n grows, and interviewers always ask for better.

Better approach

Why brute force is slow

For each element, brute force tries every other element as a partner, even though only one value can work.

What repeated work are we doing?

Each comparison only says "yes" or "no" about one pair. A "no" teaches us nothing about the other pairs, so we keep checking.

What information can we reuse?

After sorting, each "no" rules out a whole element: if a[left] + a[right] < target, then a[left] is too small with every remaining partner. So each step removes one element, and the scan is O(N).

New approach

Idea

Make pairs (value, original index) and sort them by value. Put left at the smallest and right at the largest. If the sum is too small, move left up; if too big, move right down. When it matches, return the two saved indices.

Thinking process

1
Brute force checks pairs that could never work, like the two smallest numbers when the target is large.
2
In a sorted array, the sum of the ends tells me which end is useless: if the sum is too small, the smallest number can't work even with the biggest partner, so drop it.
3
That is the Two Sum II idea. But sorting moves the elements, and the answer must be original indices.
4
So sort (value, index) pairs instead of plain values. The index travels with its value.

Visual

Top row: values after sorting. Bottom row: the original index each value came from.

Sorted pairs + two pointersnums = [5, 3, 8, 6, 1, 4], target = 10step 1/5

nums

index

State

target: 10

Pair each value with its original index

We will sort, so first glue each value to its index. The index must travel with the value.

Code & Implementation

better.cpp

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int n = nums.size();

        // Sort (value, original index) pairs, so we keep the indices we must return.
        vector<pair<int, int>> a(n);
        for (int i = 0; i < n; i++) a[i] = {nums[i], i};
        sort(a.begin(), a.end());

        int left = 0, right = n - 1;
        while (left < right) {
            long long sum = (long long)a[left].first + a[right].first;
            if (sum == target) {
                return {a[left].second, a[right].second};
            } else if (sum < target) {
                left++;   // a[left] is too small even with the largest partner left
            } else {
                right--;  // a[right] is too big even with the smallest partner left
            }
        }
        return {};  // never reached: the problem promises one answer
    }
};

import java.util.Arrays;
import java.util.Comparator;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;

        // Sort (value, original index) pairs, so we keep the indices we must return.
        int[][] a = new int[n][2];
        for (int i = 0; i < n; i++) {
            a[i][0] = nums[i];
            a[i][1] = i;
        }
        Arrays.sort(a, Comparator.comparingInt(x -> x[0]));

        int left = 0, right = n - 1;
        while (left < right) {
            long sum = (long) a[left][0] + a[right][0];
            if (sum == target) {
                return new int[] { a[left][1], a[right][1] };
            } else if (sum < target) {
                left++;  // a[left] is too small even with the largest partner left
            } else {
                right--; // a[right] is too big even with the smallest partner left
            }
        }
        return new int[0]; // never reached: the problem promises one answer
    }
}

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        # Sort (value, original index) pairs, so we keep the indices we must return.
        a = [(val, i) for i, val in enumerate(nums)]
        a.sort(key=lambda x: x[0])

        left, right = 0, len(a) - 1
        while left < right:
            s = a[left][0] + a[right][0]
            if s == target:
                return [a[left][1], a[right][1]]
            elif s < target:
                left += 1   # a[left] is too small even with the largest partner left
            else:
                right -= 1  # a[right] is too big even with the smallest partner left

        return []  # never reached: the problem promises one answer

export function twoSum(nums: number[], target: number): number[] {
    const n = nums.length;

    // Sort (value, original index) pairs, so we keep the indices we must return.
    const a: [number, number][] = nums.map((val, idx) => [val, idx]);
    a.sort((x, y) => x[0] - y[0]);

    let left = 0;
    let right = n - 1;
    while (left < right) {
        const sum = a[left][0] + a[right][0];
        if (sum === target) {
            return [a[left][1], a[right][1]];
        } else if (sum < target) {
            left++;  // a[left] is too small even with the largest partner left
        } else {
            right--; // a[right] is too big even with the smallest partner left
        }
    }
    return []; // never reached: the problem promises one answer
}

Complexity

Time O(N log N)Space O(N)

The sort costs O(N log N) and the pointer scan is O(N). The extra array of pairs is O(N). We can drop the sort completely by remembering earlier values in a map.

Optimized approach

Idea

Start from brute force

Brute force stands on nums[j] and tries every earlier nums[i] to see if nums[i] + nums[j] == target.

Find the repeated work

For a fixed j, only one value can work: target − nums[j]. Yet brute force walks over all earlier elements to find it, and does this again for every j. We can remember the earlier elements in a map instead of walking over them.

Define the state — what variables do I need?

i: The element we are standing on. We look for its partner among the elements before it.
need: `target − nums[i]`: the only value that can pair with `nums[i]`.
seen: Map: value → index, for every element **before** `i`.

Define validity

nums[i] has a partner exactly when target − nums[i] is already in seen. Because seen only holds elements before i, the partner is always a different position.

Define the transitions — when does each pointer move, and why is it safe?

need is in seen

return {seen[need], i}

seen[need] is an earlier, different index whose value plus nums[i] is exactly target.

need is not in seen

seen[nums[i]] = i

No earlier element works with nums[i]. But nums[i] may be the partner of a later element, so remember it. It goes in after the lookup so it can't match itself.

What does the current window add to the answer?

Each step answers one question: "does the current element complete a pair with anything behind it?" The first "yes" is the answer.

Code & Implementation

optimal.cpp

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        // seen[value] = index where we saw that value.
        unordered_map<long long, int> seen;

        for (int i = 0; i < (int)nums.size(); i++) {
            // The partner nums[i] needs. long long: target - nums[i] can leave the int range.
            long long need = (long long)target - nums[i];

            // Look up BEFORE inserting nums[i], so it can't pair with itself.
            auto it = seen.find(need);
            if (it != seen.end()) {
                return {it->second, i};
            }
            seen[nums[i]] = i;
        }
        return {};  // never reached: the problem promises one answer
    }
};

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

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // seen: value -> index where we saw that value
        Map<Long, Integer> seen = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            // The partner nums[i] needs. long: target - nums[i] can leave int range.
            long need = (long) target - nums[i];

            // Look up BEFORE inserting nums[i], so it cannot pair with itself.
            if (seen.containsKey(need)) {
                return new int[] { seen.get(need), i };
            }
            seen.put((long) nums[i], i);
        }
        return new int[0]; // never reached: the problem promises one answer
    }
}

class Solution:
    def twoSum(self, nums: list[int], target: int) -> list[int]:
        # seen[value] = index where we saw that value.
        seen: dict[int, int] = {}

        for i, x in enumerate(nums):
            # The partner nums[i] needs.
            need = target - x

            # Look up BEFORE inserting nums[i], so it cannot pair with itself.
            if need in seen:
                return [seen[need], i]
            seen[x] = i

        return []  # never reached: the problem promises one answer

export function twoSum(nums: number[], target: number): number[] {
    // seen: Map<value, index> where we saw that value
    const seen = new Map<number, number>();

    for (let i = 0; i < nums.length; i++) {
        // The partner nums[i] needs
        const need = target - nums[i];

        // Look up BEFORE inserting nums[i], so it cannot pair with itself
        if (seen.has(need)) {
            return [seen.get(need)!, i];
        }
        seen.set(nums[i], i);
    }
    return []; // never reached: the problem promises one answer
}

Complexity

Time O(N)Space O(N)

One pass with O(1) average map operations. The map holds at most n values.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Check all pairs (i, j) with i < j	O(N²)	O(1)
Better	Sort copies that remember their index, then squeeze from both ends	O(N log N)	O(N)
Optimal	For each x, look up target − x in a map of earlier values; then store x	O(N)	O(N)

Why does this belong to this pattern?

Clues in the problem statement

“two numbers that add up to target”Once you pick one number, the other is fixed: `target − x`. That is a complement lookup.
“return their indices”You must keep original positions. Store `value → index` in the map, and don't sort plain values.
“array is not sorted”Two pointers need sorted order. Without it, use a hash map.
“can't use the same element twice”Look up before inserting, so the map only holds earlier elements.

Pair with an exact sum+unsorted array+need indices→Hash Map — Complement Lookup (value → index)

This is the anchor of the sub-pattern: for each element, compute the one partner it needs and ask the map if that partner was seen before. The next questions keep this shape but change what is stored. Contains Duplicate II stores the last index of each value and the "partner" is the same value nearby. Max Number of K-Sum Pairs stores counts, because each element can be used only once. If the array were already sorted (Two Sum II), two pointers would do it with O(1) space.

Don't make this mistake

Using two pointers on the unsorted array

✗ int l = 0, r = n - 1; while (l < r) { if (nums[l] + nums[r] == target) return {l, r}; if (nums[l] + nums[r] < target) l++; else r--; }

✓ // unsorted → hash map of earlier values if (seen.count(target - nums[i])) return {seen[target - nums[i]], i}; seen[nums[i]] = i;

This is a pattern-confusion trap: the two-pointer move is Two Sum II, where the array is sorted. "Sum too small → move left" is only safe when everything to the right is bigger. On [3, 2, 4], target 6, it checks 3+4=7, moves r, checks 3+2=5, moves l, and stops — it never finds 2+4.

Sorting the values and losing the indices

✗ sort(nums.begin(), nums.end()); // ... two pointers ... return {l, r}; // positions in the SORTED array

✓ vector<pair<int,int>> a; // (value, original index) // sort a, two pointers, then return {a[l].second, a[r].second};

Sorting moves elements, so l and r are positions in the sorted copy, not the original array. On [3, 2, 4], target 6, it returns [0, 2], but the right answer is [1, 2]. Sort (value, index) pairs, or use the map.

Inserting before looking up

✗ seen[nums[i]] = i; if (seen.count(target - nums[i])) return {seen[target - nums[i]], i};

✓ if (seen.count(target - nums[i])) return {seen[target - nums[i]], i}; seen[nums[i]] = i;

When nums[i] is exactly half of target, the lookup finds nums[i] itself. On [3, 2, 4], target 6, it returns [0, 0] — the same element used twice.

Putting every value in the map first

✗ for (int i = 0; i < n; i++) seen[nums[i]] = i; for (int i = 0; i < n; i++) if (seen.count(target - nums[i])) return {i, seen[target - nums[i]]};

✓ for (int i = 0; i < n; i++) if (seen.count(target - nums[i]) && seen[target - nums[i]] != i) return {i, seen[target - nums[i]]};

The two-pass version can work, but only with the extra != i check. Without it, [3, 2, 4] returns [0, 0]. The one-pass "look up, then insert" order gives you that check for free.

Overflow in target − x

✗ int need = target - nums[i];

✓ long long need = (long long)target - nums[i];

With target = −10^9 and nums[i] = 10^9, the result is −2·10^9, which is outside the int range. On LeetCode it is usually fine, but it is undefined behaviour in C++.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Arrays & Hashing translate into production architectures and low-level memory mechanics.

LLD Machine Coding

In-Memory LRU / LFU Cache

Hash map combined with doubly linked list for O(1) eviction and lookup.

Explore Track

C++ Internals

STL unordered_map Internals & Rehashing

Bucket arrays, collision chaining, load factors, and custom hash functors.

Explore Track

Contains Duplicate II