Nested Loops vs. Frequency Counters: Writing More Efficient JavaScript Code

Problem Statement

Write a function called same that accepts two arrays. The function should return true if every value in the first array has its corresponding squared value in the second array. Additionally, the frequency of occurrences must match, meaning that if a number appears multiple times in the first array, its squared value must appear the same number of times in the second array.

Example Cases

same([1, 2, 3], [1, 4, 9]); // true
same([1, 2, 3], [1, 9]);    // false (missing 4)
same([1, 2, 1], [4, 1, 1]); // false (frequency mismatch)
same([3, 3, 2], [9, 9, 4]); // true

Approach 1: Nested Loop

const same = (arr1, arr2) => {
  if (arr1.length !== arr2.length) return false;

  for (let i = 0; i < arr1.length; i++) {
    let correctIndex = arr2.indexOf(arr1[i] ** 2);
    if (correctIndex === -1) {
      return false;
    }
    arr2.splice(correctIndex, 1);
  }

  return true;
};

Explanation:

• Purpose:
  The function sameNumbers is designed to check whether every value in arr1 has a corresponding squared value in arr2, while also ensuring that the frequency of occurrences is the same in both arrays.

  Algorithm:

  1. First, the function checks whether the lengths of arr1 and arr2 are the same. If they are not, it immediately returns false because the arrays cannot have the same squared values if their sizes are different.

  2. Then, it loops through each element in arr1.

  3. For each element in arr1, it computes its square and looks for this squared value inside arr2 using the indexOf method.

  4. If the squared value is found, it removes that value from arr2 using splice to ensure that duplicates are counted correctly.

  5. If at any point a squared value is not found in arr2, the function returns false.

  6. If the loop completes without returning false, the function returns true, meaning arr2 contains the squared values of arr1 with the correct frequency.

Complexity Analysis:

• The function contains a loop that iterates through arr1 (O(n)).

• Inside this loop, the indexOf method is used to search for an element inside arr2, which has a worst-case time complexity of O(n).

• Since indexOf is inside the loop, this results in an overall time complexity of O(n²).

• Additionally, splice is used, which itself has a complexity of O(n) in the worst case, further impacting performance.

• This quadratic complexity makes the function inefficient for large input sizes.

  Approach 2: Frequency Counter

    const same = (arr1, arr2) => {
      if (arr1.length !== arr2.length) return false;

      let freqCounter1 = {};
      let freqCounter2 = {};

      // Populate frequency counters for both arrays
      for (let num of arr1) {
        freqCounter1[num] = (freqCounter1[num] || 0) + 1;
      }
      for (let num of arr2) {
        freqCounter2[num] = (freqCounter2[num] || 0) + 1;
      }

      // Compare frequency counters
      for (let key in freqCounter1) {
        if (!(key ** 2 in freqCounter2)) {
          return false;
        }
        if (freqCounter1[key] !== freqCounter2[key ** 2]) {
          return false;
        }
      }

      return true;
    };

Explanation:

• Purpose:
  The function same serves the same purpose as sameNumbers, but it utilizes the frequency counter pattern, which significantly improves efficiency.

  Algorithm:

  1. First, it checks if the lengths of arr1 and arr2 are the same. If not, it returns false immediately.

  2. It creates two frequency counter objects: freqCounter1 and freqCounter2.

     • freqCounter1 keeps track of how often each number appears in arr1.

     • freqCounter2 keeps track of how often each number appears in arr2.

  3. It iterates through arr1, populating freqCounter1, and then iterates through arr2, populating freqCounter2.

  4. After building the frequency counters, it loops through freqCounter1 and:

     • Check if the square of each key in freqCounter1 exists as a key in freqCounter2. If not, it returns false.

     • Compares the frequency of the squared value in freqCounter2 with the frequency of the original value in freqCounter1. If they don’t match, it returns false.

  5. If all checks pass, the function returns true, confirming that arr2 contains the squared values of arr1 with the correct frequency.

Complexity Analysis:

• Constructing freqCounter1 and freqCounter2 each takes O(n) time since we iterate through both arrays once.

• Checking if each squared value exists in freqCounter2 is an O(1) operation for each key, resulting in an overall complexity of O(n).

• Compared to the nested loop approach, this is a significant improvement, making the function much more efficient for large datasets.

Conclusion

When solving problems involving array comparisons, choosing the right algorithmic approach can have a major impact on performance. The nested loop method has a time complexity of O(n²) due to repeated searches inside the second array, making it inefficient for larger input sizes. In contrast, the frequency counter method optimises the process to reduce the time complexity to O(n).

By leveraging frequency counters, we eliminate unnecessary nested loops, making our code more scalable and efficient. This optimisation is especially important in real-world applications where performance matters, such as handling large datasets, optimising search operations, or improving execution time in web applications.

Understanding and applying the right algorithmic techniques can help developers write cleaner, faster, and more efficient code. Always consider alternative approaches when solving problems to achieve the best performance possible.