Hashing for frequency problems

Counting with a hash map, and the array-of-26 trick that is faster than a map.

12 min read · Lesson 4 of 6 · Pro

The pattern

Any time a question contains the words count, frequency, duplicate, anagram, most common or seen before, the answer starts with a hash map. A nested loop that recounts the array for every element is O(n^2); one pass building a count map is O(n).

The trade is memory: you spend O(k) space, where k is the number of distinct values, to save a factor of n in time. Almost always worth it.

The three tools

C++

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

int main() {
    vector<int> a = {4, 2, 4, 7, 2, 4};

The rest of this lesson is Pro

The free lessons of DSA Interview Patterns finish what they start — read those first if you have not. This one goes further, and it is part of the paid half.

A pass opens the paid lessons of every course, the mock test papers and the company-wise series. It ends on its own date; nothing renews by itself.

Get a pass — from ₹29 for 7 days

Already bought one? Log in.