In this approach, we will first traverse the array to count the occurrences of each element using a hash map. Then, we will use a set to check if these occurrences are unique. If the size of the set matches the size of the occurrence counts, it implies all occurrences are unique.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(1), since we're using fixed-size arrays.
1def uniqueOccurrences(arr):
2 from collections import Counter
3 count = Counter(arr)
4 occurrences = set(count.values())
5 return len(occurrences) == len(count)
6
7arr = [1, 2, 2, 1, 1, 3]
8print(uniqueOccurrences(arr))The Python version uses a Counter from collections to count occurrences and then compares the size of the set of these counts to ensure uniqueness.
This alternative approach starts by counting occurrences just like the first one. After that, it stores these counts in a list, sorts the list, and then checks for any consecutive equal elements, which would indicate duplicate occurrences.
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(1), since we work within fixed-sized arrays.
1#include <stdio.h>
2#include <stdbool.h>
3#include <stdlib.h>
4
5int cmpfunc (const void * a, const void * b) {
6 return (*(int*)a - *(int*)b);
7}
8
9bool uniqueOccurrences(int* arr, int arrSize) {
10 int count[2001] = {0};
11 int occ[1001] = {0};
12 int idx = 0;
13
14 for(int i = 0; i < arrSize; i++) {
15 count[arr[i] + 1000]++;
16 }
17
18 for(int i = 0; i < 2001; i++) {
19 if(count[i] > 0) {
20 occ[idx++] = count[i];
21 }
22 }
23
24 qsort(occ, idx, sizeof(int), cmpfunc);
25
26 for(int i = 1; i < idx; i++) {
27 if(occ[i] == occ[i - 1])
28 return false;
29 }
30
31 return true;
32}
33
34int main() {
35 int arr[] = {1, 2, 2, 1, 1, 3};
36 int arrSize = sizeof(arr) / sizeof(arr[0]);
37 printf("%s\n", uniqueOccurrences(arr, arrSize) ? "true" : "false");
38 return 0;
39}In the C implementation using sorting, we use qsort to sort the frequency array and then check if any consecutive elements are equal.