Frequency counter

Today I wanted to show you multiple ways of dealing with a rather simple problem and why it matters.

The problem

Determining if two arrays contain the same elements with identical frequencies - a common task with significant performance implications for large datasets.

Key Challenge: Avoiding O(n²) time complexity from nested iterations.

Naive implementation

The first solution that probably comes through your mind is the following, loop through the first array and look for each value in the second array. When you do so you'll probably use the findIndex() method or even the find(), but did you know both are actually looping through the array until it finds the match:

function compare(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;

  for (let a of arr1) {
    const similarItem = arr2.find((b) => a === b);
    if (!similarItem) return false
  }

  return true;
}

Performance considerations

• find() performs full array scan per element
• O(n²) time complexity
• Becomes problematic with arrays > 1,000 elements

So what better way to find if each value inside our first array is indeed present in the second one. Well, we still have to loop through both arrays but that's fine as long as we do not have a loop inside a loop (refer to my guide on bigO), let's take a look at how it would look like :

Optimized implementation

function compare(arr1, arr2) {
  if (arr1.length !== arr2.length) return false;

  const frequency = {};
  for (let val of arr1) {
    frequency[val] ? frequency[val]++ : (frequency[val] = 1);
  }

  for (let val of arr2) {
    if (!frequency[val]) return false;
    else frequency[val]--;
  }

  return true;
};

Explanation:

1. Early length check for quick rejection
2. Single pass to build frequency map
3. Second pass to validate against map
4. O(n) time and space complexity

Performance considerations

• Linear time complexity
• Handles duplicate values correctly
• Clear, maintainable logic

Practical Application: Anagram Checker

This logic can be applied to multiple cases, let's take a practical example, a function checking if two strings are anagrams.

function validAnagram(str1, str2) {
  if (str1.length !== str2.length) return false;
  const str1LowerCased = str1.toLowerCase();
  const str2LowerCased = str2.toLowerCase();
  const frequency = {};

  for (let char of str1LowerCased) {
    frequency[char] ? frequency[char]++ : (frequency[char] = 1);
  }

  for (let char of str2LowerCased) {
    if (!frequency[char]) return false;
    else frequency[char] -= 1;
  }

  return true;
};

When Not to Use Frequency Counters

• Memory Constraints: O(n) space may be prohibitive
• Non-Hashable Data: Objects with circular references
• Approximate Matching: When exact matches aren't required
• Streaming Data: When full dataset isn't available at once

Key Takeaways

1. Default to frequency counters for exact matching in large datasets
2. Measure before optimizing - use console.time() to verify bottlenecks
3. Consider tradeoffs between time and space complexity
4. Pattern extends beyond arrays to strings, objects, and more
5. Readability matters - sometimes simple code is better for small datasets

Remember: The best solution depends on your specific constraints and data characteristics.

I hope you enjoyed this as much as I enjoyed writing it. If you have any questions or recommendations, please leave them !