In this LeetCode challenge we’re asked to find two numbers in a given array which add up to make a specific number. So in other words, given the array [1, 2, 3] and a target number of 5 , we would return [2, 3].
Disclaimer: We’re actually asked to return the indices of the numbers, not the numbers themselves, but the above made for a much simpler explanation!
This challenge has a variety of solutions, and all revolve more or less around the same concept: For each number in the provided array, check if the complement to each number exists, and if so return the number and its complement.
Wondering what the complement is? In this case, it means “The number that, when added to the current number, makes the target number”. So for example, if you have 3 and need 5, your complement will be 2, because 5 - 3 = 2.
Solution 1: Nested for loop
Here’s a super straightforward example used a nested loop:
In this example we loop through all of the numbers, and then for each number, we once again loop through all of the numbers (excluding the first one, as the question states we cannot use the same number twice), and check if the second number is the required complement to the first one.
This solution works fine, but nested loops like this are slow and generally frowned upon, so let’s look at some other approaches.
Solution 2: Maps
In this example we declare an empty Map and then loop through the array of numbers. For each number, we check if the required complement exists in the Map, returning both numbers if so, or we add the current number into the Map. By the time the loop has reached the end of the array, we then have a map of all values provided (assuming the solution hasn’t already been found).
Maps are incredibly quick for looking up data, so this solution is much faster than the nested for loop approach, but surprisingly it’s not the most common solution I see to this type of answer.
Solution 3: HashMap / Object lookups
Note: In JavaScript, Objects are not straight up HashMaps, but they’re often referred to as such.
In what is a near-identical solution to the Map approach, this method stores the numbers one-by-one in an object, which then allows the program to lookup the value using an object key, rather than looping. This means that — again similar to Maps — we can look up our complement, rather than looping through all of the data to find it.
Comparing the solutions
In reality, both the Map and Object solutions are very similar in terms of performance, and this shows when benchmarking the approaches:
The actual performance of Maps vs Object lookups varies depending on a lot of things, and as JavaScript engines evolve to prioritise one or the other, this will swing back and forth. The stats above are taken directly from LeetCode, and are based on the specific test cases they supply, so as always, your mileage may vary!
One thing that is clear though, is that a nested for loop is a very bad idea.
Top comments (0)