Two Sum II

The problem: given a sorted array and a target, return the positions of the two values that add up to it. Take [1, 3, 4, 5, 7, 11] and a target of 9.

Every pair, as a grid

Lay out every possible pair as a grid: rows are the smaller value, columns the larger. Brute force visits all 15 cells. Two pointers starts at the top-right corner, the smallest value with the largest, and the sum it finds there decides which way to move.

left ╲ right	3	4	5	7	11
1	2	2	2	2	1
3		4	4	3	1
4			✓	3	1
5				3	1
7					1

Each number is the step that ruled that cell out:

11 + 11 = 12, too big. 1 is the smallest value there is, so 11 is too big with anyone. The whole 11 column goes.
21 + 7 = 8, too small. 7 is now the largest value left, so 1 is too small with anyone. The whole 1 row goes.
33 + 7 = 10, too big. The 7 column goes.
43 + 5 = 8, too small. The 3 row goes.
54 + 5 = 9. Found it, at positions 3 and 4.

Five comparisons, and every one deleted an entire row or column of the grid, not a single cell. That's why it's safe: you never throw away a pair you haven't proven can't work. And it's why the array must be sorted: "1 is the smallest" is the sentence that kills the column.

Move the wrong pointer (left when the sum is too big) and you delete a row that might hold the answer, walking straight past it.

One loop, 1-indexed answer

@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)

$O(n)$ time, $O(1)$ space. The classic version wants 1-indexed positions, so add one to each index before returning: a correct walk with the wrong offset still fails every test. The guard is left < right because a pair needs two distinct slots.

When the array isn't sorted

Without order, nothing tells you a value is "the smallest", so no comparison can delete a row. Use a hash map instead: for each value, check whether target - value was already seen. That's $O(n)$ time but $O(n)$ space; sorting first and walking the pointers trades that space for $O(n \log n)$ time.

The grid is worth remembering. 3Sum runs this exact walk once per fixed value, and "closest to target" walks the same grid while tracking the best difference instead of stopping on a match.

Two Sum II - Input Array Is SortedMedium

Two SumEasy

3SumMedium

3Sum ClosestMedium

Two Sum II

Every pair, as a grid

One loop, 1-indexed answer

When the array isn't sorted

The Two Egg Drop Problem: Why the Answer Is 14

Invert This Binary Tree (For a CRUD Job)

Valid Triangle Number

3Sum