LeetCode #1 – Two Sum

Problem Statement

1. Task


• Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.


• Constraints from the original problem:
  • Exactly one valid solution exists.
  • You may not use the same element twice.
  • The answer can be returned in any order.


• Example:
  • nums = [2, 7, 11, 15], target = 9
  • Answer: [0, 1] because nums[0] + nums[1] = 2 + 7 = 9.

Brute Force Solution (O(n²))

1. Idea


• Check all pairs (i, j) with i < j and see if nums[i] + nums[j] === target.
• Return the first pair of indices that satisfies the condition.


2. Core Loop Structure

function twoSum(nums: number[], target: number): number[] {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
}

• Outer loop picks the first index i.
• Inner loop picks the second index j such that j > i (no duplicates, no self-pairing).
• If the sum matches target, we immediately return the indices.
• Because LeetCode guarantees a solution, we don't need explicit handling for "no answer".


3. Complexity


• Time: we check roughly n(n-1)/2 pairs ⇒ O(n²).
• Space: only uses a few local variables ⇒ O(1).
• Good for understanding, but not optimal for larger arrays.

Optimized Hash Map Solution (O(n))

1. High-Level Idea


• Instead of scanning all pairs, we remember numbers we have seen so far in a hash map.
• For each element nums[i], we look for its "partner" diff = target - nums[i] in the map:
  • If diff is already in the map, we found a pair.
  • Otherwise, we store nums[i] and its index, then move on.


2. Core Logic

const memo = new Map<number, number>();

for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];

    if (memo.has(diff)) {
        // We have seen `diff` before at index memo.get(diff)
        return [memo.get(diff)!, i];
    }

    // Remember the current number and its index
    memo.set(nums[i], i);
}

• memo maps a number to its index (e.g. memo.get(2) === 0 if nums[0] === 2).
• At each step:
  • Compute the complementary value diff.
  • If we have already seen diff, then nums[memo.get(diff)] + nums[i] === target.
  • Otherwise, store the current number so that future elements can pair with it.
• In strict TypeScript, memo.get(diff) may be undefined, so a non-null assertion ! or an extra check is used. Logically we are safe here because we only call get if has(diff) is true.


3. Complexity


• We traverse the array once, and each map operation is on average O(1).
• Time: O(n).
• Space: we store at most n entries in the map ⇒ O(n).