Two Sum II

In one line

Walk in from both ends of a sorted array: the sum tells you exactly which side is hopeless, and only one direction can ever help.

time O(n)space O(1)

Given a sorted array and a target, find the pair of values that adds up to it, and return their positions. A brute-force scan checks every pair: that's $O(n^2)$ , and it never uses the fact that the array is sorted.

Two pointers gets it down to a single pass. It starts at the two ends and proves, at every step, that one of them can be discarded for good.

Why the sum tells you which pointer to move

Discard the extreme pointer

If the sum is too big, the right value is too big to pair with left. And since left is already the smallest value left in play, that value is too big for every remaining candidate.
If the sum is too small, the same argument runs in reverse: the left value is too small to pair with anything left of right.
Each comparison rules out an entire diagonal of pairs, not just the one just tested.

What it does not prove

It doesn't say the pointer's next position is the answer, only that keeping the old one is hopeless.
It needs a single, fixed target and a total order (>/<) to compare against. It doesn't extend to "closest sum" without tracking a running best instead of stopping early.

Signals in the problem statement

"sorted array" or "input array is sorted"
a single target sum, with exactly one valid pair guaranteed
asked to return positions/indices, not just whether a pair exists
"constant extra space" ruling out a hash map

The pattern

1Place pointers at index 0 and n - 1.
2Compare the sum at the current pair against the target.
3
Sum too big → move right left. Sum too small → move left right.
4Stop when the pointers meet, or the sum matches.

@itsnas two-sum.ts

codetwo-sum.ts

// Returns 1-indexed positions, per the sorted Two Sum convention.
function twoSum(
  numbers: number[],
  target: number,
): [number, number] | null {
  let left = 0
  let right = numbers.length - 1
 
  while (left < right) {
    const sum = numbers[left] + numbers[right]
    if (sum === target) return [left + 1, right + 1]
    if (sum < target) left++ // left is too small for anything remaining
    else right-- // right is too big for anything remaining
  }
 
  return null
}

main

Nas (@itsnas)

fn two_sum(numbers: &[i32], target: i32) -> Vec<i32> {
    let (mut left, mut right) = (0usize, numbers.len() - 1);
 
    while left < right {
        let sum = numbers[left] + numbers[right];
        if sum == target {
            return vec![(left + 1) as i32, (right + 1) as i32];
        } else if sum < target {
            left += 1;
        } else {
            right -= 1;
        }
    }
 
    vec![]
}

main

Nas (@itsnas)

std::vector<int> twoSum(std::vector<int>& numbers, int target) {
  int left = 0, right = numbers.size() - 1;
 
  while (left < right) {
    int sum = numbers[left] + numbers[right];
    if (sum == target) return {left + 1, right + 1};
    else if (sum < target) left++;
    else right--;
  }
 
  return {};
}

main

Nas (@itsnas)

// Returns 1-indexed positions, per the sorted Two Sum convention.
func twoSum(numbers []int, target int) (int, int, bool) {
	left, right := 0, len(numbers) - 1
 
	for left < right {
		sum := numbers[left] + numbers[right]
		switch {
		case sum == target:
			return left + 1, right + 1, true
		case sum < target:
			left++ // left is too small for anything remaining
		default:
			right-- // right is too big for anything remaining
		}
	}
 
	return 0, 0, false
}

main

Nas (@itsnas)

def two_sum(
    numbers: list[int], target: int
) -> tuple[int, int] | None:
    # Returns 1-indexed positions, per the sorted Two Sum convention.
    left, right = 0, len(numbers) - 1
 
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return left + 1, right + 1
        if total < target:
            left += 1  # left is too small for anything remaining
        else:
            right -= 1  # right is too big for anything remaining
 
    return None

main

Nas (@itsnas)

Complexity

Time

O (n)

Each element is visited at most once as the pointers close in.

Space

O (1)

Just the two indices, no hash map, no auxiliary array.

The unsorted version of this problem needs a hash map: $O(n)$ time but also $O(n)$ space. Sorting first (if it isn't already) trades that space back for $O(n \log n)$ up front.

Common pitfalls

1
Off-by-one on the return format
The classic sorted Two Sum asks for 1-indexed positions, not array indices: a correct pointer walk with the wrong offset still fails every test.
2
Moving the wrong pointer
Moving left when the sum is too big (or right when it's too small) inverts the invariant and can walk straight past the answer without ever detecting it.
3
Using `left <= right` as the loop guard
A pair needs two distinct indices: letting the pointers land on the same slot means checking a value against itself.
4
Assuming order that isn't there
If the input isn't actually sorted by value (or is sorted by something else, like original index), the pointers silently give the wrong answer instead of an error.

Variants worth knowing

1
Unsorted Two Sum: no order to exploit, so trade the $O(1)$ space for a hash map instead.
2
3Sum: fix one value, then run this exact pattern on the rest with a moving target.
3
Closest to target: track the best difference seen so far instead of stopping at an exact match.

Practice, easiest first

Two Sum II - Input Array Is SortedMedium

Two SumEasy

3SumMedium

3Sum ClosestMedium

Two Sum II

Why the sum tells you which pointer to move

The pattern

Complexity

Common pitfalls

Variants worth knowing

Practice, easiest first

What's next in the notebook?

Valid Triangle Number

3Sum

Container With Most Water

Two Pointers