Problem Solving Patterns

                   -Problem Solving Patterns
                   -Frequency Counter Patterns
                   -Multiple Pointers Patterns 
                   -Sliding Window Pattern
                   -Divide and Conquer Pattern 

Problem Solving Patterns

These are some common patterns to solving problems with code.

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

There are many different approaches to solving common problems.

Frequency Counter Patterns

A frequency counter uses objects or sets to collect values and frequencies. May often avoid the need for nested loops operations with array and strings.

Frequency Counter Problem

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.

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])

Anagram Problem

Given two strings, write a function to determine if the second string is an anagram of the first.

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 Patterns

Creating pointers or values that correspond to an index or position and move towards the beginning, end, or middle based on certain condition.

Multiple Pointers is very efficient for solving problems with minimal space complexity as well.

Sum Zero Problem

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])

Count Unique Values Problem

Implement a function called countUniqueValues, which accepts a sorted array, and counts the unique values in the array. There can be negative numbers in the array, but it will always be sorted.

function countUniqueValues(arr){
    if(arr.length === 0) return 0;
    var i = 0;
    for(var j = 1; j < arr.length; j++){
        if(arr[i] !== arr[j]){
            i++;
            arr[i] = arr[j]
        }
    }
    return i + 1;
}
countUniqueValues([1,2,2,5,7,7,99])

Sliding Window Pattern

This pattern involves creating a window which can be either an array or number from one position to another. Depending on a certain condition, the window either increases or closes and a new window is created.

Very useful for keeping track of a subset of data in an array/string.

Max Subarray Sum Problem

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)

Write a function called maxSubarraySum which accepts an array of integers and a number called n. The function should calculate the maximum sum of n consecutive elements in the array.

Divide and Conquer Pattern

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

This pattern can decrease time complexity.

Divide and Conquer Problem

Given a sorted array of integers, write a function called search, that accepts a value and returns the index where the value passed to the function is located. If the value if not found, return -1.

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; 

}