[Algorithms] Two Sum

The Two Sum problem is a popular coding challenge that involves finding pairs of numbers in an array that add up to a specific sum. This is a great problem to practice your problem-solving skills and reinforce your understanding of hash tables for improving time complexity.

Problem Description

Given an array of numbers and a target sum, the goal is to return all pairs of numbers that add up to the target sum.

Example

Let’s take an example to understand it better. Suppose we are given the array [1, 6, 4, 5, 3, 3] and the target sum is 7. Our algorithm should return the pairs that sum to 7, which are: [[6, 1], [4, 3], [4, 3]].

Every pair of numbers from the array adds up to 7, and it’s acceptable for a number to be used in multiple pairs.

Rules to Follow

Return an array of arrays: The result should contain arrays of pairs.
Reuse of numbers is allowed: A number from the input array can be part of multiple pairs if it satisfies the sum requirement.

Basic Approach: Brute Force (O(n²) Time Complexity)

A straightforward solution would be using nested loops to check every possible pair of numbers. This approach would result in a time complexity of O(n²) because we are checking all possible combinations of pairs. However, this is not the most efficient way.

Optimized Approach: Hash Table (O(n) Time Complexity)

To make our algorithm more efficient, we can use a hash table (or an object in JavaScript) to keep track of numbers we’ve already encountered. This allows us to find the complement of the current number (i.e., the number that, when added to the current one, gives the target sum) in constant time.

function twoSum(numArray, sum) {
  const pairs = [];
  const hashTable = {};

  for (let i = 0; i < numArray.length; i++) {
    const currNum = numArray[i];
    const counterpart = sum - currNum;

    // Check if the counterpart already exists in the hashTable
    if (hashTable[counterpart]) {
      pairs.push([currNum, counterpart]);
    }
    // Add the current number to the hashTable
    hashTable[currNum] = true;
  }

  return pairs;
}

console.log(twoSum([1, 6, 4, 5, 3, 3], 7));

The time complexity of this solution is O(n) because we only need to loop through the array once. Looking up elements in the hash table takes constant time, O(1).

1. Two Sum

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

  nums.forEach((num, index) => {
    const currentNum = num;
    const counterPart = target - num;

    if (hashTable[counterPart]) {
      const counterPartIndex = nums.findIndex((num) => num === counterPart);
      pairs.push([index, counterPartIndex]);
    } else {
      hashTable[currentNum] = true;
    }
  });

  return pairs[0];
};

Conclusion

The Two Sum algorithm is a classic example of how utilizing a hash table can significantly improve performance. While a brute force approach would have a time complexity of O(n²), the hash table approach brings it down to O(n), making it much more scalable for larger datasets.

When working on coding problems like this, always consider both time and space complexity and aim for an optimized solution. Happy coding!

🧑🏻‍💻 Sean Huang 📅 October 9, 2024