Two Pointers

LeetCode 167

LeetCode #167Difficulty: MediumNeetCode 150

LeetCode 167: Two Sum II - Input Array Is Sorted

LeetCode

Find two numbers that add up to target in a sorted array using constant extra space O(1).

Problem Description

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, `[index1, index2]`, as an integer array of length 2 where 1 <= index1 < index2 <= numbers.length. You may not use the same element twice. Your solution must use only constant extra space.

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

Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. Return [1, 2].

Constraints:
  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • The tests are generated such that there is exactly one solution.

Core Mental Model

The Two-Pointer Inward Convergence pattern exploits monotonic order in a sorted array. • If current sum < target: Because the array is sorted, pairing numbers[left] with ANY smaller element to the left of `right` is guaranteed to be strictly less than target. We increment `left++` (pruning an entire candidate row in O(1)). • If current sum > target: Symmetrically, `numbers[right]` combined with any element ≥ `numbers[left]` will strictly exceed target. We decrement `right--`. This guarantees we inspect at most N elements before terminating.

Formal Loop Invariant

Invariant: At each step, if a solution exists in the original array, it is guaranteed to lie within the inclusive subsegment [left ... right]. All pairs outside this interval have been proven invalid.

Key Architectural Takeaway:

Sorting provides monotonic leverage. At each step, one pointer increment or decrement discards an entire slice of invalid combinations without memory overhead.

Asymptotic Complexity Analysis

Time ComplexityO(N) Every iteration shifts either left rightward or right leftward by 1. Total pointer movements ≤ N.
Space ComplexityO(1) Memory footprint is strictly constant (only two integer pointers maintained).

Bottleneck: Brute-force nested loops inspect N*(N-1)/2 pairs -> O(N²). Two Pointers uses the monotonicity invariant to discard N-1 impossible pairs in each step.

Edge Cases & Screener Traps

  • Both numbers are identical (e.g. [2, 2], target 4)
  • Negative numbers with zero cross-over (e.g. [-5, -2, 1, 4])