Practice › Hashing & Two Pointers
Frequency of Elements
Easy · Hashing & Two Pointers · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Print every distinct value of the array together with how many times it appears, sorted by value.
Input
First line: n. Second line: n integers.
Output
One line per distinct value: value count, in increasing order of value.
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i] ≤ 10^9
Example 1
Input
6 10 5 10 15 10 5
Output
5 2 10 3 15 1
Example 2
Input
1 7
Output
7 1
Hints
- Count each value with a map from value to count.
- The output must be sorted by value — use an ordered map (std::map / TreeMap) or sort the keys.
Approach
Insert every element into a map from value to count. A sorted map (std::map, TreeMap) gives the keys in increasing order. With a hash map, sort the keys before printing. Sorting the array and counting runs of equal values is another O(n log n) option.
Complexity: O(n log n) time · O(distinct values) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
map<long long, int> freq;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
freq[x]++;
}
for (auto &p : freq) cout << p.first << " " << p.second << "\n";
return 0;
}Python solution
import sys
from collections import Counter
data = list(map(int, sys.stdin.read().split()))
freq = Counter(data[1 : data[0] + 1])
print("\n".join(f"{v} {freq[v]}" for v in sorted(freq)))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
TreeMap<Long, Integer> freq = new TreeMap<>();
for (int i = 0; i < n; i++) freq.merge(sc.nextLong(), 1, Integer::sum);
StringBuilder sb = new StringBuilder();
for (Map.Entry<Long, Integer> e : freq.entrySet()) sb.append(e.getKey()).append(' ').append(e.getValue()).append('\n');
System.out.print(sb);
}
}