Problem Solving - Sum of Two Numbers (Hash Table)

 Problem Solving - Sum of Two Numbers (Hash Table)

The twoSum function is designed to find two numbers in an array (numbers) that add up to a specific target value. The function returns the indices of these two numbers in the form of an array. Here's a step-by-step explanation:

function twoSum(numbers = [], target = 0) {

const hashTable = {};

  for (let i = 0; i < numbers.length; i++) {

    const remaining = target - nums[i]

    if (hashTable[remaining] !== undefined) {

      return [hashTable[remaining], i]

    }

    hashTable[numbers[i]] = i;

  }

  return [];

};

 

Function Breakdown:

1. Input Parameters:

   • nums: An array of numbers.
   • target: A single number representing the target sum.

2. Output:

   • An array containing the indices of the two numbers that add up to the target. If no such pair is found, the function returns an empty array.

Explanation:

Initialization:

A hash table (or object) hashTable is initialized to store the indices of numbers encountered so far.

A loop is set up to iterate over the nums array, where i is the current index.

For each number in the array, the function calculates the remaining value that, when added to nums[i], would equal the target.

The function checks if the remaining value already exists in the hashTable.

If it does, it means a pair has been found that adds up to the target. The function then returns an array with the index of the remaining value and the current index i.

If the remaining value is not found in the hash table, the current number (nums[i]) and its index (i) are stored in the hashTable.

If the loop completes without finding a pair that adds up to the target, the function returns an empty array, indicating that no such pair exists.

Example:

• Suppose nums = [2, 7, 11, 15] and target = 9.
  Iteration 1:

  • i = 0, nums[0] = 2, remaining = 9 - 2 = 7
  • hashTable = {} (7 is not in hashTable)
  • hashTable becomes {2: 0}
  Iteration 2:
  • i = 1, nums[1] = 7, remaining = 9 - 7 = 2
  • hashTable = {2: 0} (2 is in hashTable)
  • The function returns [0, 1] since nums[0] + nums[1] = 2 + 7 = 9.

This solution is efficient with a time complexity of O(n), where n is the length of the nums array. This is because each element is processed only once in a single pass through the array.