two-sum.ts

/**
 * 1. Two Sum  (Easy)
 * Link: https://leetcode.com/problems/two-sum/
 *
 * Given an array of integers `nums` and an integer `target`, return the indices
 * of the two numbers that add up to `target`. Exactly one solution exists and
 * the same element may not be used twice.
 *
 * Example:
 *   Input:  nums = [2, 7, 11, 15], target = 9
 *   Output: [0, 1]            // nums[0] + nums[1] === 9
 *
 * Approach:
 *   Single pass with a hash map from value -> index. For each number we ask
 *   whether its complement (target - num) was already seen; if so we have the
 *   pair. This avoids the O(n^2) brute-force double loop.
 *
 * Time:  O(n)  — one pass, O(1) map operations.
 * Space: O(n)  — up to n entries stored in the map.
 */
export function twoSum(nums: number[], target: number): [number, number] {
  const seen = new Map<number, number>();

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement)!, i];
    }
    seen.set(nums[i], i);
  }

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