167. Two Sum II - Input Array Is Sorted

The sorted order is a free gift — use it. A left and right pointer squeeze inward from both ends; every step provably eliminates an entire candidate and converges to the answer in a single O(n) pass with O(1) extra space.

● MediumTwo PointersBinary SearchTypeScript

PROBLEM What we're solving

Given a sorted (non-decreasing) 1-indexed integer array numbers and an integer target, find the two numbers that add up to target and return their 1-based indices. Exactly one solution is guaranteed; you may not use the same element twice.

Example: numbers = [2, 7, 11, 15], target = 9. Numbers at indices 1 and 2 give 2 + 7 = 9, so the answer is [1, 2].

KEY IDEA Sorted order lets every comparison eliminate a full candidate

Insight → place one pointer at each end. If their sum is too small, the left element is useless — no right partner can bring it up to target (right is already the largest). Move left++. If the sum is too large, the right element is useless — no left partner can bring it down. Move right--. Each step discards exactly one candidate, and the pointers meet after at most n − 1 moves.

RECIPE Squeeze the pointers inward

0 · Initialize. Set left = 0, right = n − 1 (0-indexed internally; add 1 for the answer). These are the smallest and largest candidates.
1 · Compute sum. sum = numbers[left] + numbers[right].
2a · Hit? If sum === target, return [left + 1, right + 1].
2b · Too small? If sum < target, do left++ — we need a bigger number on the left side.
2c · Too large? If sum > target, do right-- — we need a smaller number on the right.
3 · Repeat until pointers cross. The problem guarantees a unique solution exists, so we will always exit via step 2a.

Classic confusion → returning 0-indexed vs 1-indexed. LeetCode 167 is 1-indexed, so the answer is [left + 1, right + 1]. Do not forget to add 1. Also do not confuse whichpointer to move: a sum that's too small needs a larger value, so advance left (not retreat right).

COST Complexity & alternatives

Brute force (nested loops)

O(n²)

Try every pair — ignores the sorted order entirely.

Two pointers

O(n)

One pass, O(1) space — optimal for sorted input.

Binary search alternative

For each numbers[i], binary-search for target − numbers[i] in the remainder. That is O(n log n) — worse than two pointers but better than brute force. Two pointers wins because the sorted invariant lets us eliminate candidates without restarting the search.

Pattern transfer → the same squeeze works in 3Sum (fix one element, two-pointer the rest), Container With Most Water (move the shorter side), Trapping Rain Water (track left-max / right-max from both ends), and Two Sum IV (BST) (in-order traversal gives a sorted sequence to apply the same idea).

RUN IT Squeeze pointers inward until the sum matches

numbers =target =

step 0 / 3

STARTArray has 4 elements, target is 9. Place left pointer at index 1 and right pointer at index 4 (1-indexed).

1function twoSum(numbers: number[], target: number): number[] {
2▶  let left = 0;
3▶  let right = numbers.length - 1;
4 
5  while (left < right) {
6    const sum = numbers[left] + numbers[right];
7 
8    if (sum === target) {
9      return [left + 1, right + 1]; // 1-indexed answer
10    } else if (sum < target) {
11      left++;  // need a larger sum → advance left
12    } else {
13      right--; // need a smaller sum → retreat right
14    }
15  }
16 
17  return []; // guaranteed a solution exists per constraints
18}

numbers (1-indexed)2172113154

State

left

right

—

sum

target

left pointerright pointerfound pairtarget (constant)

slowfast

TYPESCRIPT The solution, annotated

twoSumII.ts
function twoSum(numbers: number[], target: number): number[] {
  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]; // 1-indexed answer
    } else if (sum < target) {
      left++;  // need a larger sum → advance left
    } else {
      right--; // need a smaller sum → retreat right
    }
  }

  return []; // guaranteed a solution exists per constraints
}

Reading it block by block

Lines 2–3 — place the pointers. left starts at 0 (the smallest element) and right at n − 1 (the largest). Together they span the entire candidate space.

Lines 5–6 — compute the current sum. This is the key comparison: does the pair we are holding right now add up to target?

Lines 8–9 — exact match. Return 1-indexed positions. The +1 converts from 0-based internal indices to the 1-based answer the problem requires.

Lines 10–11 — sum too small. left++ replaces the smallest remaining element with the next one. Because the array is sorted, every element to the right of the new left is also larger, so the sum can only increase or stay the same — no valid pair was skipped.

Lines 12–13 — sum too large. Symmetric argument: right-- swaps in a smaller right partner. The sort guarantee ensures nothing valid is missed on the right side either.

Line 17 — safety return. The problem promises exactly one solution exists, so the while loop always exits via the return on line 9. The final empty array is unreachable in practice but keeps TypeScript happy.

Complexity → O(n) time — each pointer moves at most n − 1 steps total, and the pointers never reverse direction. O(1) space — only two index variables.

INTERVIEWFollow-ups they'll ask

"What if the array is not sorted?" Sort it first (O(n log n)), but then you lose the original indices. Use a hash map instead: for each element store its index, then look up target − x — O(n) time, O(n) space.
"What if there can be duplicate values?"Duplicates are fine — the two-pointer logic doesn't assume uniqueness. The only edge case is if both pointers land on the same index, but left < right prevents that.
"Can you extend this to 3Sum?" Yes — fix one element with an outer loop, then run two pointers on the remaining subarray. Total time O(n²).
"What if multiple valid pairs exist?" Collect all pairs: when sum === target, push the pair and advance both pointers (or handle duplicates with inner loops).
"Trace numbers = [2, 7, 11, 15], target = 9." Step 1: 2 + 15 = 17 > 9 → right--. Step 2: 2 + 11 = 13 > 9 → right--. Step 3: 2 + 7 = 9 → return [1, 2].

OPTIMAL Two Pointers

twoSumII.ts
function twoSum(numbers: number[], target: number): number[] {
  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]; // 1-indexed answer
    } else if (sum < target) {
      left++;  // need a larger sum → advance left
    } else {
      right--; // need a smaller sum → retreat right
    }
  }

  return []; // guaranteed a solution exists per constraints
}

Complexity → O(n) time — each pointer moves at most n − 1 steps total, and the pointers never reverse direction. O(1) space — only two index variables.

ALT 1 Brute force — check every pair

O(n²) time · O(1) space

Ignore the sorted order entirely: test every pair (i, j) with a double loop and return the first that sums to target — a correctness baseline before exploiting the sort.

approach-2.ts
function twoSum(numbers: number[], target: number): number[] {
  const n = numbers.length;
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (numbers[i] + numbers[j] === target) {
        return [i + 1, j + 1]; // 1-indexed answer
      }
    }
  }
  return []; // guaranteed a solution exists per constraints
}

Note → Quadratic because it re-scans the tail for every i and throws away the sorted invariant. Since the array is non-decreasing, two pointers from both ends decide each element in one move, collapsing this to O(n) time and O(1) space.

MNEMONIC The one-liner

"Two ends of a sorted bar — squeeze until they meet the target."

TRIGGERS When you see _ → reach for _

sorted array + find a pair summing to X	two pointers from both ends
sum too small → need bigger	left++ (move toward larger values)
sum too large → need smaller	right-- (move toward smaller values)
3Sum / k-Sum on a sorted array	fix outer elements, two-pointer inner range

SKELETON The reusable shape

skeleton.ts
function twoSum(numbers: number[], target: number): number[] {
  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];
    else if (sum < target) left++;
    else right--;
  }

  return [];
}

FLASHCARDS Tap to flip

Why do two pointers work on a sorted array?

Each move provably eliminates one candidate: if the sum is too small, the left element can never pair with anything to hit the target, so left++ is safe.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For numbers = [2, 7, 11, 15] and target = 9, trace the first step. What is the initial sum and which pointer moves?

QUESTION 02

What is the time complexity of the two-pointer approach?

QUESTION 03

Why is it safe to discard numbers[left] when sum < target?

QUESTION 04

What does LC 167 require you to return?

QUESTION 05

What is the space complexity?

QUESTION 06

Which problem is NOT a direct application of the same two-pointer squeeze?

QUESTION 07

For numbers = [2, 7, 11, 15], target = 9, what is the final answer after all pointer moves?

QUESTION 08

#167 · Two Sum II - Input Array Is SortedThe sorted guarantee lets two pointers squeeze inward: advance the left pointer when the sum is too small, the right when too large — reaching the target in O(n) with O(1) space.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Sorted order lets every comparison eliminate a full candidate

RECIPE Squeeze the pointers inward

COST Complexity & alternatives

Binary search alternative

RUN IT Squeeze pointers inward until the sum matches

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL Two Pointers

ALT 1 Brute force — check every pair

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _