Leetcode 167. Two Sum II - Input Array Is Sorted

Let's understand what we're being asked to do. We have a sorted array like [2, 7, 11, 15] and a target sum like target=9. We need to find two distinct elements that add up to the target and return their 1-based indices.

Tracing through: index 1 has value 2, index 2 has value 7. Check: 2+7=9 (matches target!). Return [1, 2] (1-based indices).

Important constraint: The array is already sorted in non-decreasing order, and there is exactly one solution. This means we don't need to handle cases where no solution exists or multiple solutions exist.

Edge cases to consider: What if the array has only two elements? What if the two elements are at opposite ends of the array? Remember that indices are 1-based, not 0-based!

The brute force approach checks all possible pairs of elements using nested loops. For each element at index i, check every element at index j (where j > i) to see if their sum equals the target. When a matching pair is found, return their 1-based indices. This approach is straightforward but inefficient because it doesn't leverage the sorted property of the array.

def two_sum_brute_force(nums, target):
    """
    Find two distinct elements in sorted array that sum to target.
    Returns their 1-based indices using brute force approach.
    """
    n = len(nums)
    
    # Check all possible pairs
    for i in range(n):
        for j in range(i + 1, n):
            # Calculate sum of current pair
            current_sum = nums[i] + nums[j]
            
            # Check if sum equals target
            if current_sum == target:
                # Return 1-based indices
                return [i + 1, j + 1]
    
    # No solution found (should not happen per problem statement)
    return []

Since the array is sorted, if we pick two elements and their sum is too large, we need to try a smaller element. If their sum is too small, we need to try a larger element.

By starting with pointers at both ends of the array, we can make smart decisions about which direction to move based on whether the current sum is too large or too small.

This observation means we can find the solution in a single pass through the array without checking all possible pairs.

Instead of checking n*(n-1)/2 pairs (which would be O(n²)), we only need to check at most n pairs by intelligently moving our pointers inward. The sorted property is what makes this optimization possible!

Imagine you're standing at opposite ends of a number line. If you're too far apart (sum too large), the person on the right steps left. If you're too close (sum too small), the person on the left steps right.

You keep adjusting until you meet at exactly the right distance. The sorted property guarantees that moving left always decreases the sum and moving right always increases it, so you'll never miss the solution.

The optimal approach uses two pointers starting at opposite ends of the sorted array. Calculate the sum of elements at both pointers. If the sum equals the target, return the 1-based indices. If the sum is less than the target, move the left pointer right to increase the sum. If the sum is greater than the target, move the right pointer left to decrease the sum. This converges to the solution in a single pass by exploiting the sorted property.

def two_sum_sorted(nums, target):
    """
    Find two distinct elements in sorted array that sum to target.
    Returns their 1-based indices.
    """
    # Initialize two pointers at opposite ends
    left = 0
    right = len(nums) - 1
    
    # Scan from both ends toward center
    while left < right:
        current_sum = nums[left] + nums[right]
        
        # Check if we found the target sum
        if current_sum == target:
            # Return 1-based indices
            return [left + 1, right + 1]
        elif current_sum < target:
            # Sum too small, move left pointer right to increase sum
            left += 1
        else:
            # Sum too large, move right pointer left to decrease sum
            right -= 1
    
    # Should never reach here if exactly one solution exists
    return []

• Two-pointer convergence on sorted arrays: When you have a sorted array and need to find pairs meeting a condition, use opposing pointers (left at start, right at end) - the sorted property lets you intelligently move pointers based on whether the current sum is too high (move right pointer left) or too low (move left pointer right), guaranteeing O(n) time.
• Space-time tradeoff awareness: While a hash map would solve this in one pass, the sorted array property enables an O(1) space solution with two pointers - recognize when problem constraints (like sorted input) allow you to avoid extra space by leveraging inherent structure.
• Index adjustment for 1-based arrays: When problems specify 1-indexed returns, add 1 to your 0-based loop indices at the return statement only - keep all internal logic 0-indexed to avoid off-by-one errors, then convert at the boundary.
• Pointer movement logic: The critical insight is monotonic adjustment - if `arr[left] + arr[right] < target`, left must move right (no point checking smaller right values), and vice versa - this eliminates the need to check all O(n²) pairs by pruning impossible combinations.
• Sorted array pattern recognition: Whenever you see sorted input combined with pair/triplet sum problems, immediately consider two-pointer techniques - this pattern extends to 3Sum, 4Sum, and container problems where sorted order enables intelligent search space reduction.
• Guaranteed solution handling: When the problem states exactly one solution exists, you can safely return immediately upon finding a match without defensive null checks - but in real-world scenarios, always add validation to handle the no-solution case by returning after the loop completes.