Skip to main content

Frequency Counter Pattern

The Frequency Counter pattern uses objects or sets to collect values/frequencies of values. This pattern can often avoid the need for nested loops or O(n²) operations with arrays/strings.

What is Frequency Counter?​

This pattern uses objects or sets to collect values and their frequencies. It allows us to avoid nested loops or quadratic time operations when comparing pieces of data.

When to Use?​

  • Comparing two arrays or strings to check if they're anagrams
  • Finding if a subset of elements exists in another array
  • Checking if elements in one array are squares of another array
  • Counting occurrences of elements

Common Applications​

  • Anagram validation
  • Pattern matching
  • Frequency analysis
  • Character counting
  • Array comparison

Time Complexity​

Most frequency counter solutions achieve O(n) time complexity, compared to O(n²) with nested loops.

Example Problems​

1. Valid Anagram​

Problem Description​

Write a function to determine if the second string is an anagram of the first string.

Example​

Input: 'anagram', 'nagaram';
Output: true;

Input: 'rat', 'car';
Output: false;

Solution​

function validAnagram(str1, str2) {
	if (str1.length !== str2.length) return false;

	const frequencyCounter = {};

	// Count frequencies of first string
	for (let char of str1) {
		frequencyCounter[char] = (frequencyCounter[char] || 0) + 1;
	}

	// Compare with second string
	for (let char of str2) {
		if (!frequencyCounter[char]) {
			return false;
		}
		frequencyCounter[char]--;
	}

	return true;
}

Time Complexity​

  • Time: O(n)
  • Space: O(n)

2. Same Squared​

Problem Description​

Write a function that accepts two arrays. The function should return true if every value in the first array has its corresponding value squared in the second array.

Example​

Input: [1, 2, 3], [4, 1, 9];
Output: true;

Input: [1, 2, 3], [1, 9];
Output: false;

Solution​

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

	const frequencyCounter1 = {};
	const frequencyCounter2 = {};

	// Count frequencies of both arrays
	for (let val of arr1) {
		frequencyCounter1[val] = (frequencyCounter1[val] || 0) + 1;
	}

	for (let val of arr2) {
		frequencyCounter2[val] = (frequencyCounter2[val] || 0) + 1;
	}

	// Compare frequencies
	for (let key in frequencyCounter1) {
		if (!(key ** 2 in frequencyCounter2)) {
			return false;
		}
		if (frequencyCounter2[key ** 2] !== frequencyCounter1[key]) {
			return false;
		}
	}

	return true;
}

Time Complexity​

  • Time: O(n)
  • Space: O(n)

Practice Problems​

To master the frequency counter pattern, try solving these problems:

  1. Find all duplicates in an array
  2. First non-repeating character
  3. Count unique values in sorted array
  4. Check if two strings are permutations
  5. Most frequent element in array

Common Frequency Counter Strategies​

  1. Using Objects

    • Create object to store frequencies
    • Compare frequencies between objects

  2. Using Maps

    • Use Map for non-string keys
    • Better for complex key types

  3. Using Sets

    • For unique value tracking
    • Quick lookup operations

Tips for Solving Frequency Counter Problems​

  1. Consider edge cases (empty inputs, different lengths)
  2. Choose appropriate data structure (Object vs Map vs Set)
  3. Clear variable names for frequency counters
  4. Handle case sensitivity for strings
  5. Consider space-time tradeoffs

Common Pitfalls​

  1. Forgetting to Check Lengths

    • Always compare lengths first for matching problems

  2. Not Handling Edge Cases

    • Empty inputs
    • Special characters
    • Case sensitivity

Additional Resources​