Hashing is the backbone of fast lookups and frequency-based problem solving.
Its core idea:
“Store what you’ve seen so you never recompute it again” — turning many O(n²) scans into O(n).
Focus on recognizing:
Searching, counting, or duplicate-checking → Hashing
Core Template
Map<KeyType, ValueType> map = new HashMap<>();
for (Element e : input) {
if (map.containsKey(e)) {
// use stored info
}
map.put(e, updatedValue);
}seen = {}
for e in input:
if e in seen:
... # use stored info
seen[e] = updated_valueunordered_map<KeyType, ValueType> map;
for (auto& e : input) {
if (map.count(e)) {
// use stored info
}
map[e] = updatedValue;
}const map = new Map();
for (const e of input) {
if (map.has(e)) {
// use stored info
}
map.set(e, updatedValue);
}Key = pattern, Value = memory of the past. Set = existence · Map = frequency/relationship.
Pattern 1: Frequency Counting
Watch [1,2,2,3,1] collapse into a frequency table in one pass — each lookup replaces a full re-scan. Press ▶ to animate.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Hashing — Frequency Map
Count the frequency of every value by scanning nums = [1, 2, 2, 3, 1] once and storing each value as a key in a hash map: {1:2, 2:2, 3:1}.
We scan nums = [1, 2, 2, 3, 1] from left to right and maintain a frequency map. For each number x, we check whether x already exists in the map. If it is new, we create its key with count 0. Then we increase its count by 1. The first 1 creates key 1 and changes its count to 1. The first 2 creates key 2 and changes its count to 1. The second 2 is already in the map, so its count increases from 1 to 2. The 3 is new, so we create it and give it count 1. Finally, the last 1 already exists, so its count increases from 1 to 2. The final map is {1:2, 2:2, 3:1}. Therefore, 1 appears twice, 2 appears twice, and 3 appears once. We scan the array once, giving O(n) average time and O(u) space, where u is the number of unique values.
1
freq = {}
2
for x in nums:
3
if x not in freq:
4
freq[x] = 0
5
freq[x] += 1
public Map<Integer, Integer> frequency(int[] arr) {
Map<Integer, Integer> freq = new HashMap<>();
for (int num : arr) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
return freq;
}from collections import Counter
def frequency(arr):
return Counter(arr)unordered_map<int, int> frequency(vector<int>& arr) {
unordered_map<int, int> freq;
for (int num : arr) freq[num]++;
return freq;
}function frequency(arr) {
const freq = new Map();
for (const num of arr) {
freq.set(num, (freq.get(num) ?? 0) + 1);
}
return freq;
}Hash map = frequency memory table. O(n²) counting becomes one pass.
Pattern 2: Two Sum (Complement Lookup)
Each value asks the map: have I already met my complement?
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Two Sum (Hash Map)
Given nums = [2, 7, 11, 15] and target = 9, find two different indices i and j such that nums[i] + nums[j] = 9. Return the pair of indices. For this input, the answer is [0, 1] because nums[0] = 2 and nums[1] = 7, and 2 + 7 = 9.
We scan nums = [2, 7, 11, 15] from left to right while using a hash map called seen to remember values we have already visited and their indices. For each value x, calculate the number we need: need = target - x. At index 0, x = 2, so we need 9 - 2 = 7. The map is empty, so 7 has not been seen; store 2 at index 0. At index 1, x = 7, so we need 9 - 7 = 2. The map already contains 2 at index 0, so indices 0 and 1 form the answer. We check for the complement before storing the current value, which also prevents using the same array element twice. The array is scanned only until the answer is found, giving O(n) average time and O(n) extra space in the general case.
1
seen = {}
2
for i in 0..n-1:
3
need = target - nums[i]
4
if need in seen:
5
return [seen[need], i]
6
seen[nums[i]] = i
Store value → index as you scan; each element asks “have I seen my complement?”:
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[]{map.get(complement), i};
}
map.put(nums[i], i);
}
return new int[]{-1, -1};
}def two_sum(nums, target):
seen = {}
for i, num in enumerate(nums):
if target - num in seen:
return [seen[target - num], i]
seen[num] = i
return [-1, -1]vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> seen;
for (int i = 0; i < (int)nums.size(); i++) {
auto it = seen.find(target - nums[i]);
if (it != seen.end())
return {it->second, i};
seen[nums[i]] = i;
}
return {-1, -1};
}function twoSum(nums, target) {
const seen = new Map();
for (let i = 0; i < nums.length; i++) {
if (seen.has(target - nums[i]))
return [seen.get(target - nums[i]), i];
seen.set(nums[i], i);
}
return [-1, -1];
}Hashing turns search into lookup — check before you insert.
Pattern 3: Grouping (Anagrams)
Sorted letters become a bucket key — anagrams collide into the same list.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Group Anagrams
Given words = ["eat", "tea", "tan", "ate", "nat", "bat"], group the words that are anagrams of each other. Words are anagrams when they contain the same letters with the same frequencies, even if their order is different. The expected groups are [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]].
The key idea is to give every anagram the same key. For each word, sort its letters alphabetically. For example, "eat" becomes "aet", "tea" also becomes "aet", and "ate" also becomes "aet". Because all three words produce the same key, the hash map puts them into the same group. Similarly, "tan" and "nat" both become "ant", so they share another group. "bat" becomes "abt", which is different, so it forms its own group. The animation follows every word in words = ["eat", "tea", "tan", "ate", "nat", "bat"] and shows the transformation from word to sorted key and then into its hash-map group. With sorting, the time complexity is O(N · k log k), where N is the number of words and k is the average word length. The extra space is O(N · k) for storing the groups and keys.
1
groups = {}
2
for word in words:
3
key = ''.join(sorted(word))
4
if key not in groups:
5
groups[key] = []
6
groups[key].append(word)
7
return groups
Transform each string into a canonical key, then bucket:
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<>();
for (String s : strs) {
char[] arr = s.toCharArray();
Arrays.sort(arr);
String key = new String(arr);
map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(map.values());
}from collections import defaultdict
def group_anagrams(strs):
groups = defaultdict(list)
for s in strs:
groups["".join(sorted(s))].append(s)
return list(groups.values())vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> groups;
for (string s : strs) {
sort(s.begin(), s.end());
groups[s].push_back(s);
}
vector<vector<string>> result;
for (auto& [_, g] : groups) result.push_back(g);
return result;
}function groupAnagrams(strs) {
const groups = new Map();
for (const s of strs) {
const key = [...s].sort().join("");
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(s);
}
return [...groups.values()];
}Grouping = classification via computed keys — sorted form, count signature, remainder class…
Related Patterns
- Subarray sum equals K → prefix sums in a hashmap — covered in Prefix Sum.
- Longest substring without repeats → set-backed window — covered in Strings: Sliding Window.
Common Mistakes
Forgetting the seed entry.
map[0] = 1 before scanning makes prefix-based counting work — without it, subarrays starting at index 0 vanish.
Sorting when a hash would do.
Sorting is O(n log n); hashing is O(n). Sort only when order itself is needed.
Set vs Map confusion.
Existence questions → Set. Frequency or relationship questions → Map.
Complexity
| Operation | Average |
|---|---|
| insert | O(1) |
| lookup | O(1) |
| Full pass | O(n) |
Premium Content
Unlock Array Hashing and all premium lessons with a subscription.
From ₹199.99/year — See plans