Skip to main content

15. Two Sum II - Input Array Is Sorted

easyAsked at Square

Given a sorted list of settled transaction amounts, find two that match a target refund — Square's refund-matching engine does exactly this to pair a chargeback against two split payments without rescanning the ledger.

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

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 number. Return the indices of the two numbers as an integer array [index1, index2] where 1 <= index1 < index2 <= numbers.length. You may not use the same element twice, and there is exactly one solution. You must use O(1) extra space.

Constraints

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

Examples

Example 1

Input
numbers = [2,7,11,15], target = 9
Output
[1,2]

Explanation: numbers[0] + numbers[1] = 2 + 7 = 9. Return [1, 2] (1-indexed).

Example 2

Input
numbers = [2,3,4], target = 6
Output
[1,3]

Approaches

1. Brute force

Check every pair. Correct but wastes the sorted property.

Time
O(n^2)
Space
O(1)
function twoSumII(numbers, target) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) return [i + 1, j + 1];
    }
  }
}

Tradeoff:

2. Two pointers

Use the sorted order: left pointer at start, right at end. If sum too large, shrink right; too small, advance left. O(n) time, O(1) space — the constant-space requirement is the key constraint.

Time
O(n)
Space
O(1)
function twoSumII(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:

Square-specific tips

Square interviewers care that you don't burn extra memory. State upfront that the sorted input lets you use two pointers at O(1) space — that signals you read constraints, not just pattern-match. They'll often follow with: 'what if the array weren't sorted?' so be ready to pivot to a hash map with the tradeoff explained.

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 Square interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →