Hashing and Frequency Counting

Frequency counting and hashing turn $O(n^2)$ pairwise search and grouping problems—such as finding anagrams, counting subarray sums, or identifying two-sum pairs—into $O(n)$ single-pass algorithms. In Rust, choosing between a fixed-size stack array ([u32; 26] / [u32; 256]) and a HashMap<K, usize> depends on the size of the key alphabet.

Choosing a Frequency Map in Rust:

  Small Bounded Alphabet (`'a'..='z'` or `u8` bytes `0..=255`):
    ---> Fixed Stack Array `[u32; 26]` or `[u32; 256]`
         (0 heap allocations, 0 hash computations, 1-cycle array index!)

  Large / Sparse Domain (`i64` coordinates, `&str` words, `[u32; 26]` signatures):
    ---> `HashMap<K, usize>` with `*map.entry(key).or_insert(0) += 1`

1. Fixed-Array Frequency Signatures for Anagrams and Character Counts

Because fixed-size arrays [u32; 26] implement Eq and Hash in Rust, you can use a 26-element letter frequency array directly as the key in a HashMap<[u32; 26], Vec<&str>>, grouping anagrams in $O(n \cdot L)$ time (without sorting each word in $O(L \log L)$ time!):

use std::collections::HashMap;

/// Computes the 26-letter frequency signature of a lowercase ASCII word in O(L) time.
#[inline]
pub fn letter_signature(word: &str) -> [u32; 26] {
    let mut counts = [0u32; 26];
    for &b in word.as_bytes() {
        if b.is_ascii_lowercase() {
            counts[(b - b'a') as usize] += 1;
        }
    }
    counts
}

/// Groups words that are anagrams of each other in O(N * L) time using `[u32; 26]` keys!
pub fn group_anagrams<'a>(words: &[&'a str]) -> Vec<Vec<&'a str>> {
    let mut groups: HashMap<[u32; 26], Vec<&'a str>> = HashMap::new();
    for &word in words {
        groups
            .entry(letter_signature(word))
            .or_default()
            .push(word);
    }

    let mut result: Vec<Vec<&'a str>> = groups.into_values().collect();
    result.sort_unstable_by_key(|g| g[0]);
    result
}

fn main() {
    let input = ["eat", "tea", "tan", "ate", "nat", "bat"];
    let grouped = group_anagrams(&input);

    assert_eq!(
        grouped,
        vec![vec!["bat"], vec!["eat", "tea", "ate"], vec!["tan", "nat"]]
    );
    println!("Grouped anagrams: {grouped:?}");
}

Grouped anagrams: [["bat"], ["eat", "tea", "ate"], ["tan", "nat"]]

2. Single-Pass Complementary Lookup (Two-Sum / Subarray Sum Equals $K$)

Instead of populating a HashMap in one pass and querying it in a second pass, many pair-matching and prefix-sum problems can query the map before inserting the current element in a single pass:

use std::collections::HashMap;

/// Finds indices `(i, j)` with `i < j` such that `nums[i] + nums[j] == target` in O(n) time.
pub fn two_sum(nums: &[i64], target: i64) -> Option<(usize, usize)> {
    let mut seen: HashMap<i64, usize> = HashMap::with_capacity(nums.len());
    for (i, &val) in nums.iter().enumerate() {
        let complement = target - val;
        if let Some(&prev_idx) = seen.get(&complement) {
            return Some((prev_idx, i));
        }
        seen.insert(val, i);
    }
    None
}

/// Counts contiguous subarrays whose elements sum to `target` in O(n) time.
pub fn subarray_sum_count(nums: &[i64], target: i64) -> u64 {
    let mut prefix_counts: HashMap<i64, u64> = HashMap::with_capacity(nums.len() + 1);
    prefix_counts.insert(0, 1); // Empty prefix has sum 0

    let mut running_sum = 0i64;
    let mut total_matches = 0u64;

    for &x in nums {
        running_sum += x;
        if let Some(&count) = prefix_counts.get(&(running_sum - target)) {
            total_matches += count;
        }
        *prefix_counts.entry(running_sum).or_insert(0) += 1;
    }

    total_matches
}

fn main() {
    assert_eq!(two_sum(&[2, 7, 11, 15], 9), Some((0, 1)));
    assert_eq!(subarray_sum_count(&[1, 2, 3, -3, 3], 3), 5);
    println!(
        "Two-sum indices: {:?}, subarrays summing to 3: {}",
        two_sum(&[2, 7, 11, 15], 9),
        subarray_sum_count(&[1, 2, 3, -3, 3], 3)
    );
}

Two-sum indices: Some((0, 1)), subarrays summing to 3: 5