Frequency of Each Element in an Array
Filed under TCS · Also reported at Veritas
Free read 3 of 3Understand constraints on input size and whether order of output frequencies matters.
The question
Given an array of integers, find the frequency of each element. Discuss both a naive approach and an optimized hash map approach.
Constraints
- Array can contain duplicate elements and negative numbers.
- Input array length can vary from 0 to 10^5.
Examples
- Input
- arr = [1, 2, 2, 3, 1, 4]
- Output
- 1: 2, 2: 2, 3: 1, 4: 1
- Why
- Element 1 appears twice, 2 appears twice, 3 once, and 4 once.
Approach
Understand constraints on input size and whether order of output frequencies matters.
Iterate through each element and use a nested loop or visited array to count occurrences. Time complexity is O(N^2), space complexity is O(1).
Iterate through the array once, storing counts in a hash map (dictionary). Time complexity is O(N) and space complexity is O(N).
Handle empty arrays, arrays with all identical elements, and single-element arrays correctly.
Solution
O(N) time, O(N) space
def get_frequencies(arr):
freq = {}
for num in arr:
freq[num] = freq.get(num, 0) + 1
return freq
Tips
- What they are testing: Tests your ability to analyze time complexity trade-offs between sorting/nested loops and hash-based counting.
- Common mistake: Using nested loops without checking if an element has already been counted, leading to redundant counting and O(N^2) time.
Related TCS questions
Collected from public candidate posts and coding forums. Updated Nov 2026.