How do you solve Two Sum II - Input Array Is Sorted?

Use two pointers, left and right, starting at the array's ends. In each iteration, compute the sum of numbers[left] and numbers[right]. If sum equals target, return the 1-based indices. If sum is greater than target, decrement right pointer. If sum is less than target, increment left pointer. This guarantees finding the solution in a single pass with O(n) time and O(1) space.

Two Sum II - Input Array Is Sorted

Q: What is the time complexity of Two Sum II - Input Array Is Sorted?

O(n). Each pointer moves at most n times, resulting in a single linear pass through the array.

Q: What pattern does Two Sum II - Input Array Is Sorted use?

The Pattern: Two Pointers (Greedy Contraction) The Heuristic: The logic of any optimal Two Pointers solution lies in finding the condition that allows you to permanently discard one end of the search space by moving the pointer that is the current 'limiting factor' to the solution.

Easy Two Pointers

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] of length 2, where 1 <= index1 < index2 <= numbers.length. You may assume that each input would have exactly one solution and you may not use the same element twice.

2 ≤ numbers.length ≤ 3 * 10⁴
−1000 ≤ numbers[i] ≤ 1000
numbers is sorted in non-decreasing order
−1000 ≤ target ≤ 1000
Exactly one valid answer exists

Example

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

Output: [1, 2]

Starting with pointers at the beginning (index 0) and end (index 3) of the array, the algorithm calculates the sum: 2 + 15 = 17, which is greater than the target 9. Since the array is sorted, decreasing the right pointer moves to a smaller number. Moving right pointer from index 3 to 2, sum becomes 2 + 11 = 13, still greater than 9. Move right pointer again to index 1, sum is 2 + 7 = 9, which matches the target. The algorithm returns [1, 2] (1-indexed). The critical insight is that the sorted property allows discarding one pointer at each step, avoiding a quadratic search.

Approach

Straightforward Solution

A brute-force approach checks all pairs with nested loops, resulting in O(n^2) time complexity, which is inefficient for large arrays.

Core Observation

Because the array is sorted, the sum of two numbers can be compared to the target to decide which pointer to move. If the sum is too large, moving the right pointer left decreases the sum; if too small, moving the left pointer right increases the sum.

Path to Optimal

Preview

The sorted property enables a two-pointer approach. Initialize one pointer at the start and one at the end…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use two pointers, left and right, starting at the array's ends. In each iteration, compute the sum of numbers[left] and numbers[right]…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each pointer moves at most n times, resulting in a single linear pass through the array.

Space

O(1)

Only two pointer variables and a few auxiliary variables are used, independent of input size.

Pattern Spotlight

Two Pointers (Greedy Contraction)

The logic of any optimal Two Pointers solution lies in finding the condition that allows you to permanently discard one end of the search space by moving the pointer that is the current 'limiting factor' to the solution.

Solution

Python

1class Solution:
  def twoSum(self, numbers: list[int], target: int) -> list[int]:
      l, r = 0, len(numbers) - 1
4
      while l < r:
          current_sum = numbers[l] + numbers[r]
          
          if current_sum > target:
              r -= 1
          elif current_sum < target:
              l += 1
          else:
              return [l + 1, r + 1]

Step-by-Step Solution

Initialize Left and Right Pointers at Array Boundaries

3	`l, r = 0, len(numbers) - 1`

Objective

To set up two pointers at the start and end of the sorted array to begin the search for the target sum.

Key Insight

Starting pointers at the extremes leverages the sorted order to evaluate the largest and smallest elements first, enabling a greedy contraction of the search space based on the sum comparison with the target.

Interview Quick-Check

Core Logic

Initializing pointers at the array boundaries sets the widest possible range to evaluate sums, enabling efficient contraction.

State & Boundaries

Pointers must be valid indices within the array, starting at 0 and len(numbers) - 1.

Iteratively Adjust Pointers Based on Sum Comparison

To move pointers inward based on whether the current sum is greater or less than the target, narrowing down to the correct pair.

Return 1-Based Indices of the Found Pair

To return the indices of the two numbers that sum to the target, adjusted for 1-based indexing as required by the problem.

2 more steps with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 3 Critical

l, r = 0, len(numbers) - 1

Initialize left and right pointers at the start and end of the array.

Setting pointers at the array boundaries leverages the sorted order to evaluate the largest and smallest elements first, enabling efficient contraction of the search space.

Line 5 Critical

while l < r:

Begin a loop that continues while left pointer is less than right pointer.

The loop condition ensures that the two pointers do not cross, maintaining the invariant that the pointers reference distinct elements.

Full line-by-line criticality + rationale for all 9 lines available on Pro.

Test Your Understanding

Why does moving the pointer at the side that causes the sum to be too large or too small guarantee finding the solution without missing any valid pairs?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Two Sum II - Input Array Is Sorted from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Two Sum II - Input Array Is Sorted drill

or drill a free problem

1	`class Solution:`
2	`def twoSum(self, numbers: list[int], target: int) -> list[int]:`
3	`l, r = 0, len(numbers) - 1`
4
5	`while l < r:`
6	`current_sum = numbers[l] + numbers[r]`
7
8	`if current_sum > target:`
9	`r -= 1`
10	`elif current_sum < target:`
11	`l += 1`
12	`else:`
13	`return [l + 1, r + 1]`