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.
1#include <iostream>
2#include <vector>
3#include <unordered_map>
4#include <unordered_set>
5
6bool uniqueOccurrences(std::vector<int>& arr) {
7 std::unordered_map<int, int> countMap;
8 for (int num : arr) {
9 ++countMap[num];
10 }
11 std::unordered_set<int> occurrences;
12 for (const auto& pair : countMap) {
13 if (!occurrences.insert(pair.second).second) {
14 return false;
15 }
16 }
17 return true;
18}
19
20int main() {
21 std::vector<int> arr = {1, 2, 2, 1, 1, 3};
22 std::cout << (uniqueOccurrences(arr) ? "true" : "false") << std::endl;
23 return 0;
24}In the C++ version, we use an unordered map to count occurrences of each number, followed by a set to check if any occurrence count is duplicated.
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.
1import java.util.*;
2
3public class UniqueOccurrences {
4 public static boolean uniqueOccurrences(int[] arr) {
5 HashMap<Integer, Integer> countMap = new HashMap<>();
6 for (int num : arr) {
7 countMap.put(num, countMap.getOrDefault(num, 0) + 1);
8 }
9 List<Integer> occurrences = new ArrayList<>(countMap.values());
10 Collections.sort(occurrences);
11 for (int i = 1; i < occurrences.size(); i++) {
12 if (occurrences.get(i).equals(occurrences.get(i - 1))) {
13 return false;
14 }
15 }
16 return true;
17 }
18
19 public static void main(String[] args) {
20 int[] arr = {1, 2, 2, 1, 1, 3};
21 System.out.println(uniqueOccurrences(arr));
22 }
23}In the Java version, we convert the map's values to a list, sort it, and then check for duplicates in consecutive elements.