Counting Frequencies of Array Elements
EasyOne pass to tally, one to report
Problem
Given an array, print how many times each distinct element appears.
Use a tally sheet (hash map): add one each time you see a value.
The idea
Increment a map entry per element, then iterate the map to print each distinct value with its count. Two linear passes, and the map's size tells you how many distinct values there were as a free by-product.
The trick
- O(n) time and O(distinct) space.
- Iteration order of a hash map is unspecified — sort the keys if the output order matters.
1
2
2
3
3
3
0
1
2
3
4
5
Step 1 of 5. Brute force: count each number and keep the one that appears most. Values: 1, 2, 2, 3, 3, 3.
1/5
Brute force
timeO(n²)spaceO(1)
Count each number.
1for (let i = 0; i < n; i++) {2 let count = 0;3 for (let j = 0; j < n; j++) if (nums[j] === nums[i]) count++;4 // record count for nums[i]5}Input
- array
- [1, 2, 2, 3, 3, 3]
Output
- count
- —
- best
- —
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 2, 3, 3, 3]
- Output:
- {1:1, 2:2, 3:3}
- Explanation:
- 1 once, 2 twice, 3 three times.
Example 2
- Input:
- nums = [5, 5, 5]
- Output:
- {5:3}
- Explanation:
- 5 shows up three times.
Example 3
- Input:
- nums = [1, 2, 3]
- Output:
- {1:1, 2:1, 3:1}
- Explanation:
- Each value appears exactly once.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.