Two Sum II Array is Sorted

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given a sorted array
• Find the two indices that sum to a target number

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Input array is sorted
• Need to solve in $O(1)$ space
• Use Two Pointers

Approach Taken

(Step-by-step logic or pseudocode before coding.)

• Create two pointers: one at left end and the other at right end
• If current sum is smaller than target then increment left pointer because input array is sorted and you want a bigger number
• else decrement right pointer because you want a smaller number-

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Two Pointers

Time & Space Complexity

• Time: O($n$) → Reason: Iterating through the array once
• Space: O($1$) → Reason: Two Pointers are stored which is constant

Code

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers) - 1

        while l < r:
            currentSum = numbers[l] + numbers[r]
            if currentSum == target:
                return [l + 1, r + 1]
            elif currentSum < target:
                l += 1
            else:
                r -= 1

Common Mistakes / Things I Got Stuck On

• I was incrementing the second pointer r instead of decrementing it