Master common problem solving patterns

Frequency Counter

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 / strings.

Problem 1

Write a function called same, which accepts two arrays. The function should return true if every value in the array has it's correspoding value squared in the second array. The frequency of values must be the same. (The order doesn't matter.)

Example 1

same([1, 2, 3], [4, 1, 9]); // true
same([1, 2, 3], [1, 9]); // false
same([1, 2, 1], [4, 4, 1]); // false (must be same frequency)

Solution 1 - A navie approach

// Time Complexity - O(N^2)
function same(arr1, arr2) {
  if (arr.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;
}

Solution 2 - Refactoring

// Time Complexity - 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;
}

Problem 2 - Anagrams

Given two strings, write a function to determine if the second string 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. You may assume the string contains only lowercase alphabets.

Example 1

validAnagram("", ""); // true
validAnagram("aaz", "zza"); // false
validAnagram("anagram", "nagaram"); // true
validAnagram("rat", "car"); //false
validAnagram("awesome", "awesome"); // false
validAnagram("qwerty", "qeywrt"); // true
validAnagram("texttwisttime", "timetwisttext"); // true

Solution 1 - Mine

// Time Complexity - O(N)
function validAnagram(str1, str2) {
  if (str1.length !== str2.length) {
    return false;
  }

  var freCounter1 = {};
  var freCounter2 = {};

  for (let char of str1) {
    freCounter1[char] = (freCounter1[char] || 0) + 1;
  }
  for (let char of str2) {
    freCounter2[char] = (freCounter2[char] || 0) + 1;
  }
  for (var key in freCounter1) {
    if (!(key in freCounter2)) {
      return false;
    }
    if (freCounter1[key] !== freCounter2[key]) {
      return false;
    }
  }
  return true;
}

Solution 2 - Refactoring

// Time Complexity - O(N)
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);
  }

  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;
}