FAANGPrep Sprint

Two Sum II - Input Array Is Sorted

The integer array numbers is sorted in non-decreasing order and indexed from 1. Find the two entries whose sum equals target and return their positions.

MediumSolve on LeetCode

Examples

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

Output:[1,2]

Explain:

2 + 7 = 9, and those values sit at positions 1 and 2 counting from 1, so the answer is [1, 2].

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

Output:[1,3]

Explain:

2 + 4 = 6, at positions 1 and 3 counting from 1, so the answer is [1, 3].

Problem Understanding

This is similar to the classic Two Sum, but with two key differences:

The array is already sorted.
You must return 1-based indices.

A brute force approach would be to check every pair, which is O(n²). However, the sorted property allows us to use the Two Pointers technique to solve it in linear time O(n).

Algorithm Strategy

Initialize left at the start (index 0) and right at the end (index n-1).
Calculate current_sum = numbers[left] + numbers[right].
If current_sum == target, we found the pair! Return [left + 1, right + 1].
If current_sum < target, we need a larger sum. Since the array is sorted, moving left to the right increases the sum.
If current_sum > target, we need a smaller sum. Moving right to the left decreases the sum.

Interactive Visualization

TARGET 9

START AT THE ENDS

Left

Right

Sum

—

Returns

—

Target 9: left starts at index 0, right at index 3

numbers[0] + numbers[3] = 2 + 15 = 17

Sorted array

Target

Legend & Complexity

The values under L and R being added

The pair that sums to the target

Values outside the pointers: ruled out

Time

O(n)

Space

O(1)

Each step adds the values under L and R and moves one pointer toward the target; values outside the pointers are struck out, because no answer can use them.

Dry Run: nums = [2, 7, 11, 15], target = 9

Iteration	Left (Index/Val)	Right (Index/Val)	Sum (L+R)	Comparison	Action
1	0 / 2	3 / 15	17	17 > 9 (Too Big)	Decrement Right
2	0 / 2	2 / 11	13	13 > 9 (Too Big)	Decrement Right
3	0 / 2	1 / 7	9	9 == 9 (Match!)	Return `[1, 2]`

Edge Cases & Common Mistakes

Edge Cases:

No Solution: Ensure your code handles cases where no pair sums to the target (return empty vector/array).
Array Constraints: Typically length >= 2.

Common Mistakes:

0-based vs 1-based: The problem asks for 1-based indices. Returning [left, right] instead of [left+1, right+1] is a frequent bug!
Not using Sorted Property: Using a Hash Map (O(n) space) works but is explicitly suboptimal when O(1) space is required.

Solution

Two Sum II - Input Array Is Sorted Code

1/**
2 * @param {number[]} numbers
3 * @param {number} target
4 * @return {number[]}
5 */
6var twoSum = function(numbers, target) {
7    let left = 0;
8    let right = numbers.length - 1;
9    
10    while (left < right) {
11        let sum = numbers[left] + numbers[right];
12        
13        if (sum === target) {
14            return [left + 1, right + 1];
15        } else if (sum < target) {
16            left++;
17        } else {
18            right--;
19        }
20    }
21    
22    return [];
23};

Next Problem

Container With Most Water