Frequency Counter Pattern

Back at it again with algorithms !! They still give me anxiety but like with anything else, practice & patience. Also thank God for Udemy and Youtube amiright? One of the things I’m understanding with technical interviews is that it really doesn’t matter so much that you solve a problem but how. Also demonstrating that you understand what’s being asked by asking questions. I’ve been kind of relieved that I haven’t had many live technical interviews because the amount of anxiety it gives me. During this time I’m prepping and really diving into understand algos. I’m trying to work on knowing what I don’t know and with algos, there’s so much that I don’t know. I’ve discovered that there are patterns on how to solve certain problem.

Here’s an algo that wants a function called same, which accepts two arrays. The function should return true if every value in the array has its corresponding value squared in the second array. The frequency of values must be the same. What the hell does that mean? [1,2,3] squared results in [1,4,9], 1 squared is 1, 2 squared is 4 and 3 squared is 9. Write a function!

This solution solves the the problem, but the time complexity is Quadratic O(n²) which is terrible. Firstly there’s nested loops, indexOf is just another type of loop which is nested in the for of loop on line 5. Line 2–5 says if the length of the arrays are not equal go straight to false, because if it the length isn’t the same the a number isn’t going to return a squared at all. Line 6 is where the check of arr2 against arr1 at the index and passes in the square of each value in arr1. Line 7 says that if the correctIndex is -1 return false, for example if we had 5 at the first index in arr1 but not 25 in arr1, return false. Line 10 then removes the squared number found and shortens then array & loop starts again until conditional is met. There’s a more efficient way!

In this solution, instead of having a loop nested within a loop, there’s 2 separate loops. Lines 5 & 6 are objects that will hold the count for the frequency of each individual value in the arrays. The object is holding the key which is the numbers in the array and the value which how many times it occurs in the array. Lines 7–12 is where the logic to do this happens, if a number is in the array add 1, if it occurs again in the array and 1 now making the total 2. Below is another example with a different set of numbers.

The logic is basically, if each element has the same count then the second array is the squared result of the first array. As you can see in the second screenshot, 5 & 11 are also only occurring once but lines 15–19 the code that’s checking if it is squared. Since the value of n doesn’t change how fast the code executes, this solution is O(n) which is ideal. Hope this was clear !!