Today I am going to show how to solve the Leetcode Two Sum algorithm problem.
The simplest solution is just comparing every single possible pair. So we could just have 2 for loops. The first one (i loop) is scanning whole numbers (nums) and the second one (j loop) is starting from i + 1. We will be testing all of them until the sum is equal to the target.
But this solution would be inefficient and time consuming (O(n^2)).
So that we donβt waste as much time, we need a faster approach to determining the solution. For this purpose, we can use a hash table which supports fast lookup in near constant time. ( O(1) - best case; O(n)- worst case)
Note: In the hash table Iβm going to map each element (as a key) to its index (as a value).
1) For creating a hash table, Iβm using a new data structure called Map, which was introduced in ECMAScript 2015.
var twoSum = function(nums, target) {
let map = new Map();
}
2) Next, I iterate through all of the numbers using for loop.
var twoSum = function(nums, target) {
let map = new Map();
for (let i = 0; i < nums.length; i++) {
}
}
3) While I iterate the elements, I also check if the current element's complement already exists in the table. If it exists, I have found a solution and return immediately. Otherwise, I insert an element into the table.
var twoSum = function(nums, target) {
let map = new Map(); //creating hash table
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i];
if (map.has(pairNum)) {
return [map.get(pairNum), i]
}
map.set(nums[i], i); // insert an element into the table
}
}
Top comments (0)