167. Two Sum II - Input Array Is Sorted

Summary

Solution Approach	Explanation (1-minute)	Time Complexity	Space Complexity
Naive Approach (Nested Loop)	Use two nested loops to try every possible pair of numbers. For each pair, check if their sum matches the target. Return the indices if a match is found.	O(n²): The outer loop iterates over each element, and the inner loop checks all elements after it, resulting in quadratic time.	O(1): Constant space since no extra data structures are used.
Two-pointer technique	Use two pointers on the sorted array, one starting at the beginning and the other at the end. Check the sum and adjust the pointers accordingly to find the solution in one pass.	O(n): Linear scan as the two pointers converge towards the solution.	O(1): Only pointers are used, with no extra space.

Implementation

Python

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