Skip to main content

167 - Two Sum II (Input Array Is Sorted)

Difficulty: Medium | Pattern: Two Pointers | Company tags: Amazon, Facebook, Apple

Problem Statement​

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 (1-indexed) as an integer array of length 2.

You may assume that each input has exactly one solution, and you may not use the same element twice.

You must use only O(1) extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: 2 + 7 = 9, return [1, 2]

Example 2:

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

Approach: Two Pointers — O(n), O(1)​

Key insight: The array is sorted. Start with two pointers at each end. If the sum is too small, move left pointer right (increase sum). If too large, move right pointer left (decrease sum). Guaranteed to find the answer.

Algorithm Flow​

def twoSum(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]  # 1-indexed
        elif total < target:
            left += 1
        else:
            right -= 1
    
    return []  # guaranteed to find solution per problem

Dry Run​

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

leftrightsumaction
0 (2)3 (15)1717 gt target, right--
0 (2)2 (11)1313 gt target, right--
0 (2)1 (7)9match! return [1,2]

Why Two Pointers Work on Sorted Array​

  • Sorted array means: increasing left pointer always increases the sum; decreasing right pointer always decreases it.
  • We never need to backtrack — each step strictly moves toward the answer.
  • Unlike LC 1 (Two Sum), the sort order lets us avoid the hash map and achieve O(1) space.

Comparison with LC 1 - Two Sum​

Two Sum (1)Two Sum II (167)
Inputunsortedsorted
SpaceO(n) hash mapO(1)
TimeO(n)O(n)

Edge Cases​

  • Two-element array → only one pair to check
  • Target = 2×first element? Not possible (same element can't be used twice)
  • Negative numbers → algorithm still works (same logic)

Complexity​

  • Time: O(n)
  • Space: O(1)

Key Terms​

TermDefinition
Two pointersTwo indices scanning the array from opposite ends (or same direction) to narrow a search space in one pass.
Monotonic sumThe property that moving the left pointer right only increases the sum, and moving the right pointer left only decreases it, on a sorted array.
1-indexedThe problem's output convention where the first element is index 1, not 0 — a common off-by-one trap.
In-place / O(1) spaceSolving without allocating auxiliary structures like a hash map, relying instead on array order.
Sorted invariantThe precondition (non-decreasing order) that makes two-pointer convergence correct and complete.

FAQ​

Q: Why does the two-pointer approach only work because the array is sorted? A: Sorting guarantees a monotonic relationship between pointer position and sum — increasing left strictly increases the sum, decreasing right strictly decreases it. Without sorted order, moving a pointer wouldn't predictably move the sum toward the target, so you'd need a hash map instead.

Q: Can this be solved without extra space if the array is not sorted? A: No — for an unsorted array (LC 1), you need O(n) space (a hash map) to achieve O(n) time, or O(n log n) time if you sort a copy first (which costs O(n) space unless sorting in place, but that loses original indices).

Q: What if there are duplicate values in the array? A: The two-pointer approach still works correctly since it only depends on the sum, not uniqueness. The problem guarantees exactly one solution, so duplicates don't create ambiguity here.

Q: How would you modify this to return all pairs that sum to target, including duplicates? A: After finding a match, instead of returning immediately, record the pair, then move both left++ and right--, skipping over duplicate values at each new position to avoid repeated pairs.

Q: What happens if no pair sums to target? A: The loop ends when left >= right without finding a match. The problem guarantees a solution exists, but defensively you'd return an empty array or raise an error to signal no valid pair.

Quick Revision​

  • Two pointers start at index 0 (left) and n-1 (right).
  • Sorted array guarantees moving pointers moves the sum predictably.
  • sum == target → return [left+1, right+1] (1-indexed).
  • sum < target → move left right to increase sum.
  • sum > target → move right left to decrease sum.
  • Loop continues while left < right.
  • Time: O(n) single pass; Space: O(1), no extra structures.
  • Contrast with LC 1 (unsorted): needs O(n) space hash map.
  • Works with negative numbers — logic is unaffected by sign.
  • 653 - Two Sum IV - Input Is a BST — same "find a pair summing to target" goal, adapted to a BST using in-order traversal instead of two pointers.
  • 16 - 3Sum Closest — extends the two-pointer technique by fixing one element and scanning the rest with two pointers.
  • Pattern reference: "Two Sum" (LeetCode 1, unsorted array, hash map, O(n) space) — the classic counterpart to this sorted-array, O(1)-space variant.