Patterns

Frequency Counters

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) {
    if (arr[left] + arr[right] === 0) {
       return [arr[left], arr[right]]
    } else if (sum > 0) {
      right--;
    } else {
      left++;
    }
  }
}