LeetCode Two Sum JavaScript

Two Sum

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

What are our assumptions and are there any edge cases?

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.

NOTE: It was shared with me that unless specified, assume assume an array is unsorted.

Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

Input: nums = [3,3], target = 6
Output: [0,1]

Brute Force Method

Think through before coding:

1. Need to iterate or go through the entire array.
2. Need to select the first value in the array.
3. Then traverse the remaining values of the array.
4. Check to see if one of the values when added will get the target.

function twoSum (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 [i, j];
    }
  }
}

We create two for loops and check each number against each other number. If the numbers match the target when added, we return the indices.

Input: nums = [2,7,11,15], target = 13

Starting with the 2, index 0, we would add the following indices one at a time to see if index 0 plus that index would equal our target (13).

 2 + 7 = 9
[0] [1]

 2 + 11 = 13
[0]  [2]

With this brute force method, new space complexity is not created O(1); however, our time complexity is O(N)^2. This leaves us with constant space and quadratic time.

Two Pointer:

If our array is unsorted ( nums = [11, 7, 2, 15]), we could perform a sort operation which would add n log n and get us back to nums = [2,7,11,15].

We could use a Two Pointer approach with an i variable at the start of the index and a j variable at the end of the index:

Target is 13

2, 7, 11, 15
i          j

We will check if the sum of the two variables is greater than, less than or equal to the target. As i + j = 17 is greater than our target of 13, we decrement the j:

Target is 13

2, 7, 11, 15
i      j

i + j = 13 which meets our target. If the problem did not require returning the indices, we would be able to get away with what we have. Since we sorted the array, we would need to have:

1. Made a copy of the original array.
2. Sort the copy array.
3. Found the two numbers that met the target.
4. Run the numbers over the original array to get the indices.
5. Return the indices.

This would give us a time complexity of O(n log n) due to our sort operation and a space complexity of O(n) due to copying the original array and not performing in constant space.

The example code below has a time complexity is O(n) because it utilizes a while loop that iterates through the entire array of numbers once. The number of operations inside the loop is constant (checking if the sum is equal to the target, incrementing/decrementing the pointers). The space complexity is O(1) because the code only uses a constant amount of additional memory for the variables (leftPointer, rightPointer, and sum) regardless of the size of the input array.

// Declare a function called twoSum with two parameters, nums and target
function twoSum(nums, target) {
  // Create a variable called leftPointer and set it equal to the first element in the nums array
  let leftPointer = 0;
  // Create a variable called rightPointer and set it equal to the last element in the nums array
  let rightPointer = nums.length - 1;
  // Create a while loop that continues as long as the leftPointer is less than the rightPointer
  while (leftPointer < rightPointer) {
    // Create a variable called sum and set it equal to the value of the element at the leftPointer index added to the value of the element at the rightPointer index
    let sum = nums[leftPointer] + nums[rightPointer];
    // Check if the sum is equal to the target
    if (sum === target) {
      // If it is, return an array containing the leftPointer and the rightPointer
      return [leftPointer, rightPointer];
    } else if (sum < target) {
      // If the sum is less than the target, increment the leftPointer
      leftPointer++;
    } else {
      // If the sum is greater than the target, decrement the rightPointer
      rightPointer--;
    }
  }
  // If no match is found, return -1
  return -1;
}

Hash:

Target = 9
Input: nums = [ 2, 7, 11, 15 ]
Indices:       [0] [1] [2] [3]

We want to create a hash and set the values from the array to the keys in the hash and indices of the array being values of the keys.

hashPseudo = {
  valueInArray: index,
  valueInArray: index,
  valueInArray: index,
  valueInArray: index
}

hash = {
  2: 0,
  7: 1,
  11: 2,
  15: 3
}

Now we iterate over the array to figure out a potential value and compare it to see if the number is in the hash.

//Defines a variable called twoSum that is assigned an anonymous function.
//Function takes in two parameters, an array called nums and a target number.
var twoSum = function(nums, target) {

//Initialize a variable called map as a new instance of the Map object.
    let map = new Map();

//Use a for loop to iterate through the nums array, starting at index 0.
    for (let i = 0; i < nums.length; i++) {

//Inside the for loop, two variables called num1 and num2 are defined.
//num1 is set to the current element of the nums array at the current index.
        let num1 = nums[i];

//num2 is set to the target minus num1.
        let num2 = target - num1;

//Check if map has a key of num2.
//If it does, the function returns an array containing the current index and
//the value associated with the key of num2 in the map.
        if (map.has(num2)) {
            return [i, map.get(num2)];
        }

//If map does not have a key of num2, the function adds the current element of
//the nums array (num1) as a key and the current index as the value in the 
//map object.
        map.set(num1, i);
    }
};

The time complexity is O(n) because the code iterates through the input array once and the operations inside the loop (checking if the map has a key, adding a key-value pair to the map) are constant. The space complexity of this code is O(n) as well because the map object stores a key-value pair for each element in the input array.