Leetcode - Two Sum algorithm (with JavaScript)

Today I am going to show how to solve the Leetcode Two Sum algorithm problem.

Here is the 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
    }
}