This week I was worked on an algorithm problem I came across on one of my Udemy courses by Colt Steele. I worked on how to problem-solve common algorithm question types. In particular how to turn an algorithm that would’ve been O(n²) if solved naively to an O(n) notation by using javascript objects instead of having a loop inside of a loop.
27. Frequency Counter Pattern
Write a function called same, which accepts two arrays. The function should return true if every value in the array has its corresponding values squared in the second array. The frequency of values must be the same.
Examples:
Inputs: arrayOne=[1,2,3] and arrayTwo=[4,1,9]
Output: true
Inputs: arrayOne=[1,2,3] and arrayTwo=[1,9]
Output: false
Inputs: arrayOne=[1,2,1] and arrayTwo=[4,4,1]
Output: false (must be the same frequency)
function same(arrayOne, arrayTwo){};
My Process
Understanding The Problem
Before starting to code, I restated the problem in my own words to make sure I fully understood what was needed of me: I need to create a function that accepts two inputs that are both arrays, I’ll name them arrayOne and arrayTwo. Then I have to check if the values in arrayTwo are found in the squared values of arrayOne. All the values must be the same frequency. If arrayTwo has the same values as the squared version of arrayOne then return true, if not — return false
Breaking it Down
Next I commented on my function on the things I needed to do for this problem.
function same(arrayOne, arrayTwo){ // Do something... /* return true if arrayTwo has arrayOne values squared, return false if arrayTwo does NOT have arrayOne values squared at the same frequency */}
For my “Do something…” comment, my plan was to square all the values of arrayOne and compare those squared values of arrayOne to the values in arrayTwo to see if they have the same values, order not mattering, only frequency and occurrence.
function same(arrayOne, arrayTwo){ // square the values of arrayOne
// compare the squared values of arrayOne to see if the values are in arrayTwo /* return true if arrayTwo has arrayOne values squared, return false if arrayTwo does NOT have arrayOne values squared at the same frequency */}
Since in this part of the Udemy course we’re being encouraged to use objects to avoid an O(n²) notation I started to think how I could use it to avoid a loop inside of a loop. So I wanted to create an object, squaredValues, and make the keys the squared values of arrayOne with each key initially having a value of 0.
EXAMPLE
inputs: same([1,2,3],[4,1,9])squaredValues = {
'1': 0
'4': 0
'9': 0
}
This is what I’ve added to my function…
function same(arrayOne, arrayTwo){ // square the values of arrayOne
// compare the squared values of arrayOne to see if the values are in arrayTwo // create an object let squaredValues = {} // loop through arrayOne and make the squared values a key in the squaredValues object for (let i=0; i < arrayOne.length; i++){
squaredValues[(arrayOne[i] * arrayOne[i])] = 0
} /* return true if arrayTwo has arrayOne values squared, return false if arrayTwo does NOT have arrayOne values squared at the same frequency */}
With this object, I would loop through the values in arrayTwo to see if any number in that array can be found in my new object as the key. If it is found, I will add 1 to it’s value pair.
inputs: same([1,2,3],[4,1,9])squaredValues = {
'1': 0
'4': 0
'9': 0
}
The issue I came across in checking to see if my arrayTwo value was in my squaredValues object key was the difference in data types. My array has number type values and the object keys were string types. So I had to do a little conversion of turning those array numbers into a string.
function same(arrayOne, arrayTwo){ // square the values of arrayOne
// compare the squared values of arrayOne to see if the values are in arrayTwo // create an object let squaredValues = {} // loop through arrayOne and make the squared values a key in the squaredValues object for (let i=0; i < arrayOne.length; i++){
squaredValues[(arrayOne[i] * arrayOne[i])] = 0
} // loop through arrayTwo and check if the stringified value is found as a key in the squaredValues object. If it is, add one. Do nothing else if it isn't. for (let j=0; j < arrayTwo.length; j++){
let numb = arrayTwo[j].toString()
if (numb in squaredValues){
squaredValues[numb]++
}
} /* return true if arrayTwo has arrayOne values squared, return false if arrayTwo does NOT have arrayOne values squared at the same frequency */}
So now with our function so far, our squaredValues object should look like this:
// with the following inputs:inputs: same([1,2,3],[4,1,9])
squaredValues = {
'1': 1
'4': 1
'9': 1
}inputs: same([1,2,3],[1,9])
squaredValues = {
'1': 1
'4': 0
'9': 1
}inputs: same([1,2,3],[4,4,1])
squaredValues = {
'1': 1
'4': 2
'9': 0
}
What I want to do is make sure all the values of my squaredValues object are equal to 1. If they are any value other than 1, that means my arrayTwo input does not have the same values as arrayOne squared. What I’m going to is use an object method to get all the values of the key value pairs in an array and then check if every one of those values equal 1. The .every array method inheretenly returns a boolean.
function same(arrayOne, arrayTwo){ // square the values of arrayOne
// compare the squared values of arrayOne to see if the values are in arrayTwo // create an object let squaredValues = {} // loop through arrayOne and make the squared values a key in the squaredValues object for (let i=0; i < arrayOne.length; i++){
squaredValues[(arrayOne[i] * arrayOne[i])] = 0
} // loop through arrayTwo and check if the stringified value is found as a key in the squaredValues object. If it is, add one. Do nothing else if it isn't. for (let j=0; j < arrayTwo.length; j++){
let numb = arrayTwo[j].toString()
if (numb in squaredValues){
squaredValues[numb]++
}
} // if every object key values doesn't equal 1 then return false, otherwise return true. return Object.values(squaredValues).every(el => el == 1) /* return true if arrayTwo has arrayOne values squared, return false if arrayTwo does NOT have arrayOne values squared at the same frequency */}
SOLVED
function same(arrayOne, arrayTwo){ let squaredValues = {} for (let i=0; i < arrayOne.length; i++){
squaredValues[(arrayOne[i] * arrayOne[i])] = 0
} for (let j=0; j < arrayTwo.length; j++){
let numb = arrayTwo[j].toString()
if (numb in squaredValues){
squaredValues[numb]++
}
} return Object.values(squaredValues).every(el => el == 1)}
My Thoughts + Refactoring
This was a cool problem to work on. It helped me work on using objects avoid multi-level looping. After watching Colt Steele solve the problem in his own way, I found an area I could refactor in. At the beginning of the function, I could check to see if both arrayOne and arrayTwo are the same lengths. If they aren’t then that would make the frequency off and I could immediately return false for our algorithm.
function same(arrayOne, arrayTwo){ if (arrayOne.length !== arrayTwo.length){
return false
} let squaredValues = {} for (let i=0; i < arrayOne.length; i++){
squaredValues[(arrayOne[i] * arrayOne[i])] = 0
} for (let j=0; j < arrayTwo.length; j++){
let numb = arrayTwo[j].toString()
if (numb in squaredValues){
squaredValues[numb]++
}
} return Object.values(squaredValues).every(el => el == 1)}
