1. Understand the problem

• Goal: Given a 1-indexed sorted array numbers and a target, return the indices [i, j] such that numbers[i] + numbers[j] == target.

• Space complexity: O(1).

2. Clarifying questions

1. Are all numbers positive? Can there be negatives? (Usually yes, can be negative.)

2. Are duplicates allowed? (Yes.)

3. Should we return the first solution if multiple? (Yes, exactly one guaranteed.)

4. Time/space constraints? (Aim O(n) time, O(1) space if possible.)

3. Work through examples

1. Example 1: numbers = [2,7,11,15], target = 9 → [1,2] (2 + 7 = 9)

2. Example 2: numbers = [2,3,4], target = 6 → [1,3] (2 + 4 = 6)

3. Example 3: numbers = [-1,0], target = -1 → [1,2] (-1 + 0 = -1)

4. Brainstorm 2–3 solutions & complexity

4.1. Brute Force

• Nested loops: for each i, check all j > i.

• Time: O(N^2)

• Space: O(1)

4.2. Hash Map (like classic Two Sum)

• Traverse array, store number → index in a dict.

• For each number x, check if target - x exists in the dict.

• Time: O(n)

• Space: O(n)

4.3. Two-pointer (Optimal)

• Use two pointers i = 0, j = n-1.

While i < j:

- curr = numbers[i] + numbers[j]

- If curr == target: return [i+1, j+1] (1-indexed)

- If curr < target: move i += 1

- If curr > target: move j -= 1

• Time: O(n)

• Space: O(1)

Notes: If array are sorted, two pointer is better than hashmap.

5. Implement solutions

5.1. Brute Force

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            for j in range(i + 1, len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]
        return []

• Time complexity: O(N^2).

• Space complexity: O(1).

5.2. Binary Search

• Idea:

1. Keep nums[i]

2. Find nums[j] in [i + 1, N] to find nums[i] + nums[j] == target

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            l, r = i + 1, len(numbers) - 1
            tmp = target - numbers[i]
            while l <= r:
                mid = l + (r - l)//2
                if numbers[mid] == tmp:
                    return [i + 1, mid + 1]
                elif numbers[mid] < tmp:
                    l = mid + 1
                else:
                    r = mid - 1
        return []

• Time complexity: O(NlogN).

• Space complexity: O(1).

5.3. Hash map

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        mp = defaultdict(int) # val -> index
        for i in range(len(numbers)):
            tmp = target - numbers[i]
            if mp[tmp]:
                return [mp[tmp], i + 1]
            mp[numbers[i]] = i + 1
        return []

• Time complexity: O(N).

• Space complexity: O(N).

5.4. Two Pointers

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

        while l < r:
            curSum = numbers[l] + numbers[r]

            if curSum > target:
                r -= 1
            elif curSum < target:
                l += 1
            else:
                return [l + 1, r + 1]
        return []

• Time complexity: O(N).

• Space complexity: O(1).

6. Run the testcase

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

i=0, j=2 → 2+4=6 → match → return [1,3]

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

i=0,j=3 → 2+15=17 → too large → j=2

i=0,j=2 → 2+11=13 → too large → j=1

i=0,j=1 → 2+7=9 → match → return [1,2]