Solving the Two Sum Problem

As a computer science enthusiast, I often come across intriguing problems that not only challenge my coding skills but also enhance my problem-solving abilities. One such classic problem is the "Two Sum" problem, a common interview question and a great exercise for anyone looking to improve their programming acumen. In this post, I'll walk you through what the Two Sum problem is, why it's important, and how to solve it using JavaScript.

The Two Sum problem is simple in its statement: Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. This problem tests your understanding of array manipulation and hashing concepts. It's a fundamental question in algorithm design, often used to gauge a candidate's ability to work with data structures.

Understanding the Problem

The key to solving the Two Sum problem lies in understanding how to efficiently find two numbers in the array that sum up to the target value. A brute force approach would involve checking each pair of numbers, but this is inefficient, especially for large arrays. A more efficient approach involves using a hash table to store and quickly look up the complement of each number.

The Solution

Here's a TypeScript function that solves the Two Sum problem:

export function twoSum(nums: number[], target: number): number[] {
  const hash: { [key: number]: number } = {};
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (diff in hash) {
      return [hash[diff], i];
    }
    hash[nums[i]] = i;
  }

  return [];
}

Here's a JavaScript function that solves the Two Sum problem:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  const map = new Map();

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

    if (diff !== undefined) {
      return [diff, i];
    }

    map.set(nums[i], i);
  }
};

Breaking Down the Solution

Initialize a Hash Table: We create a hash table (or object in JavaScript) to store each number's index as we iterate through the array.

Iterate Through the Array: We loop through each element in the array.

Calculate the Difference: For each element, we calculate the difference between the target and the current element. This difference is the value we need to find in the array to get a pair that sums to the target.

Check the Hash Table: We check if this difference already exists in our hash table. If it does, it means we have found a pair that adds up to the target. We return the indices of these two elements.

Store in the Hash Table: If the difference is not in the hash table, we add the current element and its index to the hash table and continue the loop.

Return Empty if No Solution: If no pair adds up to the target, we return an empty array.