LeetCode 167: Two Sum Ii Input Array Is Sorted — Step-by-Step Visual Trace

#python #leetcode #algorithms

Medium — Two Pointers | Array | Binary Search

The Problem

Find two numbers in a sorted array that add up to a specific target value, returning their 1-indexed positions.

Approach

Use two pointers starting from opposite ends of the sorted array. Move the left pointer right if the sum is too small, or move the right pointer left if the sum is too large, leveraging the sorted property to efficiently narrow down the search space.

Time: O(n) · Space: O(1)

Code

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

        # No solution found
        return [-1, -1]