Chapter 32

Home

Refactoring: Frequency Counting

Now that you know maps, the obvious frequency-count approach is a simple loop. But the refactored version uses edge-aware patterns that handle missing keys, default values, and bulk updates in one line.

The Problem: Most Frequent Element

Given an array of N integers, find the element that appears the most times. If there's a tie, return the smallest value.

Before: Nested Loop Counting

The beginner approach: for each element, count how many times it appears by scanning the whole array. O(N²) and painfully slow for large inputs.

C++ — O(N²) nested loops

int most_frequent_naive(vector<int>& arr) {
    int n = arr.size();
    int best_val = arr[0], best_count = 0;

    for (int i = 0; i < n; i++) {
        int count = 0;
        for (int j = 0; j < n; j++) {
            if (arr[j] == arr[i]) count++;
        }
        if (count > best_count ||
           (count == best_count && arr[i] < best_val)) {
            best_count = count;
            best_val = arr[i];
        }
    }
    return best_val;
}

Rust — O(N²) nested loops

fn most_frequent_naive(arr: &[i32]) -> i32 {
    let n = arr.len();
    let mut best_val = arr[0];
    let mut best_count = 0;

    for i in 0..n {
        let count = arr.iter().filter(|&x| *x == arr[i]).count();
        if count > best_count ||
           (count == best_count && arr[i] < best_val) {
            best_count = count;
            best_val = arr[i];
        }
    }
    best_val
}

🚨 This is O(N²)

For N = 10⁵, that's 10¹⁰ operations — about 10 seconds even in C++. A contest judge would time out. We can do this in O(N) with a map.

After: Single Pass with a Map

One pass to count frequencies (O(N)), one pass over the map to find the best (O(K) where K ≤ N). Total: O(N).

C++ — O(N) with unordered_map

int most_frequent(vector<int>& arr) {
    unordered_map<int, int> freq;
    int best_val = arr[0], best_count = 0;

    // Single pass: count
    for (int x : arr) {
        int c = ++freq[x];
        // Track best as we go
        if (c > best_count ||
            (c == best_count && x < best_val)) {
            best_count = c;
            best_val = x;
        }
    }
    return best_val;
}

Rust — O(N) with HashMap

use std::collections::HashMap;

fn most_frequent(arr: &[i32]) -> i32 {
    let mut freq: HashMap<i32, i32> = HashMap::new();
    let mut best_val = arr[0];
    let mut best_count = 0;

    for &x in arr {
        let c = freq.entry(x).or_insert(0);
        *c += 1;
        if *c > best_count ||
           (*c == best_count && x < best_val) {
            best_count = *c;
            best_val = x;
        }
    }
    best_val
}

💡 Track the best during the count pass

You could make two passes (count, then scan the map). But tracking the best value during the counting pass is just as fast and saves a loop. Each time a count updates, check if it's the new champion.

Extending the Pattern: Anagrams

An anagram check is just frequency counting on two strings — the maps must be identical.

C++ — anagram check

bool is_anagram(const string& s, const string& t) {
    if (s.size() != t.size()) return false;
    unordered_map<char, int> freq;
    for (char c : s) freq[c]++;
    for (char c : t)
        if (--freq[c] < 0) return false;
    return true;
}

Rust — anagram check

fn is_anagram(s: &str, t: &str) -> bool {
    if s.len() != t.len() { return false; }
    let mut freq: HashMap<char, i32> = HashMap::new();
    for c in s.chars() { *freq.entry(c).or_insert(0) += 1; }
    for c in t.chars() {
        let entry = freq.entry(c).or_insert(0);
        *entry -= 1;
        if *entry < 0 { return false; }
    }
    true
}

📐 The count-then-decrement trick

Count all characters from string A, then decrement for each character in string B. If any count goes negative, B has a character A doesn't (or has too many of it). If counts stay ≥ 0, they match.

Key Takeaways

Practice