Distinct Element Occurrences — Problem Statement & Solution Guide
Problem Description
You are provided with a sequence of integers representing a dataset. Your task is to analyze this sequence and determine the frequency of each unique value present. Construct a mapping where each key is a distinct integer from the input, and the corresponding value is the total number of times that integer appears in the sequence.
The input will be a single list of integers. The output must be a dictionary (or map) object. The keys in the resulting dictionary must be the unique integers found in the input list, and the values must be positive integers representing their respective counts. The order of keys in the dictionary does not matter, as dictionary lookups are typically unordered or order-agnostic in most programming contexts for this type of problem.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Distinct Element Occurrences"
WHY DOES IT MATTER?
Frequency maps are foundational for summarizing data and enabling downstream analytics.
OPTIMIZATION CHALLENGE
Replacing nested loops with a hash table drops complexity from quadratic to linear.
REAL-WORLD CONNECTION
Log aggregation systems count occurrences of error codes to trigger alerts.
Pre‑allocate the hash table size when the range of values is known to avoid rehashing overhead.
COMPLEXITY AT A GLANCE
O(n)O(k)Core Theory — Why This Approach?
Counting the frequency of each distinct element is a classic aggregation problem that can be solved by scanning the input once and maintaining a map from value to its count. A naïve double‑loop that compares each element with every other runs in O(n²) time and quickly becomes infeasible for large datasets because the number of comparisons grows quadratically.
The optimal paradigm leverages a hash table (or unordered_map) to achieve O(1) average‑time updates per element, resulting in an overall O(n) time algorithm with O(k) auxiliary space, where k is the number of unique values. Alternative approaches like sorting first give O(n log n) time but still require extra passes and cannot beat the linear‑time hash‑based solution for pure counting.
Interview Questions on This Problem
Q1How would you count element frequencies if the input size exceeds available memory?
Use an external sort or a streaming algorithm that writes partial counts to disk and merges them later. This reduces in‑memory footprint while preserving O(n log n) overall time.
Q2What are the trade‑offs between using a hash map versus sorting the array first?
Hash maps give linear time but use extra space proportional to distinct elements; sorting uses no extra map space but incurs O(n log n) time. Choose based on memory constraints and whether order matters.
Q3Can you modify the counting algorithm to return the most frequent element efficiently?
Maintain a running maximum while updating counts in the hash map, so the most frequent value is known after a single pass. This adds only O(1) extra work per element.
Examples
Input
nums = [4, 2, 4, 7, 2, 4]
Output
{4: 3, 2: 2, 7: 1}Explanation: The integer 4 appears at indices 0, 2, and 5, resulting in a count of 3. The integer 2 appears at indices 1 and 4, resulting in a count of 2. The integer 7 appears only at index 3, resulting in a count of 1. The final map contains these three key-value pairs.
Input
nums = [10, 10, 10, 10]
Output
{10: 4}Explanation: The input array contains only the integer 10. It appears four times consecutively. Therefore, the resulting dictionary has a single key, 10, with a value of 4.
Input
nums = [1, 2, 3, 4, 5]
Output
{1: 1, 2: 1, 3: 1, 4: 1, 5: 1}Explanation: Each integer in the input array is unique. No element repeats. Consequently, every distinct element has a frequency of 1. The output dictionary maps each of the five integers to the value 1.
Input
nums = [-5, 0, -5, 0, 3, -5]
Output
{-5: 3, 0: 2, 3: 1}Explanation: The integer -5 appears at indices 0, 2, and 5, giving a count of 3. The integer 0 appears at indices 1 and 3, giving a count of 2. The integer 3 appears once at index 4. The negative values are treated as distinct keys just like positive integers.
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
- The input array will not be empty.
- The output dictionary must contain exactly as many keys as there are distinct elements in the input.
Optimal Approach & Strategy
Use a hash map to increment the count for each element during a single pass, achieving O(n) time.
Brute Force Approach
For each element, scan the entire array to count its occurrences, leading to O(n²) time.
Verified Code Solutions
function solution(nums) { let countMap = {}; for (let num of nums) { if (countMap[num]) { countMap[num]++; } else { countMap[num] = 1; } } return countMap; }class Solution { public: std::unordered_map<int, int> solution(std::vector<int>& nums) { std::unordered_map<int, int> countMap; for (int num : nums) { countMap[num]++; } return countMap; } };import java.util.HashMap; import java.util.Map; class Solution { public Map<Integer, Integer> solution(int[] nums) { Map<Integer, Integer> countMap = new HashMap<>(); for (int num : nums) { countMap.put(num, countMap.getOrDefault(num, 0) + 1); } return countMap; } }def solution(nums): count_map = {}; for num in nums: if num in count_map: count_map[num] += 1; else: count_map[num] = 1; return count_mapfunction solution(nums) { let countMap = {}; for (let num of nums) { if (countMap[num]) { countMap[num]++; } else { countMap[num] = 1; } } return countMap; }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.