LeetCode 167: Two Sum II - Input Array Is Sorted - All Solutions Explained

Problem Statement

The Two Sum II - Input Array Is Sorted problem, LeetCode 167, is an easy-difficulty challenge where you’re given a 1-indexed array of integers numbers that is sorted in non-decreasing order and a target integer target. Your task is to find two numbers in the array that add up to target and return their indices as a 1-indexed array [index1, index2] where index1 < index2. There is exactly one solution, and you may not use the same element twice.

Constraints

2 ≤ numbers.length ≤ 3 * 10⁴
-1000 ≤ numbers[i] ≤ 1000
numbers is sorted in non-decreasing order.
-1000 ≤ target ≤ 1000
A unique solution exists.

Example

Example in Python

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: 2 + 7 = 9, indices 1 and 2 (1-indexed).

Example in Python

Input: numbers = [2,3,4], target = 6
Output: [1,3]
Explanation: 2 + 4 = 6, indices 1 and 3.

Example in Python

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: -1 + 0 = -1, indices 1 and 2.

Understanding the Problem

We need to find two distinct elements in a sorted array that sum to the target and return their 1-indexed positions. Key points:

The array is sorted, allowing efficient solutions.
Exactly one solution exists, no duplicates needed.
We’ll explore two solutions:
- Two-Pointer : Optimal using sorted property (best solution).
- Binary Search : Alternative leveraging sorting.

Solution 1: Two-Pointer (Best Solution)

Intuition

Use two pointers, one at the start and one at the end, leveraging the sorted order to adjust the sum toward the target efficiently.

How It Works

Initialize left at 0 and right at the end.
While left < right:
- Compute sum of numbers[left] + numbers[right].
- If sum equals target, return 1-indexed positions.
- If sum is too high, decrease right.
- If sum is too low, increase left.

Step-by-Step Example

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

Left = 0 (2), Right = 3 (15): 2 + 15 = 17 > 9 → Right = 2.
Left = 0 (2), Right = 2 (11): 2 + 11 = 13 > 9 → Right = 1.
Left = 0 (2), Right = 1 (7): 2 + 7 = 9 = 9 → Return [1, 2].
Result: [1, 2].

Python Code (Two-Pointer Solution)

Example in Python

def twoSum(numbers: list[int], target: int) -&gt; list[int]:
    left, right = 0, len(numbers) - 1
    
    while left &lt; right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum &lt; target:
            left += 1
        else:
            right -= 1
    
    return []  # No solution (won't happen per constraints)

# Test cases
print(twoSum([2,7,11,15], 9))    # Output: [1,2]
print(twoSum([2,3,4], 6))        # Output: [1,3]
print(twoSum([-1,0], -1))        # Output: [1,2]

Detailed Walkthrough

Pointers : Start at ends, move inward.
Sum : Adjust based on comparison with target.
Indices : Add 1 for 1-indexing.

Complexity

Time Complexity : O(n), single pass with two pointers.
Space Complexity : O(1), only using pointers.

Why It’s the Best

Optimal time complexity.
Takes full advantage of sorted order.
Preferred in interviews for its elegance.

Solution 2: Binary Search

Intuition

For each element, use binary search to find its complement (target - element) in the remaining sorted array.

How It Works

Iterate over each element as the first number.
Binary search for target - numbers[i] in numbers[i+1:].
Return 1-indexed positions when found.

Python Code (Binary Search Solution)

Example in Python

def twoSum(numbers: list[int], target: int) -&gt; list[int]:
    for i in range(len(numbers)):
        complement = target - numbers[i]
        left, right = i + 1, len(numbers) - 1
        
        while left &lt;= right:
            mid = (left + right) // 2
            if numbers[mid] == complement:
                return [i + 1, mid + 1]
            elif numbers[mid] &lt; complement:
                left = mid + 1
            else:
                right = mid - 1
    
    return []  # No solution (won't happen per constraints)

# Test cases
print(twoSum([2,7,11,15], 9))    # Output: [1,2]
print(twoSum([2,3,4], 6))        # Output: [1,3]
print(twoSum([-1,0], -1))        # Output: [1,2]

Detailed Walkthrough

Loop : Try each element as first number.
Search : Find complement in remaining array.
Indices : Convert to 1-indexed.

Complexity

Time Complexity : O(n log n), n iterations with log n search.
Space Complexity : O(1), no extra space.

Pros and Cons

Pros : Uses binary search effectively.
Cons : Slower than two-pointer due to repeated searches.

Comparison of Solutions

Solution	Time Complexity	Space Complexity	Best Use Case
Two-Pointer	O(n)	O(1)	Efficiency, interviews
Binary Search	O(n log n)	O(1)	Learning, binary search practice

Edge Cases to Consider

Two Elements : [-1,0], -1 → [1,2].
Negative Numbers : Works due to sorted order.
Large Target : target within bounds, solution guaranteed.
Min/Max Values : [-1000,1000], 0 → [1,2].

Final Thoughts

Two-Pointer : The best solution—fast and elegant, leveraging the sorted property. It’s the top choice for interviews.
Binary Search : Good for learning but less efficient here. Master the two-pointer approach for its simplicity, and revisit LeetCode 1 (unsorted Two Sum) for contrast!