Problem Solving Patterns

cs.slides.com/colt_steele/problem-solving-patterns

 

---

Frequency Counter

This pattern uses objects or sets to collect values/frequencies of values

can often avoid nested loop or O(n^2) operations with arrays/strings

 

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;
        }
        console.log(arr2);
        arr2.splice(correctIndex,1)
    }
    return true;
}

same([1,2,3,2], [9,1,4,4])

 

the idea behind the frequency counter usually use an object 

and you use that object to construct a profile sort of a way of breaking down the contents of an array or a string.

 

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        
    }
    console.log(frequencyCounter1);
    console.log(frequencyCounter2);
    for(let key in frequencyCounter1){
        if(!(key ** 2 in frequencyCounter2)){
            return false
        }
        if(frequencyCounter2[key ** 2] !== frequencyCounter1[key]){
            return false
        }
    }
    return true
}

same([1,2,3,2,5], [9,1,4,4,11])

---

Anagrams

is a word, phrase or name formed by rearrangeing the letters of another.

not only if the letters are in there but also the correct number of times the frequencies are correct.

 

vaildAnagram('cinema', 'iceman')    //true

 

Using Frequency Counter Solution

function validAnagram(str1, str2){
  // add whatever parameters you deem necessary - good luck!
  let str1Arr = str1.split('');
  let str2Arr = str2.split('');
  if(str1Arr.length !== str2Arr.length) return false;
  
  let char1 = {};
  let char2 = {};
  for(let val of str1Arr) {
      char1[val] = (char1[val] || 0) +1;
  }
  for(let val of str2Arr) {
      char2[val] = (char2[val] || 0) +1;
  }

  for( let val of Object.keys(char1) ) {
     if(char1[val] !== char2[val]) {
       return false;
     }
  }
 
  return true;
}

 

another solution without nested loop, only two loops

function validAnagram(first, second) {
  if (first.length !== second.length) {
    return false;
  }

  const lookup = {};

  for (let i = 0; i < first.length; i++) {
    let letter = first[i];
    // if letter exists, increment, otherwise set to 1
    lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }
  console.log(lookup)

  for (let i = 0; i < second.length; i++) {
    let letter = second[i];
    // can't find letter or letter is zero then it's not an anagram
    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
  }

  return true;
}

// {a: 0, n: 0, g: 0, r: 0, m: 0,s:1}
validAnagram('anagrams', 'nagaramm')

 

 

---

 

Multiple Pointers

- Creating pointers or values that correspond to an index or position and

move towards the biginning, end or middle based on a certain condition

- very efficient for solving problems with minimal space complexity

 

ex1 )

Write a function called sumSero which accepts a sorted array of integers.

the function should find the first pair whrer the sum is 0.

looking for something to sums to zero  

 

function sumZero(arr){
    for(let i = 0; i < arr.length; i++){
        for(let j = i+1; j < arr.length; j++){
            if(arr[i] + arr[j] === 0){
                return [arr[i], arr[j]];
            }
        }
    }
}


sumZero([-4,-3,-2,-1,0,1,2,5])

 

ex2) countUniqueValues

counts the unique values in the array. could accepts a sorted array.

function countUniqueValues(arr){
  // add whatever parameters you deem necessary - good luck!
  let i = 0;
  if(!arr.length) return i;
  for(let j = 0; j<arr.length; j++) {
      if(arr[i] !== arr[j]) {
          i++
          arr[i+1] = arr[j];
      }
  }
  return i+1;
}

console.log(countUniqueValues([]));

---

Sliding Window

- involves creating a window which can either be an array or number from one position to another

- very useful for keeping track of a subset of data in an array/string etc.

 

ex)

Write a function called maxSubarraySum which accepts an array of integers and a number called n.

// do not recalculate all again. just subtract the first one and add the next one.
// sliding window
function maxSubarraySum(arr, num){
  let maxSum = 0;
  let tempSum = 0;
  if (arr.length < num) return null;
  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;
}

maxSubarraySum([2,6,9,2,1,8,5,6,3],3)

---

Divide and Conquer

- This pattern involves dividing a data set into smaller chunks and then repeating a process with a subset of data.

- tremendously decrease time complexity

 

quick sort and merge sort , binary search are examples of divide and conquer algorithms

 

ex)

writhe a function called search that accepts a value and it returns the index where that value is found.

pick a middle element and compare whether the value is greater or not.

 

Time Complexity - Log(N) - Binary Search

 

it is commonly useed pattern 

function search(array, val) {
 
    let min = 0;
    let max = array.length - 1;
 
    while (min <= max) {
        let middle = Math.floor((min + max) / 2);
        let currentElement = array[middle];
 
        if (array[middle] < val) {
            min = middle + 1;
        }
        else if (array[middle] > val) {
            max = middle - 1;
        }
        else {
            return middle;
        }
    }
 
    return -1;
}