Two Sum

Problem

You are given an array of integers nums and an integer target. Find the two different positions in the array whose values add up exactly to target, and return those two indices (in any order).

You may assume every input has exactly one valid answer, and you cannot use the element at the same index twice (though two equal values at different indices are fine).

Examples

• nums = [2, 7, 11, 15], target = 9 → [0, 1] — because 2 + 7 = 9.
• nums = [3, 2, 4], target = 6 → [1, 2] — 2 + 4 = 6; note you may not use index 0 twice even though 3 + 3 = 6.
• nums = [3, 3], target = 6 → [0, 1] — equal values at two different indices are allowed.

Constraints

• 2 <= nums.length <= 10^4
• -10^9 <= nums[i], target <= 10^9
• Exactly one valid answer exists.

The array is not sorted, and with up to 10^4 elements a quadratic scan is already ~10^8 pair checks — the intended solution is linear.

Think about it first

TL;DR

One-pass hash map — O(n) time, O(n) space.

Approach 1 — Brute force

Try every pair of indices and check whether the values sum to the target.

from typing import List


def twoSum(nums: List[int], target: int) -> List[int]:
    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 []  # unreachable: exactly one answer is guaranteed

Complexity: O(n²) time, O(1) space.

With n up to 10^4 that is ~5·10^7 pair checks: acceptable in C but slow in Python, and not the intended solution.

Approach 2 — Sort + two pointers

In a sorted array, you can find a pair with a given sum in linear time by walking two pointers inward: if the sum is too small, advance the left pointer; if it is too large, retreat the right one. The answer needs the original indices, so sort (value, index) pairs rather than bare values.

from typing import List


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

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

1. Indices sorted by value: order = [1, 0, 2] (values 2, 3, 4).
2. lo=0, hi=2: values 2 + 4 = 6 — match. Return the original indices [1, 2].

Complexity: O(n log n) time for the sort, O(n) space for the index array.

Approach 3 — One-pass hash map

At index i you know the exact value you need: target - nums[i]. A hash map from value to index answers “have I already passed that value?” in O(1). Checking before inserting the current element guarantees the two indices are distinct.

from typing import List


def twoSum(nums: List[int], target: int) -> List[int]:
    seen: dict[int, int] = {}  # value -> index
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

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

1. i=0, num=3: complement 3 not in seen → store {3: 0}.
2. i=1, num=2: complement 4 not in seen → store {3: 0, 2: 1}.
3. i=2, num=4: complement 2 is in seen at index 1 → return [1, 2].

Complexity: O(n) time — one pass, O(1) expected work per element; O(n) space for the map.

Common pitfalls

• Inserting the current element into the map before checking for its complement — with target = 6 and nums = [3, 2, 4] you would wrongly pair index 0 with itself.
• Building a full value → index map first and then failing the duplicate case ([3, 3], target 6): the second 3 overwrites the first, so a naive two-pass lookup returns the same index twice unless you check seen[complement] != i.
• Sorting and returning the sorted positions instead of the original indices.
• Assuming values are positive — they can be negative, so “complement is negative, skip” style shortcuts are wrong.

Pattern takeaway

When a scan needs to answer “have I already seen the thing that completes what I’m holding?”, store what you’ve passed in a hash map keyed by the property you’ll look up. Trading O(n) memory to make membership tests O(1) is the core move of the Arrays & Hashing pattern.