Definition
- Frequency counting – iterate the array once and store each element as a key with its occurrence count as the value in a
HashMap. - merge method –
map.merge(key, 1, Integer::sum)inserts one if the key is absent, otherwise adds one to the existing count in a single call. - getOrDefault method –
map.put(key, map.getOrDefault(key, 0) + 1)reads the current count defaulting to zero, then writes back one more. - Time complexity – O(n) because each element is processed once and each
HashMapoperation is amortized O(1). - Space complexity – O(k) where k is the number of distinct elements, since each unique value gets one map entry.
Imagine the National Bank of India wants to know how many transactions each merchant received today. The teller goes through the day's slips one by one. For each slip, she finds the merchant's name in a tally sheet and adds one to the running count, or writes the name down with a count of one if it is new. At the end, the tally sheet shows exactly how many transactions every merchant received, built in a single pass through the slips.
Understanding the Concepts
What is frequency counting with a HashMap?
Frequency counting means building a map from each distinct element to the number of times it appears in the array. You iterate over the array once, and for each element you either start its count at one or add one to the existing count. The result is a HashMap where every key is a unique element and every value is that element's total occurrence count.
At the National Bank of India, Rajesh processes daily transaction records where each record carries a merchant category code. He needs to know how many transactions each category received so the fraud team can spot unusual spikes. A frequency map gives him that answer in a single pass.
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class FrequencyCounter {
public static Map<Integer, Integer> countFrequencies(int[] transactions) {
Map<Integer, Integer> frequency = new HashMap<>();
for (int code : transactions) {
frequency.merge(code, 1, Integer::sum);
}
return frequency;
}
public static void main(String[] args) {
int[] merchantCodes = {101, 202, 101, 303, 202, 101, 404, 303};
Map<Integer, Integer> freq = countFrequencies(merchantCodes);
System.out.println("Frequency map: " + freq);
}
}
Frequency map: {101=3, 202=2, 303=2, 404=1}
Why use a HashMap instead of nested loops?
The brute-force approach counts each element by rescanning the entire array, which takes O(n^2) time. With a HashMap each lookup and insert is amortized O(1), so processing every element once gives O(n) total time. For Rajesh's fraud dashboard at the National Bank of India, where millions of transactions arrive daily, the quadratic approach would never finish within the reporting window.
package com.bank.core;
public class BruteForceFrequency {
// Wrong approach: O(n^2) nested loop
public static void countBruteForce(int[] arr) {
boolean[] visited = new boolean[arr.length];
for (int i = 0; i < arr.length; i++) {
if (visited[i]) continue;
int count = 1;
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]) {
count++;
visited[j] = true;
}
}
System.out.println(arr[i] + " appears " + count + " times");
}
}
public static void main(String[] args) {
int[] codes = {101, 202, 101, 303, 202, 101};
countBruteForce(codes);
}
}
101 appears 3 times
202 appears 2 times
303 appears 1 times
The brute-force version works but is far too slow for production-scale data.
How does the merge method work internally?
The merge method on HashMap takes three arguments: the key, a default value, and a BiFunction that combines the existing value with the default when the key is already present. Calling map.merge(key, 1, Integer::sum) means: if the key is absent, insert it with value one; if the key is present, replace its value with oldValue + 1. This single line handles both the new-key and existing-key cases without an explicit if-else.
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class MergeDemo {
public static void main(String[] args) {
Map<String, Integer> ledger = new HashMap<>();
// First occurrence: key absent, inserts "HDFC" -> 1
ledger.merge("HDFC", 1, Integer::sum);
System.out.println("After first HDFC: " + ledger);
// Second occurrence: key present, updates to 1 + 1 = 2
ledger.merge("HDFC", 1, Integer::sum);
System.out.println("After second HDFC: " + ledger);
ledger.merge("ICICI", 1, Integer::sum);
System.out.println("After first ICICI: " + ledger);
}
}
After first HDFC: {HDFC=1}
After second HDFC: {HDFC=2}
After first ICICI: {HDFC=2, ICICI=1}
How is merge different from getOrDefault?
Both approaches build the same frequency map, but merge does the read-modify-write in a single atomic-like call, while getOrDefault requires a separate put. In concurrent contexts, merge on a ConcurrentHashMap is thread-safe for this operation, whereas the get-then-put pattern with a plain HashMap is not.
| Aspect | merge | getOrDefault + put |
|---|---|---|
| Lines of code | One call | Two calls (get then put) |
| Thread safety on ConcurrentHashMap | Atomic | Not atomic without synchronization |
| Readability | Slightly more abstract | More explicit |
| Performance | Same amortized O(1) | Same amortized O(1) |
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class GetOrDefaultDemo {
public static void main(String[] args) {
int[] merchantCodes = {101, 202, 101, 303, 202, 101};
// Approach 1: merge
Map<Integer, Integer> freqMerge = new HashMap<>();
for (int code : merchantCodes) {
freqMerge.merge(code, 1, Integer::sum);
}
// Approach 2: getOrDefault
Map<Integer, Integer> freqGet = new HashMap<>();
for (int code : merchantCodes) {
freqGet.put(code, freqGet.getOrDefault(code, 0) + 1);
}
System.out.println("merge result: " + freqMerge);
System.out.println("getOrDefault result: " + freqGet);
}
}
merge result: {101=3, 202=2, 303=1}
getOrDefault result: {101=3, 202=2, 303=1}
How do you find the most frequent element?
Once the frequency map is built, finding the most frequent element is a single scan of the entries comparing values. Rajesh uses this at the National Bank of India to find the busiest merchant category and flag it if it exceeds a threshold.
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class MostFrequent {
public static int findMostFrequent(int[] arr) {
Map<Integer, Integer> freq = new HashMap<>();
for (int val : arr) {
freq.merge(val, 1, Integer::sum);
}
int maxCount = 0;
int maxElement = arr[0];
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
if (entry.getValue() > maxCount) {
maxCount = entry.getValue();
maxElement = entry.getKey();
}
}
return maxElement;
}
public static void main(String[] args) {
int[] codes = {101, 202, 101, 303, 202, 101, 404, 303};
System.out.println("Most frequent: " + findMostFrequent(codes));
}
}
Most frequent: 101
What are common mistakes?
A common mistake is forgetting to handle the first occurrence of a key, which causes a NullPointerException when trying to increment a null value.
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class FrequencyMistake {
public static void main(String[] args) {
int[] codes = {101, 202, 101};
Map<Integer, Integer> freq = new HashMap<>();
// WRONG: NullPointerException on first occurrence
// freq.put(101, freq.get(101) + 1); // get(101) returns null
// CORRECT: use getOrDefault or merge
for (int code : codes) {
freq.put(code, freq.getOrDefault(code, 0) + 1);
}
System.out.println(freq);
}
}
{101=2, 202=1}
Another mistake is using containsKey followed by get, which traverses the hash bucket twice for the same key. The getOrDefault or merge approach is cleaner and avoids the redundant lookup.
What about using Java Streams?
Java Streams provide a functional approach to frequency counting using Collectors.groupingBy with Collectors.counting(). This is concise but creates intermediate objects and is generally slower than a plain loop for large arrays.
package com.bank.core;
import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;
public class StreamFrequency {
public static void main(String[] args) {
int[] merchantCodes = {101, 202, 101, 303, 202, 101};
Map<Integer, Long> freq = Arrays.stream(merchantCodes)
.boxed()
.collect(Collectors.groupingBy(
Function.identity(),
Collectors.counting()
));
System.out.println("Stream frequency: " + freq);
}
}
Stream frequency: {101=3, 202=2, 303=1}
What are the edge cases?
Edge cases include an empty array, an array with a single element, and an array where all elements are the same.
package com.bank.core;
import java.util.HashMap;
import java.util.Map;
public class FrequencyEdgeCases {
public static Map<Integer, Integer> countFrequencies(int[] arr) {
Map<Integer, Integer> freq = new HashMap<>();
for (int val : arr) {
freq.merge(val, 1, Integer::sum);
}
return freq;
}
public static void main(String[] args) {
// Edge case 1: empty array
System.out.println("Empty: " + countFrequencies(new int[]{}));
// Edge case 2: single element
System.out.println("Single: " + countFrequencies(new int[]{500}));
// Edge case 3: all same
System.out.println("All same: " + countFrequencies(new int[]{101, 101, 101}));
// Edge case 4: all distinct
System.out.println("All distinct: " + countFrequencies(new int[]{101, 202, 303}));
}
}
Empty: {}
Single: {500=1}
All same: {101=3}
All distinct: {101=1, 202=1, 303=1}
What problems build on the frequency map?
The frequency map is a foundational building block for many interview problems. Finding the first non-repeating element means scanning the map for the first entry with count one in insertion order using a LinkedHashMap. Detecting the majority element means checking if any count exceeds n/2. Grouping anagrams means building a frequency signature as the key. Checking whether two arrays are permutations means comparing their frequency maps for equality.
package com.bank.core;
import java.util.LinkedHashMap;
import java.util.Map;
public class FirstNonRepeating {
public static int findFirstNonRepeating(int[] arr) {
Map<Integer, Integer> freq = new LinkedHashMap<>();
for (int val : arr) {
freq.merge(val, 1, Integer::sum);
}
for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
if (entry.getValue() == 1) {
return entry.getKey();
}
}
return -1;
}
public static void main(String[] args) {
int[] codes = {101, 202, 101, 303, 202, 404};
System.out.println("First non-repeating: " + findFirstNonRepeating(codes));
}
}
First non-repeating: 303
What about thread safety and concurrency?
In a multi-threaded environment such as a real-time transaction processing system, a plain HashMap is not thread-safe. Using ConcurrentHashMap with merge provides atomic frequency updates without external synchronization.
package com.bank.core;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;
public class ConcurrentFrequency {
public static void main(String[] args) {
ConcurrentMap<Integer, Integer> freq = new ConcurrentHashMap<>();
// Simulating concurrent updates from multiple teller threads
int[] batch1 = {101, 202, 101};
int[] batch2 = {202, 303, 101};
// merge on ConcurrentHashMap is atomic
for (int code : batch1) {
freq.merge(code, 1, Integer::sum);
}
for (int code : batch2) {
freq.merge(code, 1, Integer::sum);
}
System.out.println("Concurrent frequency: " + freq);
}
}
Concurrent frequency: {101=3, 202=2, 303=1}
Visual Overview
Input Array: [101, 202, 101, 303, 202, 101, 404, 303]
│
▼
┌──────────────┐
│ HashMap │
│ Frequency │
│ Counter │
└──────┬───────┘
│
┌───────────┼───────────┐
│ │ │
▼ ▼ ▼
Step 1 Step 2 Step 3 ...
101 → 1 202 → 1 101 → 2
│ │ │
└───────────┼───────────┘
│
▼
┌──────────────┐
│ Final Map │
│ 101 → 3 │
│ 202 → 2 │
│ 303 → 2 │
│ 404 → 1 │
└──────────────┘
Key Takeaway
Counting the frequency of each element in an array is one of the most common operations in coding interviews and real-world systems. The approach is straightforward: iterate the array once and use a HashMap where each element is the key and its occurrence count is the value. Java provides two clean ways to handle the insert-or-update logic: the merge method, which handles both cases in a single call, and the getOrDefault method, which reads the current count defaulting to zero before writing back one more.
The time complexity is O(n) because each element is processed exactly once and each HashMap operation is amortized O(1). The space complexity is O(k) where k is the number of distinct elements. This is far better than the brute-force approach of counting each element by rescanning the entire array, which would take O(n^2) time.
In Rajesh's work at the National Bank of India, this technique powers the daily fraud analytics dashboard. Each transaction record carries a merchant category code, and in one pass he builds a frequency map of categories to spot unusual spikes. A sudden surge in one category can signal card-testing fraud, and the linear-time frequency map ensures the analysis completes well within the reporting window even for millions of transactions.
The frequency map is a foundational building block that shows up everywhere in interviews. Finding the first non-repeating element, detecting the majority element, grouping anagrams, and checking whether two arrays are permutations all start with exactly this HashMap tally. Knowing when to reach for merge versus getOrDefault, understanding thread safety with ConcurrentHashMap, and reasoning about the linear time complexity are what separate a production-ready answer from a textbook one.
Remember one sentence: iterate the array once and use HashMap merge or getOrDefault to count each element in O(n) time and O(k) space.
---