Coding Interview Prep: Two Sum With 3 Solutions (Brute Force, Hashtable, 2 Pointers)

Solution 1 — Brute Force

/*
 Brute force method: 2 inner for loops
 Complexity: O(n^2)
 Space: 0(n)
 Runtime: 60 ms
 */
var twoSum_bruteForce = function(nums, target) {
    for (let i=0; i<nums.length; i++){
        for (let j=i+1; j<nums.length; j++){
            if (nums[i]+nums[j] == target){
                return new Array(i, j);
            }
        }
    }
    return [];
};

Solution 2 — Hashing

/*
Hashing Method: map key is the number value in the array, map value is the index
Complexity: ordered map O(n), unordered map O(n^2)
Space: O(n)
Runtime: 69 ms
 */
var twoSum_hashing = function(nums, target){
    const map = new Map();
    for (let i=0; i<nums.length; i++){
        const num = nums[i];
        const complement = target - nums[i];
        if (map.has(complement)){
                    return new Array(map.get(complement), i);
                } 
                map.set(nums[i], i);
            }
            return [];
        }

Hashmap is a data structure that allows you to store key-value pairs. Every JavaScript object is a simple hashmap which accepts a string or a symbol as its key. So the complexity of a search is O(1)

Solution 3–2 Pointer Approach…