Introduction

The Two Sum problem is a classic coding challenge that often appears in technical interviews at top tech companies. It's a great way to assess a programmer's understanding of fundamental algorithms and data structures.

Problem Statement: (Two Sum)

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Constraints:

2 <= nums.length <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Naive Approach: Brute Force

A straightforward solution involves using nested loops to iterate through the array and check every possible pair of elements.

function twoSumBruteForce(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i,j];
      }
    }
  }
  return [];
}

This approach has a time complexity of O(n^2) as it iterates through the array twice.

Optimized Approach: Using a Hash Table

A more efficient solution utilizes a hash table to store the elements and their corresponding indices. As we iterate through the array, we check if the difference between the target and the current element already exists in the hash table. If it does, we've found a pair that sums up to the target.

function twoSumHash(nums, target) {
  const complementMap = {};
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (complementMap[complement] !== undefined) {
      return [complementMap[complement], i];
    }
    complementMap[nums[i]] = i;
  }
  return [];
}

This approach has a time complexity of O(n) as we iterate through the array only once.

Approach	Time Complexity	Space Complexity
Brute Force	O(n²)	O(1)
Hash Table	O(n)	O(n)

Edge Cases: Consider edge cases such as empty arrays or arrays with only one element.

Duplicate Elements: If duplicate elements are allowed, you might need to adjust the hash table to handle multiple indices for the same element.

Variations: Explore variations of the problem, such as finding three numbers that sum up to a target or finding the closest sum to a given target.

Companies that Ask the Two Sum Problem

The Two Sum problem is a popular interview question at many top tech companies, including:

Amazon
Google
Facebook
Microsoft
Apple
Netflix
Uber
Airbnb
Dropbox
... and many others