LeetCode 167: Two Sum II - Input Array Is Sorted Solution in Python Explained

Problem Statement

In LeetCode 167, you’re given a 1-indexed array numbers sorted in non-decreasing order and an integer target. Your task is to return a 1-indexed array [index1, index2] (where index1 < index2) representing the indices of two numbers that sum to target. The array has exactly one solution, and you must achieve O(n) time complexity or better, using O(1) extra space. This builds on LeetCode 1: Two Sum with a sorted array, differing from decimal conversion like LeetCode 166: Fraction to Recurring Decimal.

Constraints

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• Sorted in non-decreasing order
• -1000 <= target <= 1000
• Exactly one solution exists

Example

Let’s see some cases:

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

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

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

These examples show we’re finding index pairs in a sorted array.

Understanding the Problem

How do you solve LeetCode 167: Two Sum II - Input Array Is Sorted in Python? Take numbers = [2,7,11,15], target = 9. We need indices (1-indexed) of two numbers summing to 9—2 + 7 = 9, so [1,2]. For [2,3,4], target = 6, 2 + 4 = 6, so [1,3]. The sorted property lets us optimize beyond the O(n²) brute force of Two Sum, aiming for O(n) or O(n log n) time with O(1) space. This isn’t a gap-finding task like LeetCode 164: Maximum Gap; it’s about pair summing. We’ll use: 1. Two-Pointer Approach: O(n) time, O(1) space—our best solution. 2. Binary Search: O(n log n) time, O(1) space—an alternative.

Let’s dive into the best solution.

Best Solution: Two-Pointer Approach

Explanation

Two-Pointer Approach leverages the sorted array with two pointers:

• Start left at the beginning (index 0) and right at the end (index n-1).
• Compute the sum numbers[left] + numbers[right]:
• If sum equals target, return [left+1, right+1] (1-indexed).
• If sum < target, increment left (need a larger sum).
• If sum > target, decrement right (need a smaller sum).
• Continue until pointers meet or solution is found.

This is the best solution due to its O(n) time complexity (single pass), O(1) space usage, and simplicity by exploiting the sorted order, making it optimal and elegant.

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

• Left=2, Right=15, 17 > 9, move right.
• Left=2, Right=11, 13 > 9, move right.
• Left=2, Right=7, 9 = 9, return [1,2].

Step-by-Step Example

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

Goal: Return [1,2].

• Start: left = 0, right = 3.
• Step 1: sum = 2 + 15 = 17, 17 > 9, right = 2.
• Step 2: sum = 2 + 11 = 13, 13 > 9, right = 1.
• Step 3: sum = 2 + 7 = 9, 9 = 9, return [left+1, right+1] = [1,2].
• Finish: Return [1,2].

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

Goal: Return [1,3].

• Start: left = 0, right = 2.
• Step 1: sum = 2 + 4 = 6, 6 = 6, return [1,3].
• Finish: Return [1,3].

Example 3: numbers = [-1,0], target = -1

Goal: Return [1,2].

• Start: left = 0, right = 1.
• Step 1: sum = -1 + 0 = -1, -1 = -1, return [1,2].
• Finish: Return [1,2].

How the Code Works (Two-Pointer Approach) – Detailed Line-by-Line Explanation

Here’s the Python code with a thorough breakdown:

def twoSum(numbers: list[int], target: int) -> list[int]:
    # Line 1: Initialize pointers
    left = 0
    # Left pointer (e.g., 0)
    right = len(numbers) - 1
    # Right pointer (e.g., 3 for [2,7,11,15])

    # Line 2: Traverse with two pointers
    while left < right:
        # Continue until pointers meet (e.g., 0 < 3)

        # Line 3: Compute current sum
        curr_sum = numbers[left] + numbers[right]
        # Sum of pair (e.g., 2 + 15 = 17)

        # Line 4: Compare with target
        if curr_sum == target:
            # Found solution (e.g., 2 + 7 = 9)
            return [left + 1, right + 1]
            # 1-indexed (e.g., [1,2])
        elif curr_sum < target:
            # Sum too small (e.g., 2 + 11 < 9, false here)
            left += 1
            # Move left (e.g., 1)
        else:
            # Sum too large (e.g., 17 > 9)
            right -= 1
            # Move right (e.g., 2)

    # Line 5: Return default (unreachable due to problem guarantee)
    return []
    # Not reached, as solution exists

This detailed breakdown clarifies how the two-pointer approach efficiently finds the target pair.

Alternative: Binary Search Approach

Explanation

Binary Search uses one pointer and binary search for the complement:

• For each numbers[i], compute complement = target - numbers[i].
• Binary search for complement in numbers[i+1:].
• Return 1-indexed indices if found.

It’s a practical alternative, O(n log n) time (n searches, log n each), O(1) space, but slower than two-pointer due to repeated searches.

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

• i=0, 9-2=7, search [7,11,15], find at 1, return [1,2].

Step-by-Step Example (Alternative)

For [2,3,4], target = 6:

• Step 1: i=0, complement=4, search [3,4], find at 2, return [1,3].
• Finish: Return [1,3].

How the Code Works (Binary Search)

def twoSumBinary(numbers: list[int], target: int) -> list[int]:
    for i in range(len(numbers)):
        complement = target - numbers[i]
        left, right = i + 1, len(numbers) - 1
        while left <= right:
            mid = left + (right - left) // 2
            if numbers[mid] == complement:
                return [i + 1, mid + 1]
            elif numbers[mid] < complement:
                left = mid + 1
            else:
                right = mid - 1
    return []

Complexity

• Two-Pointer Approach:
• Time: O(n) – single pass.
• Space: O(1) – constant space.
• Binary Search:
• Time: O(n log n) – n binary searches.
• Space: O(1) – constant space.

Efficiency Notes

Two-Pointer Approach is the best solution with O(n) time and O(1) space, leveraging sorted order optimally—Binary Search uses O(n log n) time, making it viable but less efficient, though still space-efficient.

Key Insights

• Two-Pointer: Sorted advantage.
• Binary: Search complement.
• 1-Indexed: Adjust output.

Additional Example

For numbers = [1,3,4,6], target = 7:

• Goal: [2,3].
• Two-Pointer: 1+6=7, return [2,3].

Edge Cases

• Two Elements: [1,2], 3 → [1,2].
• Negative: [-2,-1], -3 → [1,2].
• Ends: [1,5], 6 → [1,2].

Both solutions handle these well.

Final Thoughts

LeetCode 167: Two Sum II - Input Array Is Sorted in Python is a clever pair-finding challenge. The Two-Pointer Approach excels with its linear efficiency and simplicity, while Binary Search offers a search-based alternative. Want more? Try LeetCode 1: Two Sum for the unsorted version or LeetCode 94: Binary Tree Inorder Traversal for tree skills. Ready to practice? Solve LeetCode 167 on LeetCode with [2,7,11,15] and target=9, aiming for [1,2]—test your skills now!