Pattern: Hash Maps — Problem Statement & Solution Guide
Problem Description
Given an array of integers, determine the element that appears most frequently. If multiple elements share the same highest frequency, return the one with the smallest numerical value. The solution must efficiently count occurrences using a hash map to achieve linear time complexity.
Input: A single array of integers, nums.
Output: A single integer representing the most frequent element, with ties broken by selecting the minimum value among the candidates.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Pattern: Hash Maps"
WHY DOES IT MATTER?
Hash‑map frequency counting is a fundamental pattern for any problem that requires grouping or aggregating data by key, from analytics dashboards to real‑time monitoring. Mastery of this pattern enables engineers to turn quadratic‑time brute force solutions into linear‑time, production‑ready code.
OPTIMIZATION CHALLENGE
The key insight is to update the current most‑frequent element on‑the‑fly while populating the map, eliminating the need for a separate pass over the map entries and thus keeping the algorithm strictly O(n).
REAL-WORLD CONNECTION
Think of a distributed logging system where each log line contains a status code; a hash map acts like a local aggregator that tallies occurrences before shipping the summary to a central dashboard, mirroring how map‑reduce counts words in large text corpora.
During an interview, initialize your hash map and best‑candidate variables together; update the best candidate whenever you increment a count, checking both the new frequency and the tie‑breaker. This shows you can think incrementally and avoid unnecessary loops.
COMPLEXITY AT A GLANCE
O(n)O(n)Core Theory — Why This Approach?
The most frequent element problem is a classic frequency‑counting task that maps naturally to a hash map (or dictionary) where keys are the distinct numbers and values are their occurrence counts. A naive solution would scan the array for each unique value, leading to O(n²) time on large inputs because each element could be compared against every other element. By using a hash map we can update the count of each number in constant amortized time, achieving a single linear pass over the data. Once the map is populated, a second linear scan over its entries (or an inline update during the first pass) yields the element with the highest frequency, breaking ties by selecting the smallest numeric value. This two‑phase linear algorithm respects both time and space optimality for unsorted integer arrays.
The optimal paradigm leverages the principle of constant‑time look‑ups provided by hash tables, which is a cornerstone of many frequency‑based problems (e.g., mode, top‑k elements, anagrams). By maintaining the current best candidate while populating the map, we avoid a separate traversal, further tightening the runtime to O(n). The space usage is O(m), where m is the number of distinct integers, which in the worst case equals O(n) but is unavoidable because we must remember each unique count.
Why naive approaches fail: In the worst case (e.g., all elements distinct), a double loop incurs ~n²/2 comparisons, quickly exceeding time limits for n in the order of 10⁵ or more. The hash‑map approach sidesteps this by collapsing the counting work into a single pass, making it scalable for production‑grade data streams.
Interview Questions on This Problem
Q1How would you modify the solution if the input array is read as a stream and you cannot store all elements in memory?
Use a bounded-size hash map with a count‑min sketch or a reservoir sampling technique to approximate frequencies, or maintain a min‑heap of size k for the top‑k frequent elements while discarding low‑frequency entries.
Q2What changes are required if the tie‑breaking rule is to return the element that appears first in the array rather than the smallest value?
Track the first index at which each number appears alongside its count; when updating the best candidate, compare counts first, then use the stored index to break ties, ensuring O(1) updates per element.
Q3Explain how you could solve the problem in O(n log n) time without extra space beyond the input array.
Sort the array in‑place (O(n log n) time, O(1) extra space) and then scan linearly to count consecutive equal values, keeping the element with the longest run and applying the tie‑breaker as needed.
Examples
Input
nums = [4, 2, 4, 7, 2, 4, 9]
Output
4
Explanation: Count frequencies: 4 appears 3 times, 2 appears 2 times, 7 appears 1 time, 9 appears 1 time. The maximum frequency is 3, belonging to the element 4. Thus, return 4.
Input
nums = [10, 5, 10, 5, 3]
Output
5
Explanation: Count frequencies: 10 appears 2 times, 5 appears 2 times, 3 appears 1 time. Both 10 and 5 have the maximum frequency of 2. Since 5 < 10, return 5.
Input
nums = [1, 1, 1, 2, 2, 3, 3, 3, 3]
Output
3
Explanation: Count frequencies: 1 appears 3 times, 2 appears 2 times, 3 appears 4 times. The maximum frequency is 4, belonging to the element 3. Thus, return 3.
Input
nums = [-5, -5, 0, 0, 0, 7]
Output
0
Explanation: Count frequencies: -5 appears 2 times, 0 appears 3 times, 7 appears 1 time. The maximum frequency is 3, belonging to the element 0. Thus, return 0.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- The array will always contain at least one element.
Optimal Approach & Strategy
Use a hash map to record frequencies in a single pass, updating the best candidate on the fly; this runs in O(n) time with O(n) auxiliary space.
Brute Force Approach
For each element, scan the entire array to count how many times it appears, keeping track of the highest count and applying the tie‑breaker; this results in O(n²) time.
Verified Code Solutions
function mostFrequent(nums) {
const freq = new Map();
let maxCount = 0;
let answer = Infinity;
for (const x of nums) {
const cnt = (freq.get(x) || 0) + 1;
freq.set(x, cnt);
if (cnt > maxCount || (cnt === maxCount && x < answer)) {
maxCount = cnt;
answer = x;
}
}
return answer;
}
// Example usage:
const nums = [4, 2, 4, 7, 2, 4, 9];
console.log(mostFrequent(nums));#include <bits/stdc++.h>
using namespace std;
int mostFrequent(vector<int>& nums) {
unordered_map<int, int> freq;
int maxCount = 0;
int answer = INT_MAX;
for (int x : nums) {
int cnt = ++freq[x];
if (cnt > maxCount || (cnt == maxCount && x < answer)) {
maxCount = cnt;
answer = x;
}
}
return answer;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n; if(!(cin >> n)) return 0;
vector<int> nums(n);
for(int i=0;i<n;++i) cin >> nums[i];
cout << mostFrequent(nums) << "\n";
return 0;
}
import java.util.*;
public class Solution {
public int mostFrequent(int[] nums) {
Map<Integer, Integer> freq = new HashMap<>();
int maxCount = 0;
int answer = Integer.MAX_VALUE;
for (int x : nums) {
int cnt = freq.getOrDefault(x, 0) + 1;
freq.put(x, cnt);
if (cnt > maxCount || (cnt == maxCount && x < answer)) {
maxCount = cnt;
answer = x;
}
}
return answer;
}
public static void main(String[] args) {
int[] nums = {4, 2, 4, 7, 2, 4, 9};
Solution sol = new Solution();
System.out.println(sol.mostFrequent(nums));
}
}
def most_frequent(nums):
from collections import Counter
freq = Counter(nums)
max_count = max(freq.values())
candidates = [num for num, cnt in freq.items() if cnt == max_count]
return min(candidates)
# Example usage:
if __name__ == "__main__":
nums = [4, 2, 4, 7, 2, 4, 9]
print(most_frequent(nums))
function mostFrequent(nums) {
const freq = new Map();
let maxCount = 0;
let answer = Infinity;
for (const x of nums) {
const cnt = (freq.get(x) || 0) + 1;
freq.set(x, cnt);
if (cnt > maxCount || (cnt === maxCount && x < answer)) {
maxCount = cnt;
answer = x;
}
}
return answer;
}
// Example usage:
const nums = [4, 2, 4, 7, 2, 4, 9];
console.log(mostFrequent(nums));
Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.