22. Two Sum II - Input Array Is Sorted

Q: Why don't we need to consider moving both pointers at once?

If sum target. So only one pointer moves at a time.

easyAsked at Datadog

Find two numbers in a sorted array that add up to a target — using O(1) memory. Datadog uses the two-pointer trick as a building block for problems on sorted metric streams where allocating a hashmap is wasteful.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-20

Source citations

Public interview reports confirming this problem appears in Datadog loops.

Glassdoor (2026-Q1)— Datadog phone screen variant of Two Sum.
LeetCode Discuss (2025-09)— Datadog tagged.

Problem

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target. Return the indices (1-indexed) of the two numbers. Your solution must use only constant extra space.

Constraints

2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
Exactly one solution exists.

Examples

Example 1

Input

numbers = [2,7,11,15], target = 9

Output

[1,2]

Example 2

Input

numbers = [2,3,4], target = 6

Output

[1,3]

Approaches

1. Hashmap (Two Sum I approach)

Same hashmap pattern as unsorted Two Sum.

Time: O(n)
Space: O(n)

function twoSum(numbers, target) {
  const seen = new Map();
  for (let i = 0; i < numbers.length; i++) {
    const need = target - numbers[i];
    if (seen.has(need)) return [seen.get(need) + 1, i + 1];
    seen.set(numbers[i], i);
  }
}

Tradeoff: Ignores the sorted input. Datadog will dock you for not using the structure.

2. Two pointers (optimal)

Left at start, right at end. If sum < target, advance left. If sum > target, retract right. Else return.

Time: O(n)
Space: O(1)

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

Tradeoff: O(1) space — exploits sorted input. Datadog-canonical: the same two-pointer sweep underlies their sorted-stream merge join.

Datadog-specific tips

Datadog grades on whether you spot the sortedness — if you reach for a hashmap when the input is sorted, you've missed the point. Articulate WHY two pointers work: monotonic sweep means we never need to backtrack.

Common mistakes

Forgetting 1-indexing — returning [lo, hi] instead of [lo + 1, hi + 1].
Using <= instead of < in the while loop — would compare an index to itself, violating the 'distinct indices' constraint.
Trying binary search per element — O(n log n), beaten by the two-pointer sweep.

Follow-up questions

An interviewer at Datadog may pivot to one of these next:

3Sum (LC 15) — outer loop + two pointers.
4Sum (LC 18) — two outer loops + two pointers.
Find pairs that differ by K in a sorted stream — symmetric problem.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why don't we need to consider moving both pointers at once?

If sum < target, moving right backward only makes sum smaller — wrong direction. Symmetric argument for sum > target. So only one pointer moves at a time.

What about duplicates?

The problem guarantees one solution. With duplicates, you'd find one of them; the two-pointer sweep doesn't enumerate all pairs.

Practice these live with InterviewChamp.AI

Drill Two Sum II - Input Array Is Sorted and other Datadog interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →