Two Sum

Intuition

We need to find two numbers in the array whose sum equals the given target . A naive approach would be to check every possible fair, but this would be inefficient.

Instead, we can leverage the fact that if nums[i] + nums[j] = target , then nums[j] = target - nums[i] .

So as we iterate, if we already saw target - nums[i] , we have our answer.

Approach

• Create a dictionary to store numbers we’ve seen so far with their indices.
• Iterate through the array:
  • For each number nums[i] , compute complement = target - nums[i] .
  • Check if complement exists in the dictionary:
    • If yes, return [index_of_complement, i] .
  • Otherwise, add nums[i] to the dictionary with its index.
• This ensures each element is processed once, giving us 0(n) time complexity.

Proof of Correctness

• Existence: The dictionary always contains all elements before the current index. So if a valid pair exists, it will be found when processing the second element of the pair.
• Uniqueness: The problem guarantees exactly one solution; hence, the first match found is the correct and only answer.
• Termination: The loop stops as soon as the pair is found, so no unnecessary work is done.

Complexity

• Time:
  • We traverse the array once, and each lookup in the dictionary is 0(1) on average.
  • Total: 0(n).
• Space:
  • The dictionary stores up to n elements in the worst case.
  • Total: 0(n).

Code

function twoSum(nums: number[], target: number): number[] {
    const seen: Record<number, number> = {};

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

        if (seen[complement] !== undefined) {
            return [seen[complement], i]
        }

        seen[num] = i;
    }

    return [];    
};

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i