Code Implementation

class Solution:
    def uniqueOccurrences(self, arr):
        from collections import Counter
        freq = Counter(arr)
        occurrences = list(freq.values())
        return len(set(occurrences)) == len(occurrences)
      

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        unordered_map<int, int> freq;
        for (int num : arr) {
            freq[num]++;
        }
        unordered_set<int> occ;
        for (auto &p : freq) {
            if (!occ.insert(p.second).second) {
                return false;
            }
        }
        return true;
    }
};
      

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : arr) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        Set<Integer> occ = new HashSet<>();
        for (int count : freq.values()) {
            if (!occ.add(count)) {
                return false;
            }
        }
        return true;
    }
}
      

var uniqueOccurrences = function(arr) {
    const freq = {};
    for (const num of arr) {
        freq[num] = (freq[num] || 0) + 1;
    }
    const occurrences = Object.values(freq);
    return new Set(occurrences).size === occurrences.length;
};
      

Problem Description

Given an array of integers arr, determine if the number of times each value occurs is unique. In other words, return true if and only if no two distinct values in arr have the same number of occurrences.

• You must count how many times each number appears in arr.
• Check if all these counts are unique (no two numbers appear the same number of times).
• Return true if the counts are unique; otherwise, return false.
• Constraints typically guarantee arr has at least one element and all elements are integers.

Thought Process

The problem asks us to check if the frequencies of elements in an array are all different. A naive way would be to compare every frequency with every other one, but that would be inefficient. Instead, we can leverage data structures that help us count and check uniqueness efficiently.

• First, count how many times each number occurs. This can be done using a hash map or dictionary.
• Then, collect all these counts into a list or array.
• Finally, check if all these counts are unique. We can do this by converting the list of counts to a set and comparing the lengths: if the set is smaller, there was a duplicate count.

This approach is more efficient than brute-force comparison, as it avoids redundant checks and leverages fast lookups.

Solution Approach

Let's break down the solution step by step:

1. Count Occurrences:
   • Use a hash map (dictionary) to store each number as a key and its frequency as the value.
   • This allows us to count occurrences in a single pass through the array.
2. Check Uniqueness of Counts:
   • Extract all frequency values from the hash map.
   • Insert these counts into a set, which automatically removes duplicates.
   • If the size of the set equals the number of unique numbers (i.e., the size of the hash map), then all frequencies are unique.
   • If not, some counts were the same, so return false.
3. Return the Result:
   • Return true if all frequencies are unique, else false.

We use hash maps and sets because their typical operations (insert, lookup) are O(1) on average, making the solution efficient.

Example Walkthrough

Let's consider arr = [1,2,2,1,1,3].

1. Count Occurrences:
   • 1 appears 3 times
   • 2 appears 2 times
   • 3 appears 1 time
   • So, the frequency map is: {1: 3, 2: 2, 3: 1}
2. Collect and Check Uniqueness:
   • Frequencies: [3, 2, 1]
   • Convert to set: {1, 2, 3}
   • Set size is 3, same as the number of unique numbers (3)
   • All frequencies are unique, so return true

Now, consider arr = [1,2,2,1,1,3,3,3]:

• 1 appears 3 times
• 2 appears 2 times
• 3 appears 3 times
• Frequencies: [3, 2, 3] → set is {2, 3} (size 2, but 3 unique numbers)
• Not all frequencies are unique, so return false

Time and Space Complexity

• Brute-Force Approach:
  • Would compare each frequency with every other: O(n^2) time, where n is the number of unique elements.
• Optimized Approach (Hash Map + Set):
  • Counting frequencies: O(N), where N is the length of arr.
  • Building the set of frequencies: O(U), where U is the number of unique elements (U ≤ N).
  • Overall time: O(N).
  • Space: O(U) for the frequency map and O(U) for the set of counts.

The use of hash maps and sets makes the solution efficient even for large arrays.

Summary

The Unique Number of Occurrences problem can be efficiently solved by counting how often each number appears and then checking if all these counts are unique. By using hash maps for counting and sets for uniqueness checking, we avoid inefficient brute-force comparisons and ensure our solution runs in linear time. This approach is both concise and elegant, leveraging fundamental data structures for clarity and efficiency.