Unraveling the LeetCode Two Sum Challenge

In the world of coding and problem-solving, there exist challenges that serve as fundamental building blocks of programming knowledge. One such challenge, often encountered by coding enthusiasts and frequently featured in technical interviews, is the Two Sum problem. At first glance, it may appear deceptively simple, but as we delve into its intricacies, you'll discover that it holds the key to honing your problem-solving skills and unlocking the world of efficient algorithms.

Problem Statement

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

Example:

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

---

Brute Force Approach

The most straightforward way to tackle this problem is by using a brute force approach. Here's the basic idea:

1. Loop through the array.
2. For each element, check if there exists another element in the array that, when added to the current element, equals the target sum.

const twoSum = (nums, target) => {
  for(i=0; i<nums.length; i++) {
    for(j=i+1; j<nums.length; j++) {
      if(nums[i] + nums[j] === target) {
        return [i,j]
      }
    }
  }
};

// Time Complexity:  O(N^2) 
// Space Complexity: O(1)

The Downside of Brute Force

While the Brute Force approach is conceptually simple and guarantees a solution, it's not the most efficient way to tackle the Two Sum problem. The nested loops create a time complexity of O(n^2), where 'n' represents the number of elements in the array. This means that as the size of the array increases, the time it takes to find a solution grows quadratically. In other words, it becomes slow and impractical for large datasets.

---

Optimized Hash table Approach

To enhance our runtime efficiency, we require a more effective method for verifying the existence of the complement within the array and retrieving its corresponding index. What is the optimal approach for preserving a mapping of each element in the array to its index? The answer lies in employing a hash table.

const twoSum = (nums, target) => {
  const obj = {}
  for(let i=0; i<nums.length; i++) {
    const comp = target - nums[i];
    if(comp in obj) return [i,obj[comp]];
    obj[nums[i]] = i
  }
};

// Time Complexity:  O(N) 
// Space Complexity: O(N)

We can reduce the lookup time from O(n) to O(1) by trading space for speed. We achieve faster runtime at the expense of using more memory. In most cases, this tradeoff is acceptable, as modern computers typically have sufficient memory.

In conclusion, the optimized Hash table approach is an elegant and efficient solution to the Two Sum problem. It strikes a balance between time and space complexity, providing a scalable solution for most real-world scenarios.

Thank you for reading, and happy coding! 🚀