PROBLEM DESCRIPTION
You are given an integer array A. You have to find the number of occurences of each number. Return an array containing only the occurences with the smallest value’s occurence first.
SOLUTION
APPRAOCH 1 (HashMap)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;
public class Solution {
public int[] findOccurrences(int[] A) {
// Sort the array in ascending order
// We are doing this because the answer needs to be returned based on small number to larger number in arr A
Arrays.sort(A);
int n = A.length;
// Create a HashMap to store elements and their occurrences
Map<Integer, Integer> map = new HashMap<>();
// Count occurrences of each element in the array
for (int i = 0; i < n; i++) {
map.put(A[i], map.getOrDefault(A[i], 0) + 1);
}
// Create an array to store the occurrences
// The number of unique occurances will be equal to the size of hashmap
int[] res = new int[map.size()];
int idx = 0; // Index to fill the result array
for (int i = 0; i < n; i++) {
// Skip if the element is a duplicate by comparing it with the previous element
if (i > 0 && A[i] == A[i - 1]) continue;
// Store the count of occurrences for each unique element
res[idx++] = map.get(A[i]);
}
return res;
}
}
APPROACH 2 (TreeMap)
We can simplify our code a bit by making use of TreeMap which will sort the collection based on the Integer Key in our code.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public class Solution {
public int[] findOccurences(int[] A) {
Arrays.sort(A);
int n = A.length;
//replaced with TreeMap instead of HashMap
Map<Integer, Integer> map = new TreeMap<>();
for(int i=0; i<n; i++){
map.put(A[i], map.getOrDefault(A[i], 0) + 1);
}
int[] res = new int[map.size()];
int idx = 0;
//The values will be sorted based on Keys already
//So, we can directly iterated over the values and use them as answer
for(Integer x: map.values()){
res[idx++] = x;
}
return res;
}
}