Coding Interview Questions | Two Sum

December 13th, 2023

Introduction:

This summary will talk about my solution to the classic two sum coding problem as seen on leetcode here.

Solution:

function twoSum(nums: number[], target: number): number[] {
  const seenNumbersValToIdxMap = new Map<number, number>();

  for (let numIdx = 0; numIdx < nums.length; numIdx++) {
    const currentNumber = nums[numIdx];
    const solutionNumber = target - currentNumber;
    const solutionIdx = seenNumbersValToIdxMap.get(solutionNumber);

    if (solutionIdx !== undefined) {
      return [solutionIdx, numIdx];
    }

    seenNumbersValToIdxMap.set(currentNumber, numIdx);
  }

  return [];
}

Summary:

The solution above utilizes a Map to store encountered numbers and their corresponding indices while iterating through the provided nums array. For each number, it calculates the complement needed to reach the target, checks if the complement is in the map, and returns the indices if a solution is found. This approach ensures a time complexity of O(n) by avoiding unnecessary nested iterations and achieves the goal of finding the indices of two numbers that add up to the target.