Solving the ‘Two Sum Problem’ on LeetCode — JavaScript Solutions Walkthrough

Image Source

Introduction

In this post, we will delve into three diverse solutions to the Two Sum Problem in JavaScript, evaluating their time and space complexity to aid in understanding the most optimal approach. A detailed, step-by-step explanation with commented code for each solution is provided to offer deeper insights and clarity after the conclusion, ensuring a comprehensive grasp of the various methods available.

Problem Description

Given an array of integers nums and an integer target, return the indices of the two numbers that add up to the target.

JavaScript Function Signature:

function twoSum(nums, target) {

}

Example 1:

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

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Solution 1: Brute Force Approach

In this approach, we iterate through the entire array, and for each element, we iterate through the remaining elements to find a pair that sums up to the target. This method guarantees a solution if one exists as it checks every possible pair.

JavaScript Code:

function twoSum(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];
      }
    }
  }
}

Time Complexity: O(n²), This is because for each element in the array, we are iterating through the rest of the array to find a pair that sums up to the target. For an array of n elements, this leads to n*n total operations.

Space Complexity: O(1), No additional data structures are used that grow with the input size, thus the space complexity is constant.

Solution 2: Two-Pass Hash Table

In this approach, we use a hash map to reduce the time complexity. First, we add each element and its index to a hash map. Then, we iterate through the array again and check if each element’s complement (target — element) exists in the hash map.

JavaScript Code:

function twoSum(nums, target) {
  const numMap = {};
  for (let i = 0; i < nums.length; i++) {
    numMap[nums[i]] = i;
  }
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (numMap.hasOwnProperty(complement) && numMap[complement] !== i) {
      return [i, numMap[complement]];
    }
  }
}

Time Complexity: O(n), We are iterating through the array twice: first to fill the hash map, and then to find the complement. The time complexity is linear as the number of operations grows linearly with the number of elements in the array.

Space Complexity: O(n), We are using a hash map to store the elements and their indices, leading to linear space complexity.

Solution 3: One-Pass Hash Table

This approach optimizes the Two-Pass Hash Table Approach by only making one iteration through the array. During the iteration, we add each element’s index to a hash map and check if the complement already exists in the hash map.

JavaScript Code:

function twoSum(nums, target) {
  const numMap = {};
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (numMap.hasOwnProperty(complement)) {
      return [numMap[complement], i];
    }
    numMap[nums[i]] = i;
  }
}

Time Complexity: O(n), Even though we are making only one pass through the array, the time complexity remains linear as the number of operations still grows linearly with the number of elements in the array.

Space Complexity: O(n), Like the Two-Pass approach, we are using a hash map to store the elements and their indices, leading to linear space complexity.

Conclusion and Comparison

In solving the Two Sum problem, we’ve explored three distinctive methods, each with its pros and cons.

Brute Force Approach:

• Time Complexity: O(n²)
• Space Complexity: O(1)
• Pros: This is the most straightforward method, requiring no additional data structures or complex logic. It’s easy to understand and implement.
• Cons: The brute force approach is highly inefficient for large datasets as it examines every possible pair, leading to a quadratic time complexity.

Two-Pass Hash Table:

• Time Complexity: O(n)
• Space Complexity: O(n)
• Pros: This method significantly improves the time complexity by utilizing a hash table. The linear time complexity makes it suitable for larger datasets, offering better performance than the brute force approach.
• Cons: It requires additional space to store the hash table, which can be a limitation for extensive datasets.

One-Pass Hash Table:

• Time Complexity: O(n)
• Space Complexity: O(n)
• Pros: This is the most efficient among the three approaches. It optimizes the Two-Pass Hash Table approach by reducing the number of passes to one, which could lead to a faster execution time.
• Cons: Like the two-pass approach, it requires additional space for the hash table.

Final Thoughts

Each method has its place. For smaller datasets or scenarios where space complexity is a crucial concern, the Brute Force Approach might be sufficient. However, its quadratic time complexity makes it unsuitable for processing large datasets. The Two-Pass Hash Table approach offers an excellent middle-ground solution, enhancing time efficiency while keeping the implementation relatively simple. Finally, the One-Pass Hash Table approach stands out as the most time-efficient option, especially beneficial for larger datasets where execution time is paramount.

Your choice should weigh the dataset’s size against the trade-off between time and space complexity. For most real-world scenarios, a linear time complexity solution like the One-Pass Hash Table approach is typically the most beneficial, ensuring optimal performance and efficient resource utilization.

1. JavaScript Arrays: MDN Array
2. JavaScript Objects: MDN Object
3. Time Complexity: Big O Notation

Thank you for reading! If you find this guide helpful, please consider highlighting, clapping, responding or connecting with me on Twitter/X as it’s very appreciated!

Also check out my other Leetcode Walkthrough Lists:

• Palindrome Number Problem

Step-by-Step Explanations with Code Comments

In this section, each solution is broken down, providing the JavaScript code with comments and step-by-step explanations for a deeper understanding.

Solution 1: Brute Force Approach with Comments

function twoSum(nums, target) {
  // Step 1: Iterate over the numbers in the array.
  for(let i = 0; i < nums.length; i++) {
    // Step 2: For each number, iterate over the rest of the numbers in the array.
    for(let j = i+1; j < nums.length; j++) {
      // Step 3: Check if the current two numbers add up to the target.
      if(nums[i] + nums[j] === target) 
        return [i, j];
    }
  }
};

• Step 1: The outer loop iterates over the numbers in the array.
• Step 2: The inner loop iterates over the rest of the numbers for each number from the outer loop.
• Step 3: If a pair sums up to the target, their indices are returned.

Solution 2: Two-Pass Hash Table Approach with Comments

function twoSum(nums, target) {
  // Step 1: Create a map to store numbers and their indices.
  const numMap = {};
  // Step 2: Iterate through the array and add each number and its index to the map.
  for (let i = 0; i < nums.length; i++) {
    numMap[nums[i]] = i;
  }
  // Step 3: Iterate through the array again to find the complement of each number.
  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    // If the complement exists in the map and is not the number itself, return the indices.
    if (numMap.hasOwnProperty(complement) && numMap[complement] !== i) {
      return [i, numMap[complement]];
    }
  }
}

• Step 1: A map (numMap) is created to store numbers and their indices.
• Step 2: The code iterates through the nums array, adding each number and its index to numMap.
• Step 3: The code again iterates through the nums array, calculates the complement for each number, and checks if the complement exists in numMap. If the complement exists and is not the number itself (its index in numMap is not i), the function returns the indices [i, numMap[complement]].

Solution 3: One-Pass Hash Table Approach with Comments

function twoSum(nums, target) {
  // Step 1: Create a map to store numbers and their indices.
  const numMap = {};
  // Step 2: Iterate over the numbers in the array.
  for (let i = 0; i < nums.length; i++) {
    // Calculate the complement for each number.
    const complement = target - nums[i];
    // Step 3: Check if the complement exists in the map. If so, return the indices.
    if (numMap.hasOwnProperty(complement)) {
      return [numMap[complement], i];
    }
    // Step 4: Otherwise, add the current number and its index to the map.
    numMap[nums[i]] = i;
  }
}

• Step 1: A map (numMap) is created to store numbers and their indices.
• Step 2: The code iterates through the nums array.
• Step 3: For each number, it calculates the complement and checks if the complement exists in numMap. If the complement exists in the map, it returns the indices [numMap[complement], i].
• Step 4: If the complement does not exist in the map, it adds the current number and its index to numMap.