167. Two Sum II - Input Array Is Sorted

This problem asks to find two numbers within a sorted array that add up to a specific target. The solution must use only constant extra space.

Approach 1: Binary Search

This approach iterates through the array. For each number, it uses binary search to check if the complement (target - number) exists in the remaining portion of the array.

Algorithm:

1. Iterate: Loop through the array using a single for loop.
2. Calculate Complement: For each number numbers[i], calculate its complement complement = target - numbers[i].
3. Binary Search: Perform a binary search on the subarray numbers[i+1:] to find the complement. bisect_left (or lower_bound in C++) is efficient for this.
4. Check and Return: If the complement is found at index j within the subarray, return [i+1, j+1] (indices are 1-based).

Time Complexity: O(n log n). The outer loop iterates n times, and the binary search takes O(log n) time in each iteration.

Space Complexity: O(1). The algorithm uses only a few variables to store indices and the complement.

Approach 2: Two Pointers

This approach leverages the sorted nature of the input array. It uses two pointers, one at the beginning and one at the end of the array, and moves them towards the middle based on the sum of the numbers they point to.

Algorithm:

1. Initialization: Initialize two pointers, left at the beginning (index 0) and right at the end (index n-1) of the array.
2. Sum and Compare: Calculate the sum sum = numbers[left] + numbers[right].
3. Adjust Pointers:
   • If sum == target, return [left + 1, right + 1] (1-based indices).
   • If sum < target, increment left to consider a larger number.
   • If sum > target, decrement right to consider a smaller number.
4. Repeat: Continue until left and right cross each other (left >= right).

Time Complexity: O(n). The two pointers move towards the middle, resulting in at most n comparisons.

Space Complexity: O(1). Only a few variables are used.

Code Examples

Here's how the two approaches are implemented in various programming languages:

(Note: The following code snippets omit error handling for brevity. Production code should include checks to handle edge cases like empty input arrays or cases where no solution exists.)

Python (Binary Search)

import bisect
 
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        for i in range(n):
            complement = target - numbers[i]
            j = bisect.bisect_left(numbers, complement, i + 1)
            if j < n and numbers[j] == complement:
                return [i + 1, j + 1]

Python (Two Pointers)

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

Similar code can be written in Java, C++, JavaScript, and other languages using the same core logic for both approaches. The two-pointer approach is generally preferred due to its better time complexity.