Skip to content
ΣDSA Patterns
Menu
PatternsProblemsTemplatesRoadmapResourcesMathReviewsAbout
Language
EnglishTürkçe

Two Pointers

Guide 6 of 6 · Path 6 of 6

← PreviousNext pattern: Fast & Slow Pointers →

Interactive

Mental model

A worked animation for this problem. Scrub steps or press space to pause; re-tell the invariant out loud.

Step 1 of 6
2
7
11
15

target = 9

Sorted 1-indexed array. Pair that sums to 9. Exactly one answer.

Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Mediumtwo-pointers

Two Sum II. Input Array Is Sorted

Problem (restated)

Given a 1-indexed sorted array of integers, find two numbers that add up to target. Return their 1-based indices. Exactly one solution exists.

Intuition

Sorted order lets the larger end decrease the sum and the smaller end increase it. one pass from both ends.

Approaches

Two pointers from ends

Unverified
Time O(n)Space O(1)

Idea. lo at start, hi at end. If sum too small, lo++. If too large, hi–. Else return 1-based indices.

Walkthrough. numbers=[2,7,11,15], target=9 → 2+15 too big, 2+11 too big, 2+7=9 → [1,2].

Trade-offs. Faster than hash map when input is sorted and constant extra space is required.

Solution
export function twoSum(numbers: number[], target: number): number[] {
  let lo = 0, hi = numbers.length - 1;
  while (lo < hi) {
    const s = numbers[lo]! + numbers[hi]!;
    if (s === target) return [lo + 1, hi + 1];
    if (s < target) lo++;
    else hi--;
  }
  return [-1, -1];
}

export function twoSum(numbers: number[], target: number): number[] {
  let lo = 0, hi = numbers.length - 1;
  while (lo < hi) {
    const s = numbers[lo]! + numbers[hi]!;
    if (s === target) return [lo + 1, hi + 1];
    if (s < target) lo++;
    else hi--;
  }
  return [-1, -1];
}

Template connection

Sorted two-sum: opposite-end two pointers, no hash map needed.

Reflection