Two Sum II Input Array Is Sorted

MEDIUM✓ CHIP-TIMEDLC #167 — FULL STATEMENT ↗

The drill: The sorted remix of Two Sum: find the one pair of values adding to the target and report their 1-indexed positions. Sortedness is the license to trade the hash map for two pointers and constant memory.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A sorted array of values and a target sum arrive together, and somewhere in that array sit exactly two positions whose values add to the target — the job is to report those two positions.

Positions are reported using 1-indexed numbering rather than the usual 0-indexed style, and the smaller index always comes first in the answer.

Every input on this course is built so exactly one valid pair exists, and a position can never pair with itself even if its value could technically double to the target.

EX 01

numbers = [1, 3, 6, 10] · target = 9

→ [2, 3]

PAIR IN THE MIDDLE

EX 02

numbers = [2, 7, 9] · target = 16

→ [2, 3]

PAIR AT THE RIGHT EDGE

EX 03

numbers = [-5, 1, 4] · target = -1

→ [1, 3]

NEGATIVE PLUS POSITIVE ACROSS THE ARRAY

array holds between two and a few thousand values
values arrive already sorted in non-decreasing order
exactly one valid pair exists per input on this course
reported indexes are 1-indexed, smaller index first

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

The hash-map answer from the original Two Sum still works here, but it ignores the headline: this array arrives sorted. Sorted input usually refunds the map's memory.

HINT 2 THE STRUCTURE

Stand at both ends and add. The sum tells you something certain: too small means the left value can pair with nothing at all, too big means the same about the right value.

HINT 3 ONE STEP FROM THE ANSWER

Advance the left pointer on a small sum, retreat the right on a big one — each comparison permanently retires one element. The guaranteed pair is found before the pointers ever cross.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE PINCERPATTERN · TWO POINTERS ON SORTED INPUTnumbers = [1, 3, 6, 10] · target = 9

STEP 1

L at 0 (value 1), R at 3 (value 10). Target 9.

STEP 1 / 5 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/two-sum-ii-input-array-is-sorted.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1
        while l < r:
            total = numbers[l] + numbers[r]
            if total == target:
                return [l + 1, r + 1]  # 1-indexed
            if total < target:
                l += 1
            else:
                r -= 1
        return []

TIME O(N)SPACE O(1)PYTHON · RACE PACE · 12 LN

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            for j in range(i + 1, n):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]  # 1-indexed
        return []

TIME O(N²)SPACE O(1)PYTHON · TRAINING PACE · 8 LN

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int total = numbers[l] + numbers[r];
            if (total == target) {
                return new int[] { l + 1, r + 1 }; // 1-indexed
            }
            if (total < target) {
                l++;
            } else {
                r--;
            }
        }
        return new int[] {};
    }
}

TIME O(N)SPACE O(1)JAVA · RACE PACE · 17 LN

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            for (int j = i + 1; j < numbers.length; j++) {
                if (numbers[i] + numbers[j] == target) {
                    return new int[] { i + 1, j + 1 }; // 1-indexed
                }
            }
        }
        return new int[] {};
    }
}

TIME O(N²)SPACE O(1)JAVA · TRAINING PACE · 12 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED