LeetCode 1 — Simplest Solution to TwoSum Problem

When it comes to honing your coding skills, LeetCode is an excellent platform with a plethora of challenges to solve. As junior to mid-level developers, there’s one particular problem that you’re likely to come across early on: “Two Sum”. In this problem, you’re given an array of integers and a target value, and the task is to find two numbers in the array that add up to the target value. But don’t worry, we’ve got you covered. This article will guide you through different solutions and offer a detailed analysis of this popular LeetCode question.

Understanding the Problem: What is “Two Sum”?

The “Two Sum” problem is simple yet intriguing. Suppose you have an array, say [2, 4, 7, 11], and a target value, like 9. You’re required to find two numbers in this array that add up to your target value, and then return their indices. In our example, the numbers 2 and 7 add up to 9, and their indices are 0 and 2, respectively. Therefore, the output should be [0, 2].

Diving into the Brute Force Solution

The brute force solution for the “Two Sum” problem involves comparing each element with every other element in the array. If we find a pair that adds up to the target sum, we return their indices. Sounds easy, right? Let’s break it down using the array [4, 2, 11, 7] and the target value 9 as an example.

Here’s how it works:

1. Start by comparing the first number, 4, with all other numbers.

2. Find that 4 + 2 equals 6, 4 + 11 equals 15, and 4 + 7 equals 11. None of these is the target value.

3. Move on to the second number, 2, and compare it with the remaining numbers.

4. Find that 2 + 11 equals 13, and 2 + 7 equals 9. Voila! You’ve found your target value, so you return the indices of 2 and 7, which are [1, 3].

This brute force solution has two nested loops, which iterate through each element in the array and checks every element after the current outer loop element. However, while this approach works, it becomes inefficient as the array grows larger due to its time complexity of O(n²).

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

Exploring an Optimal Solution

There’s an optimal way to solve the “Two Sum” problem that involves a single pass through the array and a hash map. This more efficient approach takes advantage of the fact that for each number, we’re simply looking for the difference between the target value and the current value.

Here’s how the optimal solution works using the same example:

1. Initialize an empty hash map to store the numbers you’ve seen and their corresponding indices.

2. Iterate through the array one element at a time.

3. For the first element, 4, calculate the complement by subtracting it from the target value, which is 9–4, equaling 5.

4. Check if the complement (5) exists as a key in your hash map. If it doesn’t, store the current element, 4, as a key and its index, 0, as the value.

1. Repeat this process for each number in the array.

2. When you reach the last element, 7, its complement is 2, which does exist in the hash map! Return the indices of the complement (2) and the current element (7), which are 1 and 3, respectively.

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

This optimal solution reduces the time complexity to O(n) and significantly speeds up the process, especially for large arrays.

Wrapping Up

The LeetCode “Two Sum” problem is a great starting point for developers to sharpen their problem-solving skills and get acquainted with data structures and algorithms concepts. It not only teaches you to think critically about the problem at hand but also exposes you to the concept of time and space complexity. By understanding and implementing these solutions, you’re well on your way to becoming a proficient coder.

I hope you found this article helpful and easy to follow. Keep practicing and happy coding!