Frequency counting is a technique where you use a HashMap (or a fixed-size array) to keep track of how many times each element appears in a collection. This often allows you to solve "counting" and "uniqueness" problems in $O(n)$ time.

Imagine you're sorting a bag of M&Ms by color:

• Inefficient way: You pick a red one, then count every red one in the bag. Then pick a blue one, count all blues...
• Efficient way (Frequency Count): You have a piece of paper with "Red", "Blue", "Green" written on it. You pick an M&M, see it's Red, and put a tally mark $|$ next to "Red". You go through the bag only once. At the end, you know exactly how many of each you have.

---

Why it's powerful

Many brute-force solutions involve nested loops ($O(n^2)$) to compare elements. By using a frequency map, you can store everything you've seen in one pass ($O(n)$) and then check your results.

When to use an Array vs. Map

• Use an Array: When the "keys" are limited and known (e.g., counting 26 lowercase English characters). It's faster and uses less memory.
• Use a Map: When the keys are unpredictable or sparse (e.g., counting random integers or long strings).

---

javascript Standard
/**
 * Finding the First Non-Repeating Character in a string.
 * This is a classic application of frequency counting.
 */
function firstUniqChar(s) {
  const count = new Map();

  // 1. Build the frequency map (First Pass)
  for (let char of s) {
    count.set(char, (count.get(char) || 0) + 1);
  }

  // 2. Find the first character with a count of 1 (Second Pass)
  for (let i = 0; i < s.length; i++) {
    if (count.get(s[i]) === 1) {
      return i; // Return the index
    }
  }

  return -1;
}

// Example
console.log(firstUniqChar("interviewforge")); // 0 ('i' is unique)
console.log(firstUniqChar("aabbcc")); // -1

---

Variations to Practice

• Is Anagram: Check if two strings have the exact same character frequencies.
• Top K Frequent Elements: Build a frequency map, then use a Min-Heap or Bucket Sort to find the top $K$.
• Subarray Sum Equals K: Use a running prefix sum and a frequency map of previous sums.

Pro-Tip

If the problem involves "Comparing two sets of things to see if they match," a frequency map is almost always the intended solution.