Two Sum II - Input Array Is Sorted

Q: Why not use the hash map from the original Two Sum?

It works in O(n) time, but it needs O(n) extra memory. The sorted order lets two pointers reach the same time with O(1) space, which is what this version asks for.

Q: What is the most common bug?

Returning 0-based positions. This problem counts from 1, so add 1 to both indices.

Q: Where do two pointers on sorted data show up in infra work?

Any time two sorted streams are compared or combined: merging sorted log files by timestamp, or diffing two sorted lists of resources. Moving the pointer on the smaller side is the same decision.

mediumTwo pointers Must-do

You are given a list of integers numbers sorted in non-decreasing order, and a target. Exactly one pair of different positions has values that add up to target. Return those two positions as [i, j] with i < j, counting positions from 1, not 0.

Use only constant extra space.

Examples

Example 1

Input: numbers = [1, 3, 4, 6, 9], target = 13

Output: [3, 5]

Explanation: 4 (position 3) + 9 (position 5) = 13.

Example 2

Input: numbers = [-4, -1, 0, 5], target = -1

Output: [2, 3]

Explanation: -1 (position 2) + 0 (position 3) = -1.

Hints

Approach

Put left at the smallest value and right at the largest. Their sum tells you which way to move.

Compute sum = numbers[left] + numbers[right].
If it equals the target, return [left + 1, right + 1].
If it is too small, move left right to get a bigger value.
If it is too big, move right left to get a smaller value.

Why nothing is missed: when the sum is too small, numbers[left] cannot pair with anything, because right is already the largest value still available. So it is safe to drop it. The same argument applies to right when the sum is too big.

ComplexityTime O(n)Space O(1)

Python

class Solution:
    def twoSum(self, numbers: list[int], target: int) -> list[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            if total < target:
                left += 1
            else:
                right -= 1
        return []

Follow-up questions

Return every distinct pair of values that sums to the target.
Count pairs whose sum is less than or equal to the target.

Frequently asked questions

It works in O(n) time, but it needs O(n) extra memory. The sorted order lets two pointers reach the same time with O(1) space, which is what this version asks for.

Returning 0-based positions. This problem counts from 1, so add 1 to both indices.

Any time two sorted streams are compared or combined: merging sorted log files by timestamp, or diffing two sorted lists of resources. Moving the pointer on the smaller side is the same decision.

Problem statement