My resources for this blog post is Colt Steel's course on Udemy, which can be found here. I'm essentially taking notes during the video lecture, slowly making sure I understand and explore every detail of the lectures.

(a continuation from my last blog post on DS & A)...

Where do these logarithms show up?

Certain searching algorithms have logarithmic time complexity.
Efficient sorting algorithms involve logarithms.
Recursion sometimes involves logarithmic space complexity.

Objects are generally fast, and there is no order. Simply a collection of keys and values.

Big O of objects

Insertion - O(1)
Removal - O(1)
Searching - O(n)
Access. - O(1)

Big O of object methods

Object.keys. - O(n)
Object.values. - O(n)
Object.entries. - O(n)
hasOwnProperty. - O(1)

Big O of array methods

Insertion - it depends...
Removal - it depends...
Searching - O(n)
Accessing - O(1)

It is always more costly in time complexity to insert or remove a value from an array if we do so from the beginning or middle. O(n). When insertion or removal is done from the last index it becomes less costly O(1) ....such methods in JavaScript are the push() and pop() methods.

Steps to Problem Solving

Understand the problem

Restate the problem/question in your own words.
What are the inputs, what are the outputs?
Can the outputs be determined from the inputs?
How should I label important pieces of data when resolving the problem?

Explore concrete examples

Start with simple examples
Then move on to more complex examples
Explore edge cases like empty inputs and invalid inputs

Break it down

Write sudo code, talk about the steps out loud; not every line of code, just a general idea of what steps you plan on taking.

Solve/Simplify

Solve the problem if you can, if not solve a portion of the problem.

Look back and refactor

It is important to take time to improve your code. Line by line, how it reads. What about efficiency? (Space and Time Complexity).

Is there a different approach to solve this problem?

Can you use the solution for another problem?

At least reflect on what you wrote.

Below is an example of a problem with comments each step of the way. The result returns an object with a character count for each occurrence with in a string.

let myString2 = "Your PIN is 1234!"

function charCount(str){
  // make an object to return at end
  let result = {}
  // loop over string, for each character...
  for (let i = 0; i<str.length; i++){
    // if the char is a num/letter AND is a key in obj, add one to count
    // handle uppercase letters
    // handle if the char is a space, period, special char, etc.
    let char = str[i].toLowerCase()

    if(/[a-z0-9]/.test(char)){

    if(result[char]>0){
      result[char]++
       // if the char is a num/letter and not in obj, add it to obj set value to 1
    }else{
      result[char] = 1
    }

  }  
  }   
  // return obj at end


return result
}

After reviewing the above solution, there are a few things we can do to refactor the code and make it cleaner. See below.


function charCount(str){
  let result = {}
  for (let char of str){
    if(isAlphaNumeric(char)){
    char = char.toLowerCase()
    result[char] = ++ result[char] || 1;
    }  
  }  
return result
}


function isAlphaNumeric(char){
  let code = char.charCodeAt(0)
  if(!(code > 47 && code < 58) && // numeric (0-9)
      !(code > 64 && code < 91) && // upper alpha (A-Z)
      !(code > 96 && code < 123)){ // lower alpha (a-z)
        return false;
      }
      return true;
}

I'm going to isolate the line below for future reference because I think it's a neat short hand. (If result[char] is truthy, add one to it, else initialize the value one).

  result[char] = ++ result[char] || 1;

Some Common Patterns to know

Frequency Counter
Multiple Pointers
Sliding Window
Divide and Conquer
Dynamic Programming
Greedy Algorithms
Backtracking
...Many more!

Frequency Counter Pattern

This pattern uses objects or sets to collect values/frequencies of values.
Often is used to avoid using nested loops or O(N^2) operations with arrays /strings

Below is an example of a "naive approach" to solving this problem. There is a nested loop present(indexOf inside the for loop) O(N^2) no bueno :)

// write a function called same, which accepts two arrays. 
// The function should return true if every value in the array 
// has its corresponding value squared in the second array. 
// The frequency of values must be the same.

let arr1 = [1,2,3]
let arr2 = [4,1,9] // returns true

// let arr1 = [1,2,3]
// let arr2 = [1,9]  // returns false

// let arr1 = [1,2,1]
// let arr2 = [4,4,1]  // returns false

function same(arr1, arr2){
    if(arr1.length !== arr2.length){
      return false
    }
    for(let i = 0; i < arr1.length; i++){
      let correctIndex = arr2.indexOf(arr1[i] ** 2)
      if(correctIndex === -1){
        return false;
      }
      arr2.splice(correctIndex, 1)
    }
    return true
}

Below is the same problem refactored to a "frequency counter pattern" and has a time complexity of O(3n), which simplifies to O(n).

function same(arr1, arr2){
    if(arr1.length !== arr2.length){
      return false
    }
    let frequencyCounter1 = {} 
    let frequencyCounter2 = {}
    for (let val of arr1){
      frequencyCounter1[val] = (frequencyCounter1[val] || 0) +1
    }
    for (let val of arr2){
      frequencyCounter2[val] = (frequencyCounter2[val] || 0) +1
    }
    for(let key in frequencyCounter1){
      if(!(key ** 2 in frequencyCounter2)){
        return false
      }
      if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
        return false
      }
    }
    return true
}

Using the frequency counter pattern, solve an anagram challenge using two strings.

my solution:

function validAnagram(str1, str2){

  if(str1.length !== str2.length){
    return false
  }

  let frequencyObject1 = {}
  let frequencyObject2 = {}


  str1 = str1.split('')
  str2 = str2.split('')

  for(let char of str1){
    frequencyObject1[char] = (frequencyObject1[char] || 0) +1
  }
  for(let char of str2){
    frequencyObject2[char] = (frequencyObject2[char] || 0) +1
  }

  console.log(frequencyObject1)
  for(let key in frequencyObject1){
    if(frequencyObject1[key] !== frequencyObject2[key]){
      return false
    }

  }
return true
}

Once you grasp the technique above with the 'frequency counting pattern' it becomes easy to solve other similar problems. See below a more elegant solution Colt Steel provides in his lecture:

function validAnagram(str1, str2){
  if(str1.length !== str2.length){
    return false
  }
  str1 = str1.split('')
  str2 = str2.split('')

  let frequencyObject = {}

  for(let char of str1){
    frequencyObject[char] = (frequencyObject[char] || 0)  + 1
  }
   for(let char of str2){
     if(!(frequencyObject[char])){
       return false
     }
     frequencyObject[char] -= 1
   }
   return true
}

Multiple Pointers Pattern

This is a pattern where you loop through an array once, shifting which indices are being compared. You can start at the beginning, end or both sides of an array until you meet in the middle. Below is an example where you look for the count of unique values in an array, starting at index 0 and index 1. If the values are not the same, increment i and replace its value with j. At the end return i + 1 to return the number of unique values.

function countUniqueValues(sortedArr){
    if (sortedArr.length === 0 ){
        return 0
    }
   let i = 0
   for(let j =1; j<sortedArr.length; j++){
       if(sortedArr[i] !== sortedArr[j]){
           i ++
           sortedArr[i] = sortedArr[j]

       }
     }
     console.log(i+1)
   return i + 1
}

Sliding Windows Pattern

Below is another pattern that is useful when avoiding nested loops. Given an array of numbers, and a given single number that represents the number of consecutive integers to add together, find the largest sum of those numbers in the array. Confused yet? Essentially, we create a sliding window and each time it shifts to the right, the digit to the left is subtracted while the digit to the right is added.

function maxSubArraySum(arr, num){
  if(num > arr.length){
    return null
  }
  let maxSum = 0;
  let tempSum = 0;

  for(let i = 0; i < num; i++){
    maxSum += arr[i]
  }
  tempSum = maxSum

  for(let i = num; i < arr.length; i ++){
    tempSum = tempSum - arr[i - num] + arr[i]
    maxSum = Math.max(maxSum, tempSum)
  }
  return maxSum
}

Code Challenges

Screen Shot 2022-02-12 at 2.04.00 PM.jpg

My solution:

function sameFrequency(num1, num2){
  num1 = num1.toString()
  num2 = num2.toString()
  if(num1.length !== num2.length){
      return false
  }

  let frequencyObj1 = {}
  let frequencyObj2 = {}

  for(let char of num1){
      frequencyObj1[char] = (frequencyObj1[char] || 0) + 1
  }
    for(let char of num2){
      frequencyObj2[char] = (frequencyObj2[char] || 0) + 1
  }

  for(let key in frequencyObj1){
      if(frequencyObj1[key] !== frequencyObj2[key]){
          return false
      }
  }
  return true
}

This one was fairly straight forward and simple to solve. My first thought was to build up two objects for comparison using the frequency counter pattern.

Screen Shot 2022-02-12 at 2.08.24 PM.jpg