Patterns

Frequency Counters

The idea behind it, is that we're using object usually in javascript to basically collect a bunch of values in their frequencies, and this is useful when you have alogorithms and challenges when you have multiple pieces of data, multiple inputs and you need to compare them, to see if their consist of similar values, if they are anagrams, if their value contained in another value, anytime you comparing peices of data, 2 inputs or more than 2, you can use this pattern

this pattern uses objects or sets to collect values/frequencies of values.

this can often avoid the need for nested loops or O(N^2) operations with arrays and strings.

Example

write a function which accepts two arrays. the function should return true if every value in the array has it's corresponding value squared in the second array. the frequency of values must be the same.

same([1,2,3], [4,1,9]) // true
same([1,2,3], [4,1,6]) // false

function same(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;

  let frequencyCounter1 = {};
  let frequencyCounter2 = {};
  
  for (let val of arr1) {
    frequncyCounter1[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;
}

Anagrams

Given two strings, write a function to determine if the second is an anagram of the first. An anagram is a word, phrase, or name formed by rearranging the letters of another, such as cinema, formed from iceman.

validAnagram("car", "rat"); // false
validAnagram("anagram", "nagaram") // true

ValidAnagram.js

function validAnagram(first, second) {
    let frequencyCounter1 = {};

    for (let val of first) {
        frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
    }

    for (let val of second) {
        if (!frequencyCounter1[val]) {
            return false
        } else {
            frequencyCounter1[val]--;
        }
    }

    return true;
}

Multiple pointers

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

Very efficient for solving problems with minimal space complexity as well.

we have some sort of structure, linear structure, like an array or a string or later on we talk about doubly linked list. for example we are going to searching a pair of values or searching for something to meet a condition, usually we looking for a pair. and we use two references and we work towards to each other.

just to recap, we have a pointer, which is just a variable and we have the second one.

[-4, -3, -2, -1, 0, 1, 2, 5]
"assadsadaskdbsakjdsagd"

Example

write a function called sumZero which accepts a sorted array of integers. The function should find the first pair where the sum is 0. Return an array that includes both values that sum to zero or undefined if a pair does not exist.

sumZero([-3,-2,-1,0,1,2,3]) // [-3, 3]
sumZero([1,2,3]) // undefined

first thing that is important is that our array is sorted, if it was unsorted we were out of luck, we should find other solution.

we could solve this using two for loops inside each other to compare each item to the next item and this naive approch which is not good:

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

Above Solution works but it's not a good solution

We can refactor this using multiple pointers pattern because our array is sorted we could use this pattern.

as you can see our array is sorted, and in our array we know that 4 is smallest number and 5 in largest number.

-4 + 5 = 1

this is to big, we're looking for 0.

Soooooo, what we're doing is move this pointer down. to 2

-4 + 2 = -2

this time it is small it is -2

Sooooo, that means we have to have to add one to left pointer => -3

-3 + 2 = -1

it is still negative,

Soooo we have to add another one to the left side => -2

-2 + 2 = 0

Yessss. that is the first pair.

Refactored Solution:

function sumZero(arr) {
  let left = 0;
  let right = arr.length - 1;

  while(left < right) {
    let sum = arr[left] + arr[right];
    if (sum === 0) {
       return [arr[left], arr[right]]
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
}

that is the two pointers in this case far left and right side. towards the middle. next we're going to solve a problem which we have to start from the same side.

countUniqueValues example

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.

countUniqueValues([1,1,1,1,1,2]) // 2
countUniqueValues([1,2,3,3,3,3]) // 3

remember it should accept a sorted array again.