[AlgoMastery]
Topics›Array›Frequency Counting
📖

Frequency Counting

Array
~20 min read
5 practice problems

Overview

Frequency Counting is a technique that counts occurrences of elements in an array using hash maps (objects or Maps). It transforms O(n²) nested loop solutions into O(n) single-pass algorithms by trading space for time.

The key insight: use a hash map to store element frequencies, then query the map for counts. This enables efficient lookups and aggregations.

Frequency counting is particularly useful for:

  • Counting element occurrences
  • Finding duplicates
  • Grouping elements
  • Anagrams and permutations
  • Majority elements
  • Frequency-based queries

Pattern 1: Count Element Frequencies

Count occurrences of each element.

function countFrequencies(nums: number[]): Map<number, number> {
  const freq = new Map<number, number>();
  
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  return freq;
}

// Using object
function countFrequenciesObject(nums: number[]): Record<number, number> {
  const freq: Record<number, number> = {};
  
  for (const num of nums) {
    freq[num] = (freq[num] || 0) + 1;
  }
  
  return freq;
}

Time: O(n), Space: O(n)

Pattern 2: Find Duplicates

Find duplicate elements in array.

function findDuplicates(nums: number[]): number[] {
  const freq = new Map<number, number>();
  const duplicates: number[] = [];
  
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  for (const [num, count] of freq) {
    if (count > 1) {
      duplicates.push(num);
    }
  }
  
  return duplicates;
}

// Single pass version
function findDuplicatesSinglePass(nums: number[]): number[] {
  const seen = new Set<number>();
  const duplicates = new Set<number>();
  
  for (const num of nums) {
    if (seen.has(num)) {
      duplicates.add(num);
    } else {
      seen.add(num);
    }
  }
  
  return Array.from(duplicates);
}

Time: O(n), Space: O(n)

Pattern 3: Majority Element

Find element appearing more than n/2 times.

function majorityElement(nums: number[]): number {
  const freq = new Map<number, number>();
  const threshold = Math.floor(nums.length / 2);
  
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
    if (freq.get(num)! > threshold) {
      return num;
    }
  }
  
  return -1;
}

// Boyer-Moore algorithm (O(1) space)
function majorityElementBoyerMoore(nums: number[]): number {
  let candidate = nums[0];
  let count = 1;
  
  // Find candidate
  for (let i = 1; i < nums.length; i++) {
    if (count === 0) {
      candidate = nums[i];
      count = 1;
    } else if (nums[i] === candidate) {
      count++;
    } else {
      count--;
    }
  }
  
  // Verify candidate
  count = 0;
  for (const num of nums) {
    if (num === candidate) count++;
  }
  
  return count > nums.length / 2 ? candidate : -1;
}

Time: O(n), Space: O(n) or O(1)

Pattern 4: Top K Frequent Elements

Find K most frequent elements.

function topKFrequent(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  
  // Count frequencies
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  // Sort by frequency
  const sorted = Array.from(freq.entries()).sort((a, b) => b[1] - a[1]);
  
  return sorted.slice(0, k).map(([num]) => num);
}

// Using bucket sort (O(n) time)
function topKFrequentBucket(nums: number[], k: number): number[] {
  const freq = new Map<number, number>();
  
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  // Bucket by frequency
  const buckets: number[][] = Array(nums.length + 1).fill(null).map(() => []);
  
  for (const [num, count] of freq) {
    buckets[count].push(num);
  }
  
  const result: number[] = [];
  
  // Extract top K from buckets
  for (let i = buckets.length - 1; i >= 0 && result.length < k; i--) {
    result.push(...buckets[i]);
  }
  
  return result.slice(0, k);
}

Time: O(n log n) or O(n), Space: O(n)

Pattern 5: Group Anagrams

Group strings that are anagrams of each other.

function groupAnagrams(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  
  for (const str of strs) {
    const key = str.split('').sort().join('');
    
    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key)!.push(str);
  }
  
  return Array.from(groups.values());
}

// Using frequency count as key
function groupAnagramsFreq(strs: string[]): string[][] {
  const groups = new Map<string, string[]>();
  
  for (const str of strs) {
    const freq = new Array(26).fill(0);
    
    for (const char of str) {
      freq[char.charCodeAt(0) - 'a'.charCodeAt(0)]++;
    }
    
    const key = freq.join(',');
    
    if (!groups.has(key)) {
      groups.set(key, []);
    }
    groups.get(key)!.push(str);
  }
  
  return Array.from(groups.values());
}

Time: O(n k log k) or O(n k), Space: O(n * k)

Pattern 6: Find All Anagrams

Find all anagram substrings.

function findAnagrams(s: string, p: string): number[] {
  const result: number[] = [];
  const pFreq = new Map<string, number>();
  const windowFreq = new Map<string, number>();
  
  // Count frequency of pattern
  for (const char of p) {
    pFreq.set(char, (pFreq.get(char) || 0) + 1);
  }
  
  let left = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    windowFreq.set(char, (windowFreq.get(char) || 0) + 1);
    
    // Shrink window if size exceeds pattern length
    if (right - left + 1 > p.length) {
      const leftChar = s[left];
      windowFreq.set(leftChar, windowFreq.get(leftChar)! - 1);
      if (windowFreq.get(leftChar) === 0) {
        windowFreq.delete(leftChar);
      }
      left++;
    }
    
    // Check if window is anagram
    if (right - left + 1 === p.length && mapsEqual(windowFreq, pFreq)) {
      result.push(left);
    }
  }
  
  return result;
}

function mapsEqual(map1: Map<string, number>, map2: Map<string, number>): boolean {
  if (map1.size !== map2.size) return false;
  
  for (const [key, value] of map1) {
    if (map2.get(key) !== value) return false;
  }
  
  return true;
}

Time: O(n), Space: O(k) where k is pattern length

Pattern 7: Longest Substring with K Distinct Characters

Find longest substring with at most K distinct characters.

function longestSubstringKDistinct(s: string, k: number): number {
  const freq = new Map<string, number>();
  let left = 0;
  let maxLen = 0;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    freq.set(char, (freq.get(char) || 0) + 1);
    
    // Shrink window if distinct count exceeds K
    while (freq.size > k) {
      const leftChar = s[left];
      freq.set(leftChar, freq.get(leftChar)! - 1);
      if (freq.get(leftChar) === 0) {
        freq.delete(leftChar);
      }
      left++;
    }
    
    maxLen = Math.max(maxLen, right - left + 1);
  }
  
  return maxLen;
}

Time: O(n), Space: O(k)

Pattern 8: Frequency Sort

Sort array by frequency.

function frequencySort(nums: number[]): number[] {
  const freq = new Map<number, number>();
  
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  return [...nums].sort((a, b) => {
    const freqA = freq.get(a)!;
    const freqB = freq.get(b)!;
    
    if (freqA !== freqB) {
      return freqA - freqB; // Lower frequency first
    }
    return b - a; // Higher value first if same frequency
  });
}

// Using bucket sort
function frequencySortBucket(nums: number[]): number[] {
  const freq = new Map<number, number>();
  
  for (const num of nums) {
    freq.set(num, (freq.get(num) || 0) + 1);
  }
  
  const buckets: number[][] = Array(nums.length + 1).fill(null).map(() => []);
  
  for (const [num, count] of freq) {
    buckets[count].push(num);
  }
  
  const result: number[] = [];
  
  for (let i = 1; i < buckets.length; i++) {
    buckets[i].sort((a, b) => b - a); // Sort by value descending
    for (const num of buckets[i]) {
      for (let j = 0; j < i; j++) {
        result.push(num);
      }
    }
  }
  
  return result;
}

Time: O(n log n) or O(n), Space: O(n)

Pattern 9: Intersection of Two Arrays

Find intersection of two arrays.

function intersection(nums1: number[], nums2: number[]): number[] {
  const set1 = new Set(nums1);
  const result: number[] = [];
  
  for (const num of nums2) {
    if (set1.has(num)) {
      result.push(num);
      set1.delete(num); // Avoid duplicates
    }
  }
  
  return result;
}

// With duplicates (intersection II)
function intersect(nums1: number[], nums2: number[]): number[] {
  const freq1 = new Map<number, number>();
  
  for (const num of nums1) {
    freq1.set(num, (freq1.get(num) || 0) + 1);
  }
  
  const result: number[] = [];
  
  for (const num of nums2) {
    if (freq1.has(num) && freq1.get(num)! > 0) {
      result.push(num);
      freq1.set(num, freq1.get(num)! - 1);
    }
  }
  
  return result;
}

Time: O(n + m), Space: O(min(n, m))

Pattern 10: Subarray Sum Equals K

Count subarrays with sum K using frequency map.

function subarraySum(nums: number[], k: number): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, 1); // Empty subarray
  
  let sum = 0;
  let count = 0;
  
  for (const num of nums) {
    sum += num;
    
    if (prefixSum.has(sum - k)) {
      count += prefixSum.get(sum - k)!;
    }
    
    prefixSum.set(sum, (prefixSum.get(sum) || 0) + 1);
  }
  
  return count;
}

Time: O(n), Space: O(n)

Key insight: Track prefix sum frequencies. If current sum is S and we've seen S - k, subarray between has sum k.

Pattern 11: Contiguous Array

Find longest contiguous subarray with equal 0s and 1s.

function findMaxLength(nums: number[]): number {
  const prefixSum = new Map<number, number>();
  prefixSum.set(0, -1);
  
  let sum = 0;
  let maxLen = 0;
  
  for (let i = 0; i < nums.length; i++) {
    sum += nums[i] === 0 ? -1 : 1;
    
    if (prefixSum.has(sum)) {
      maxLen = Math.max(maxLen, i - prefixSum.get(sum)!);
    } else {
      prefixSum.set(sum, i);
    }
  }
  
  return maxLen;
}

Time: O(n), Space: O(n)

Explanation: Treat 0 as -1, 1 as +1. Equal 0s and 1s means sum = 0.

Pattern 12: Word Pattern

Check if string follows pattern.

function wordPattern(pattern: string, s: string): boolean {
  const words = s.split(' ');
  
  if (pattern.length !== words.length) return false;
  
  const charToWord = new Map<string, string>();
  const wordToChar = new Map<string, string>();
  
  for (let i = 0; i < pattern.length; i++) {
    const char = pattern[i];
    const word = words[i];
    
    if (charToWord.has(char)) {
      if (charToWord.get(char) !== word) return false;
    } else {
      charToWord.set(char, word);
    }
    
    if (wordToChar.has(word)) {
      if (wordToChar.get(word) !== char) return false;
    } else {
      wordToChar.set(word, char);
    }
  }
  
  return true;
}

Time: O(n), Space: O(n)

When to Use Frequency Counting

Use frequency counting when:

  • Need to count occurrences of elements
  • Problem involves duplicates or anagrams
  • Grouping elements by property
  • Sliding window with frequency constraints
  • Prefix sum problems
  • Lookup optimization (O(1) instead of O(n))

Key insight: Hash map provides O(1) lookup, transforming nested loops into single pass.

Template (Basic Frequency Count)

function frequencyCountTemplate<T>(arr: T[]): Map<T, number> {
  const freq = new Map<T, number>();
  
  for (const item of arr) {
    freq.set(item, (freq.get(item) || 0) + 1);
  }
  
  return freq;
}

Template (Frequency-Based Filtering)

function filterByFrequency<T>(arr: T[], condition: (count: number) => boolean): T[] {
  const freq = frequencyCountTemplate(arr);
  
  return arr.filter(item => condition(freq.get(item)!));
}

// Example: Keep elements appearing at least twice
const result = filterByFrequency([1, 2, 2, 3, 3, 3], count => count >= 2);

Time and Space Complexity Summary

  • Count frequencies: O(n) time, O(n) space
  • Find duplicates: O(n) time, O(n) space
  • Majority element: O(n) time, O(n) or O(1) space
  • Top K frequent: O(n log n) or O(n) time, O(n) space
  • Group anagrams: O(n k log k) or O(n k) time, O(n * k) space
  • Subarray sum: O(n) time, O(n) space

Practice Tips

  1. Choose data structure - Map vs object vs Set
  2. Single pass - Count and process in one iteration when possible
  3. Prefix sum - Combine with frequency counting for subarray problems
  4. Sliding window - Use frequency map for window constraints
  5. Bucket sort - For frequency-based sorting

Common Mistakes

  1. Not initializing - Forgetting to handle undefined values
  2. Wrong key - Using wrong key for grouping
  3. Memory overhead - Using Map when Set is sufficient
  4. Not cleaning up - Not removing zero frequencies
  5. Order matters - Not considering insertion order when needed

Related Concepts

  • Hash Map - Core data structure for frequency counting
  • Sliding Window - Often combined with frequency maps
  • Prefix Sum - Used together for subarray problems
  • Bucket Sort - For frequency-based sorting

Frequency counting is essential for efficient element analysis. Master this technique, and you'll solve many counting and grouping problems optimally in coding interviews.

← PreviousArray ManipulationNext →Monotonic Stack