Count How Often Each Element Appears
Solve this ProblemEasy10 min
Topics
BasicsArraysHashing
Companies
TCSInfosysWipro
Given an array
nums, return an array of the same length where each position holds how many times that position's value appears in nums.
Frequency countingFrequency CountingRecording how many times each distinct value occurs, usually in a hash map from value to count. is one of the most useful techniques in programming. Rather than recounting a value every time it is needed, count everything once into a hash mapHash MapA structure that stores key → value pairs and can look up a key in O(1) time on average. and look the answers up afterwards — turning an O(n²) approach into O(n).
Test Case 1:
Input:nums = [5, 2, 5, 8, 5, 2]
Output:[3, 2, 3, 1, 3, 2]
Explanation:Every 5 is replaced by 3 (it appears three times), every 2 by 2, and 8 by 1.
Test Case 2:
Input:nums = [7]
Output:[1]
Explanation:A single value appears once.
Constraints
- ◆
1 ≤ nums.length ≤ 1000 - ◆
-1000000 ≤ nums[i] ≤ 1000000
Try the Dry Run
Approach & Solutions
Recount for Every ElementBrute
For each position i, scan the whole array again and count how many elements equal nums[i]. Simple, but the same value is recounted from scratch every time it appears — n scans of n elements.
Time
O(n²)Space
O(n) for the outputJava
class Solution {
public int[] frequencyOfEach(int[] nums) {
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
int count = 0;
for (int value : nums) {
if (value == nums[i]) {
count++;
}
}
result[i] = count;
}
return result;
}
}Count Once with a Map, Then Look UpOptimal
First pass: build a frequency map from each value to how many times it occurs. Second pass: for every position, look its value up in the map. Each value is counted exactly once. C uses an array indexed by value + 1,000,000 as the map.
Time
O(n)Space
O(n)Java
class Solution {
public int[] frequencyOfEach(int[] nums) {
Map<Integer, Integer> counts = new HashMap<>();
for (int value : nums) {
counts.merge(value, 1, Integer::sum);
}
int[] result = new int[nums.length];
for (int i = 0; i < nums.length; i++) {
result[i] = counts.get(nums[i]);
}
return result;
}
}