In this post, we’re going to look at LeetCode’s Two Sum problem and find the most efficient algorithm to solve the problem.
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.
You can return the answer in any order.
The answer to Two Sum is really easy to come by. But that obvious answer is a trap, it’s not the most efficient solution.
I am talking about the brute force method. Something like this:
Notice that we’re using two loops, that’s never a good solution. The time complexity will be
O(n2). In other words, as the list grow larger and larger, the algorithm is going to be exponentially slower.
We want to try solving this only by looping through the list once, and we can achieve that with the help of a hash map.
Now that we’re using a hash map, the time complexity is down to
n represents the length of the array). In the worst case, each element in the array will be visited once before we get our answer.
As for space complexity, it’s also
O(n). In the worst case, the algorithm will have to put each number from the array into the map.
That’s it for Two Sum with TypeScript. 🎉
You can also find the code on my Github.