Skip to main content

21. Two Sum II - Input Array Is Sorted

easyAsked at Ola

Find two indices in a sorted array whose values sum to a target using O(1) extra space.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a 1-indexed array of integers numbers sorted in non-decreasing order, find two numbers such that they add up to a specific target. Return their 1-based indices.

Constraints

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • 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. Hash map

Ignore the sort and use a complement hash.

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

Tradeoff:

2. Two pointers

lo and hi shrink inward based on whether the sum is too low or too high. O(n) and O(1) space.

Time
O(n)
Space
O(1)
function twoSum(numbers, target) {
  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--;
  }
}

Tradeoff:

Ola-specific tips

Ola uses this to see if you exploit sorted input; tie it to scanning a sorted ETA table from both ends to fit a budget pickup window.

Solve it now

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

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →