Algorithm

Two Sum

Arrays & Strings Pattern

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.

CONSTRAINTS
  • 2 <= nums.length <= 10⁴
  • -10⁹ <= nums[i] <= 10⁹
  • -10⁹ <= target <= 10⁹
  • Exactly one valid answer exists
EXAMPLE 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
2 + 7 = 9, and the two values sit at different positions. The answer is the pair of indices [0, 1], not the values themselves.
EXAMPLE 2
Input: nums = [3,2,4], target = 6
Output: [1,2]
2 + 4 = 6. Note that [0, 0] would be wrong even though 3 + 3 = 6 — that would use the element at index 0 twice.
EXAMPLE 3
Input: nums = [3,3], target = 6
Output: [0,1]
Two different elements happen to hold the same value 3. Using both is allowed, because they are different positions.
Can I use the same element twice?
No — the two indices must be different. A single 3 cannot pair with itself to reach 6, but two 3s at different indices (as in [3, 3]) are a perfectly valid answer.
Is the array sorted?
No, assume no ordering. Always worth confirming: on a sorted array a different approach that uses no extra memory becomes possible — that variation appears as the follow-up problem, Two Sum II.
Can the numbers be negative, or appear more than once?
Yes to both. Values go down to -10⁹, and the same value may appear at several indices.
What if there are multiple valid answers?
The problem guarantees exactly one solution exists, so you never have to choose between pairs — and never have to handle a no-answer case.

Finding a pair of numbers that adds up to a specific target is a classic search problem. The goal is to identify the indices of two distinct elements that, when combined, satisfy the target sum requirement.

Search Every Pair (O(N²))

The most straightforward approach is to check every possible pair of numbers. We use one loop to pick the first number and a second loop to scan the rest of the array for a partner.

python
for i in range(len(nums)):
    for j in range(i + 1, len(nums)):
        if nums[i] + nums[j] == target:
            return [i, j]
Finding the Complement

The O(N²) approach is slow because we perform a full linear scan just to find one specific value (the complement). The core insight is that if we know our current value is x, we are looking for exactly one specific partner: target - x.

Hash Map Memory (O(N))

Instead of scanning for the partner, we can "remember" every number we've already seen. We use a Hash Map to store values as keys and their indices as values. As we walk through the array, we check if the current number's "required partner" is already in our memory.

python
seen = {}
for i, x in enumerate(nums):
    partner = target - x
    if partner in seen:
        return [seen[partner], i]
    seen[x] = i
Worked Example:[2, 7, 11, 15], target 9
0
2
i
1
7
2
11
3
15
We look at the number 2. The complement we need is 7 (9 minus 2), which is not yet in our memory map. We record that 2 is located at index 0 and move forward.
0
2
1
7
i
2
11
3
15
We look at the number 7. The complement we need is 2 (9 minus 7). Since 2 is already stored in our memory map at index 0, we have found our pair and return the indices [0, 1].
Interactive Strategy Visualization

One-Pass Hash Map

Checking for complement while iterating

ARRAY
CUR
2
0
5
1
9
2
11
3
3
4
6
5
HASH MAP (Val → Idx)
Empty
CURRENT
2
NEED
7
Current: 2. Target: 9. Need: 9 - 2 = 7. Check Map.

Key Insight

We can iterate through the array once. For each element, we calculate the complement (Target - Current). If this complement is already in our hash map, we found the pair!

Time & Space

Time: O(N) because we traverse once. Space: O(N) because the hash map stores up to N elements.

O(N²) Time · O(1) Space
→
O(N) Time · O(N) Space