Frequency Counters

frequencyCounters.js

/**
 * These two functions do the same thing.
 * They check if a second array contains squared values of the first array.
 * The first is slow. Every value is compared to each other.
 * The second is faster, it runs through each array only once.
 * The approach of the second function I refer to as a "frequency counter".
 */

function nestedLoop (array1, array2) {
  if (array1.length !== array2.length) {
    return false
  }
  for (let i = 0; i < array1.length; i++) {
    let squaredValue = array1[i] ** 2
    let squareIndex = -1 
    for (let j = 0; j < array2.length; j++) {
      if (array2[j] === squaredValue) {
        squareIndex = j
      }
    }
    if (squareIndex === -1) {
      return false
    } else {
      array2.splice(squareIndex, 1) 
    }
  }
  return true
}

function frequencyCounter (array1, array2) {
  if (array1.length !== array2.length) {
    return false
  }
  // Build frequency counter according to array1's contents.
  // example: frequencyCounter[value] = frequency (a.k.a. times appeared)
  const frequencyCounter = {}
  for (let i = 0; i < array1.length; i++) {
    const key = array1[i]
    if (frequencyCounter[key] === undefined) {
      frequencyCounter[key] = 1
    } else {
      frequencyCounter[key]++
    } 
  }
  
  for (let i = 0; i < array2.length; i++) {
    const key = Math.sqrt(array2[i])
    if (
      frequencyCounter[key] === undefined ||
      frequencyCounter[key] === 0
    ) {
      return false
    } else if (frequencyCounter[key] > 0) {
      frequencyCounter[key]--
    }
  }
  return true
}

console.log(nestedLoop([1,2,3], [1, 4, 9])) // => true O(n^2) time complexity
console.log(frequencyCounter([1,2,3], [1, 4, 9])) // => true O(n) time complexity