First Week of Algorithm Immersion

In my last blog entry I detailed a rough outline for my plans of studying data structures and algorithms going forward.

Since this was my first week attempting to implement that system, I will relay some things I’ve learned.

Ive gotten much more comfortable using hashes to store data to avoid having to use nested loops. The main algorithm I used this on is an easy level problem on Leetcode called Two Sum. This problem asks you to take an array of integers and find the two integers inside the array that add up to a passed in target value.

The brute force way to do this would be to make a for loop and then another for loop inside of the first one and compare each element to the other elements in the array resulting in O(n²) time complexity.

The more efficient way to do this was this:

for(let i = 0; i <len; i++){
      let currentNum = nums[i]
      let comp = target - currentNum
      
      let indexTwo = previousNums[comp]
      if(indexTwo !== undefined){
           return [indexTwo,i ]
      }
      else{
          previousNums[currentNum] = i
      }
    
  }

After initializing the for loop, I set a variable currentNum to the value of nums[i], then I set a variable comp to the value of the difference between the passed in target and currentNum.

Above the for loop I initialized an empty javascript object previousNums:

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

The variable indexTwo is then set to the value of previousNums[comp].

By checking if the value of indexTwo existed in my javascript object (and if it did not exist, proceeding to store it so it did exist), I was able to find the correct answer without resorting to a nested loop thus avoiding O(n²) time complexity.

This is a slow process but I definitely feel myself improving.