167. Two Sum II - Input Array Is Sorted

Quick Identifier

Topic: two-pointers
Pattern: sorted target sum from both ends
Difficulty: Medium
Companies: Amazon, Google, Meta, Apple, Adobe
Frequency: High
LeetCode: 167
Hint: Too small means move left right; too large means move right left.

Quick Sights

Time Complexity: O(n) - one pointer moves each iteration.
Space Complexity: O(1) - only indexes are stored.
Core Mechanism: Use sorted order to steer pointer movement until the target pair is found; return 1-based indices.

Concept Explanation

The sorted array makes the current sum meaningful. With the smallest remaining value on the left and largest on the right, the sum tells us how to move.

If the sum is too small, moving right left can only reduce it, so we must move left right. If the sum is too large, move right left. That is the discard rule.

Diagram

This diagram shows the pointer decisions and the step-by-step algorithm flow.

Loading diagram…

Study Pattern (SDE3+)

0-3 min: Name the pointer shape, then state the invariant and discard rule before coding.
Implementation pass: Keep pointer movement explicit; every branch must return, record an answer, or move at least one pointer.
5 min extension: Explain how the solution changes for immutable input, streaming input, many duplicate values, or many repeated queries.

Approaches

Hash map ignores the sorted property and uses space. Binary search per index is O(n log n). Two pointers are O(n) and O(1).

Optimal Solution

JavaScript

function twoSum(numbers, target) {
	let left = 0, 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++;
		else right--;
	}
	return [];
}

Go

func twoSum(numbers []int, target int) []int {
	left, right := 0, len(numbers)-1
	for left < right {
		sum := numbers[left] + numbers[right]
		if sum == target { return []int{left + 1, right + 1} }
		if sum < target { left++ } else { right-- }
	}
	return nil
}