Skip to main content
DSA patterns

Two Sum II - Input Array Is Sorted

mediumTwo pointers Must-do

Problem statement

You are given a list of integers numbers that is sorted from smallest to largest, and a number 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.

Your solution may use only a constant amount of extra memory.

Examples

Example 1

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

Output: [1, 2]

Explanation: 2 (position 1) plus 7 (position 2) is 9. The positions are counted from 1.

Example 2

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

Output: [1, 3]

Explanation: 2 (position 1) plus 4 (position 3) is 6. The pair does not have to be next to each other.

Hints

Hint 1: Checking every pair works, but it ignores the fact that the list is sorted. Ask what the sorting could let you skip.

Approach

Optimal: Two pointers

Intuition

Put one finger on the smallest value (the start) and one on the largest (the end). Look at their sum. If it is too small, the left value is too small to pair with anything: even the biggest value still available is not enough. So the left finger can safely move right to a bigger value. If the sum is too big, the right value is too large to pair with anything, so the right finger moves left. Each move throws away one value that can never be part of the answer, so no pair is missed.

Steps

  1. Set left = 0 and right = n - 1.
  2. While left < right, compute total = numbers[left] + numbers[right].
  3. If total == target, return [left + 1, right + 1].
  4. If total < target, move left one step right.
  5. If total > target, move right one step left.

Dry run

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

step left right total action
1 0 3 17 too big → right moves left
2 0 2 13 too big → right moves left
3 0 1 9 match → return [1, 2]

Edge cases: a list of exactly two values is checked in one step. Negative numbers and duplicates need no special handling, because only the sorted order is used.

Complexity

Time O(n) - Every step moves either `left` right or `right` left, and the two pointers never cross. So there are at most n steps in total. Each step does one addition and one comparison.

Space O(1) - Only the two pointers and the current sum are stored. The list is not copied or changed. This is the memory limit the problem asks for.

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 []


if __name__ == "__main__":
    print(Solution().twoSum([2, 7, 11, 15], 9))
    print(Solution().twoSum([2, 3, 4], 6))
RecapThe whole problem in a few lines, for the night before
  • Spot it: find two numbers that add up to a target in a sorted array
  • Idea: two pointers at both ends; if the sum is too small move the left one right, if too big move the right one left
  • Cost: O(n) time, O(1) space
  • Trap: the answer is 1-indexed; a hash map works but wastes the O(1) space the sorted order gives you

Interview follow-ups

  • Return every distinct pair of values that adds up to the target.

    Keep the two pointers, but do not stop at the first match. When the sum equals the target, record the pair, then move left forward and right back, and keep moving each one past values equal to the one just used. This skips duplicate pairs. When the sum is too small or too big, move a pointer as before. Time is O(n) plus the size of the output, and space is O(1) besides the output. This is the inner loop of 3Sum.

  • Count the pairs whose sum is less than or equal to the target.

    Use the same pointers. If numbers[left] + numbers[right] <= target, then left pairs with every position from left + 1 to right, so add right - left to the count and move left forward. Otherwise move right back. Each step moves a pointer, so the time is O(n) with O(1) space. The count can be large, so use a 64-bit integer.

Frequently asked questions

The hash map version also runs in O(n) time, but it needs O(n) extra memory to remember the values it has seen. This problem asks for constant extra space. The sorted order lets two pointers reach the same speed with O(1) memory, so the hash map is correct but breaks the rule.

Returning 0-based positions. This problem counts from 1, so you must add 1 to both indices before returning. The second most common bug is writing left <= right, which can use the same value twice. The loop must stop when left == right.

Say the sum is too small. Then numbers[left] plus the biggest value still available is not enough. Any other partner for numbers[left] would be smaller or equal, so it is also not enough. That means numbers[left] cannot be in any answer, and dropping it loses nothing. The same argument works for right when the sum is too big.

Any time two sorted streams are compared or combined: merging sorted log files by timestamp, or diffing two sorted lists of resources such as instance IDs. At each step you move the pointer on the smaller side, which is the same decision as here.