1
\$\begingroup\$

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.

\$\endgroup\$
8
  • \$\begingroup\$ (The point about frequency is tricky: [-1, 1], [1, 1].) \$\endgroup\$
    – greybeard
    Commented Jul 26, 2022 at 12:45
  • \$\begingroup\$ Did you yourself write the code presented for review? \$\endgroup\$
    – greybeard
    Commented Jul 26, 2022 at 14:15
  • \$\begingroup\$ 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 \$\endgroup\$
    – Blindman67
    Commented Jul 26, 2022 at 15:21
  • 1
    \$\begingroup\$ @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, \$\endgroup\$
    – RONE
    Commented Jul 26, 2022 at 18:11
  • 1
    \$\begingroup\$ @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 \$\endgroup\$
    – Blindman67
    Commented Jul 26, 2022 at 18:34

2 Answers 2

1
\$\begingroup\$

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] ) );

\$\endgroup\$
1
\$\begingroup\$

"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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.