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.
1using System;
2using System.Collections.Generic;
3using System.Linq;
4
5public class Program {
6 public static bool UniqueOccurrences(int[] arr) {
7 Dictionary<int, int> countMap = new Dictionary<int, int>();
8 foreach (int num in arr) {
9 if (countMap.ContainsKey(num)) countMap[num]++;
10 else countMap[num] = 1;
11 }
12 List<int> occurrences = countMap.Values.ToList();
13 occurrences.Sort();
14 for (int i = 1; i < occurrences.Count; i++) {
15 if (occurrences[i] == occurrences[i - 1]) return false;
16 }
17 return true;
18 }
19
20 public static void Main() {
21 int[] arr = {1, 2, 2, 1, 1, 3};
22 Console.WriteLine(UniqueOccurrences(arr));
23 }
24}In C#, we use Linq to turn the map of occurrences into a list, sort it, and check if there are any duplicates in sorted order.