"Frequency Counter Pattern", Can we get other better algorithm having like, O(n) or O(n log n)

Question

Problem Statement :

Write a function called matchSquare, which accept two arrays (arr1, arr2)

Criteria:

1. The function should return true, if every value in the arr1, has its corresponding values squared in the second array arr2
2. The frequency of the values must be the same.

Ex:

matchSquare([1,2,3], [4,1,9]) //true
matchSquare([1,2,3], [1,9]) //false, frequency and length issue
matchSquare([1,2,1], [4,4,1]) //false (Must have the same frequency), 
//because in the arry2, there is 2 4's, which does not have a matching another 2 in the arr1,

My solution (brute force):

function matchSquare(arr1, arr2){
 if(arr1.length !== arr2.length){
 return false;
 }
 for(let i = 0; i < arr1.length; i++){ // This is O(n)
 let correctIndex = arr2.indexOf(arr1[i] ** 2) // This is O(n)
 if(correctIndex === -1) {
 return false;
 } 
 arr2.splice(correctIndex,1) //Here again after splice, the re-index of the arr2,O(n)
 }
 return true;
} 

Together it is O(n^2),

Can we get any better approach here?
An explanation if possible would be helpful.

• greybeard: (The point about frequency is tricky: [-1, 1], [1, 1].)
• greybeard: Did you yourself write the code presented for review?
• Blindman67: O(n^2) is too high for your function. Looks like O(n log(n)). Each number checked either reduces the number of seaches by one (if matched) for the nexr value or returns false (no match).. Note that javascripts Set is considered O(n) for searches thus const matchSquare = (a, b, s = new Set(b)) => a.every(v => s.has(v * v))); will solve in O(n) time
• RONE: @Blindman67, I doubt you understood my question, with your code above the testcase matchSquare([1,2,1], [4,4,1]) should return false. but your code will return true, you are not considering the frequency thing, every item (it may have duplicate items also) from the arr1, should have the same value doubled in arr2,
• Blindman67: @RONE You can use a Map (or second Set) and create it manualy adding a repeat count. Then count repeats down as you find matches

Answer 1

One idea I had. If you copy array1 and square all the values with a map, then sort both arrays, you can use every() to test if they have all the same values at the same indexes. This might be easier to read, but would have to run some tests to compare performance.

function matchSquare( array1, array2 ) {
 if ( array1.length != array2.length ) return false;
 const testArray1 = [...array1].map( item => item ** 2 ).sort();
 const testArray2 = [...array2].sort();
 return testArray1.every( ( item, index ) => item == testArray2[index] );
}
console.log( matchSquare( [1,2,3], [4,1,9] ) );
console.log( matchSquare( [1,2,3], [1,9] ) );
console.log( matchSquare( [1,2,1], [4,1,4] ) );

You could also try using toString() and == on each array, instead of every() for the final comparison to see which is faster.

function matchSquare( array1, array2 ) {
 if ( array1.length != array2.length ) return false;
 const testArray1 = [...array1].map( item => item ** 2 ).sort();
 const testArray2 = [...array2].sort();
 return testArray1.toString() == testArray2.toString();
}
console.log( matchSquare( [1,2,3], [4,1,9] ) );
console.log( matchSquare( [1,2,3], [1,9] ) );
console.log( matchSquare( [1,2,1], [4,1,4] ) );

Answer 2

"Frequency Counter Pattern", Can we get other better algorithm having like, O(n) or O(n log n)? Yes, one example is the answer by dqhendricks using an algorithm of O(n log n) complexity due to the sort of the arrays. Your approach having a quadratic complexity can be reduced to a linear complexity as suggested by blindman67 by the use of Map where the specification requires maps to be implemented "that, on average, provide access times that are sublinear on the number of elements in the collection". So you can take your arr1 array, square the elements and create your map storing the occurrences of the elements:

let map = arr1.map(elem => elem ** 2)
 .reduce((acc, elem) => acc.set(elem, (acc.get(elem) || 0) + 1)
 , new Map());

Then you can use the arr2 elements decrementing the occurrences and checking if all occurrences are equal to 0 (so it is falsy) with the every function:

function matchSquareWithMap(arr1, arr2) {
 let map = arr1.map(elem => elem ** 2)
 .reduce((acc, elem) => acc.set(elem, (acc.get(elem) || 0) + 1)
 , new Map());
 
 arr2.forEach(elem => {
 let noccurrences = map.get(elem);
 if (!noccurrences) { return false; }
 map.set(elem, --noccurrences);
 });
 return [...map.values()].every(elem => !elem);
}
console.log(matchSquareWithMap([1,2,3], [4,1,9]) === true ? 'pass' : 'fail'); 
console.log(matchSquareWithMap([1,2,3], [1,9]) === false ? 'pass' : 'fail'); 
console.log(matchSquareWithMap([1,2,1], [4,4,1]) === false ? 'pass' : 'fail'); 

So you can reach a linear complexity with the use of an additional storing struct like the Map that provide linear access times to its elements.