Solutions

# Two pointers. Or binary search. Or hash map. Or brute force.
# two-pointers

# O(n) time, O(1) space
def two_sum(numbers: list[int], target: int) -> list[int]:
    left = 0
    right = 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
    return []

# Binary search: O(log n) time, O(1) space
def two_sum(numbers: list[int], target: int) -> list[int]:
    for i in range(len(numbers)):
        complement = target - numbers[i]
        low = i + 1
        high = len(numbers) - 1
        while low <= high:
            mid = (low + high) // 2
            if numbers[mid] == complement:
                return [i + 1, mid + 1]
            elif numbers[mid] < complement:
                low = mid + 1
            else:
                high = mid - 1
    return []

# Hash map: O(n) time, O(n) space
def two_sum(numbers: list[int], target: int) -> list[int]:
    num_dict = {}
    for i, num in enumerate(numbers):
        complement = target - num
        if complement in num_dict:
            return [num_dict[complement] + 1, i + 1]
        num_dict[num] = i
    return []