LeetCode TwoSum JavaScript Solution

LeetCode TwoSum JavaScript Solution

O(n) and O(1) solutions

The Problem:

Given an array of integers, and a given target, return two unique indices of numbers that add up to the given target.

The Pseudocode - O(n)

  1. Create an outer for loop
  2. Create an inner for loop
  3. If the outer and inner indexes are not similar
  4. And if nums at outer index and nums at inner index add up to target
  5. Return array holding two indices

The Solution - O(n)

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let k = 0; k < nums.length; k++) {
            if (i !== k) {
                if (nums[i] + nums[k] === target) {
                    return [i, k];
                }
            }
        }
    }
};

The Pseudocode - O(1)

  1. Create an object (hash)
  2. Create a loop
  3. Check if the object at key of (Target - Nums at Index) is not undefined
  4. If it is not undefined, return array holding our loop's index of i at position 0, and our hash's value at key of Target - Nums at Index
  5. Else, set a property on our hash of key Nums at Index and value of Index

The Solution - O(1)

var twoSum = function(nums, target) {
    let result = {};
    for (let i = 0; i < nums.length; i++) {   
        if (result[target - nums[i]] !== undefined) {
            return [i, result[target - nums[i]]];
        } else {
            result[nums[i]] = i;
        }
    }
};

O(1) Video Walkthrough