two-sum-ii.ts

/**
 * 167. Two Sum II - Input Array Is Sorted  (Medium)
 * Link: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/
 *
 * Given a 1-indexed array sorted in non-decreasing order, return the 1-based
 * indices of the two numbers that add up to `target`. Exactly one solution
 * exists and you may not use the same element twice.
 *
 * Example:
 *   Input:  numbers = [2, 7, 11, 15], target = 9
 *   Output: [1, 2]
 *
 * Approach:
 *   Because the array is sorted, use two pointers at the ends. If the pair sum
 *   is too small, move the left pointer up (increase the sum); if too large,
 *   move the right pointer down. This is O(1) space vs the hash-map version.
 *
 * Time:  O(n)  — pointers converge in a single pass.
 * Space: O(1)
 */
export function twoSumII(numbers: number[], target: number): [number, number] {
  let left = 0;
  let right = numbers.length - 1;

  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) return [left + 1, right + 1];
    if (sum < target) left++;
    else right--;
  }

  throw new Error("No two sum solution exists for the given input.");
}