# Unique Number of Occurrences
**Difficulty:** EASY
[External](https://leetcode.com/problems/unique-number-of-occurrences)
Canonical: https://scaleengineer.com/dsa/problems/unique-number-of-occurrences
**Data structures:** Array, Hash Table
**Companies:** [Datadog](https://scaleengineer.com/companies/datadog)
---
## Problem
Given an array of integers `arr`, return `true` _if the number of occurrences of each value in the array is **unique** or_ `false` _otherwise_.

**Example 1:**

**Input:** arr = [1,2,2,1,1,3]
**Output:** true
**Explanation:** The value 1 has 3 occurrences, 2 has 2 and 3 has 1. No two values have the same number of occurrences.

**Example 2:**

**Input:** arr = [1,2]
**Output:** false

**Example 3:**

**Input:** arr = [-3,0,1,-3,1,1,1,-3,10,0]
**Output:** true

**Constraints:**

* `1 <= arr.length <= 1000`
* `-1000 <= arr[i] <= 1000`

# Approaches
## Sorting-Based Approach
This approach relies on sorting to solve the problem. First, the input array is sorted, which conveniently groups all identical numbers next to each other. Then, a single pass through the sorted array is enough to count the occurrences of each unique number. These counts are stored in a separate list. To check if the counts themselves are unique, this list of counts is also sorted. A final pass over the sorted counts list can easily reveal any duplicates by checking adjacent elements. If any duplicates are found, the function returns false; otherwise, it returns true.
**Time:** O(N log N), where N is the number of elements in the array. The initial sort of the array dominates the time complexity. Counting frequencies takes O(N), and sorting the frequencies takes O(K log K), where K <= N. · **Space:** O(K), where K is the number of unique elements in `arr`. In the worst case (all elements are unique), the space complexity is O(N) to store the counts. Sorting algorithms might also use O(log N) to O(N) auxiliary space depending on the implementation.
**Pros:** The logic is straightforward and relies on the fundamental concept of sorting.; It does not require complex data structures like hash maps.
**Cons:** The time complexity of O(N log N) is suboptimal compared to other approaches.; It requires modifying the input array by sorting it, or using extra space to store a sorted copy.; It involves multiple traversals and sorting operations, making it more complex to implement correctly.
### Explanation
The core idea is to transform the problem of checking unique occurrences into a simpler problem of checking for duplicates in a sorted list. By sorting the initial array, we can easily compute the frequencies. By sorting the list of frequencies, we can easily check for uniqueness.

**Algorithm Steps:**
1.  Sort the input array `arr`.
2.  Initialize an `ArrayList<Integer>` named `counts`.
3.  Iterate through the sorted `arr` using an index `i`.
4.  Inside the loop, count the occurrences of the current element `arr[i]` by checking the subsequent elements.
5.  Add the final count to the `counts` list.
6.  Advance the index `i` past the block of identical elements.
7.  After the loop, sort the `counts` list.
8.  Iterate through the sorted `counts` list from the first element to the second-to-last element.
9.  In each iteration, compare `counts.get(j)` with `counts.get(j + 1)`. If they are equal, return `false`.
10. If the loop completes, it means no two frequencies were the same, so return `true`.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        Arrays.sort(arr);
        List<Integer> counts = new ArrayList<>();
        int i = 0;
        while (i < arr.length) {
            int count = 1;
            while (i + 1 < arr.length && arr[i] == arr[i + 1]) {
                count++;
                i++;
            }
            counts.add(count);
            i++;
        }

        Collections.sort(counts);
        for (int j = 0; j < counts.size() - 1; j++) {
            if (counts.get(j).equals(counts.get(j + 1))) {
                return false;
            }
        }
        return true;
    }
}
```
### Algorithm
- Sort the input array `arr` to group identical elements together.
- Initialize an empty list, `counts`, to store the frequency of each unique number.
- Iterate through the sorted array. For each unique number, count its occurrences and add the count to the `counts` list.
- After populating the `counts` list, sort it as well.
- Iterate through the sorted `counts` list. If any two adjacent elements are identical, it means a frequency is not unique, so return `false`.
- If the entire `counts` list is traversed without finding duplicates, return `true`.

## Using Hash Map and Hash Set
A more efficient and standard approach for frequency-related problems is to use a hash map. This method involves two main steps. First, iterate through the input array and use a hash map to count the occurrences of each number. The number itself is the key, and its frequency is the value. Second, after all frequencies are counted, check if these frequencies are unique. This can be done efficiently by inserting all the frequency counts into a hash set and comparing the size of the hash set with the original number of unique elements (the size of the hash map).
**Time:** O(N), where N is the number of elements in the array. Populating the hash map requires a single pass through the array. Creating the hash set from the map's values takes O(K) time, where K is the number of unique elements (K <= N). · **Space:** O(K), where K is the number of unique elements in the array. The hash map will store K key-value pairs, and the hash set will store at most K frequencies. In the worst case, K=N.
**Pros:** Optimal time complexity of O(N).; It is a general-purpose solution that works regardless of the range of numbers in the input array.; The code is often more concise and readable.
**Cons:** Requires extra space for both the hash map and the hash set.; Hashing can have a higher constant factor overhead compared to direct array indexing.
### Explanation
This approach decouples the counting from the uniqueness check, leading to a more efficient linear time solution.

**Algorithm Steps:**
1.  Initialize a `HashMap<Integer, Integer>` called `freqMap`.
2.  Iterate through each number `num` in the input array `arr`.
3.  For each `num`, update its frequency in `freqMap`. You can use `freqMap.put(num, freqMap.getOrDefault(num, 0) + 1)`.
4.  After the loop, `freqMap` contains all unique numbers and their corresponding frequencies.
5.  To check if the frequencies are unique, we can get the collection of values from the map.
6.  Create a `HashSet<Integer>` using the values from `freqMap`. A set only stores unique elements, so any duplicate frequencies will be discarded.
7.  Compare the size of the `freqMap` (which is the number of unique elements) with the size of the `freqSet` (which is the number of unique frequencies).
8.  If the sizes are equal, it means each unique element had a unique frequency. Return `true`.
9.  Otherwise, return `false`.

```java
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        // Step 1: Count frequencies of each number
        Map<Integer, Integer> freqMap = new HashMap<>();
        for (int num : arr) {
            freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
        }

        // Step 2: Check if the frequencies are unique
        // We can do this by adding all frequencies to a set
        // and comparing the size of the set with the size of the map.
        Set<Integer> freqSet = new HashSet<>(freqMap.values());

        return freqMap.size() == freqSet.size();
    }
}
```
### Algorithm
- Create a `HashMap<Integer, Integer>` to store the frequency of each number.
- Iterate through the input array `arr` and populate the hash map. For each number, increment its corresponding count.
- After counting, the goal is to check if the frequencies (the values in the map) are unique.
- Create a `HashSet<Integer>` from the values of the hash map.
- The number of unique frequencies is the size of the hash set. The number of distinct elements is the size of the hash map.
- If these two sizes are equal, it means every element had a unique number of occurrences. Return `true`, otherwise return `false`.

## Using Two Arrays (Optimized for Constraints)
This approach is a highly optimized solution that takes advantage of the problem's constraints on the range of values in the input array. Instead of using a hash map, which involves computational overhead for hashing, we can use a simple array as a direct-access table (or frequency map). A second array is then used to check for the uniqueness of the frequencies found. This method avoids hashing and can be faster due to better cache performance and direct memory access.
**Time:** O(N + M), where N is the length of the input array and M is the range of possible values (2001). We iterate through the input array once (O(N)) and the frequency array once (O(M)). Given the constraints, this is a very fast linear time solution. · **Space:** O(M + L), where M is the range of values (2001) and L is the maximum possible length of `arr` (1001). Since these are fixed by the problem constraints, the space complexity is effectively O(1).
**Pros:** Extremely fast due to the use of arrays and direct indexing, avoiding hashing overhead.; The time complexity is linear, O(N + M), and the space complexity is constant with respect to the input size N, as it only depends on the problem's fixed constraints.
**Cons:** This solution is not general; it relies heavily on the specific constraints of the problem (`-1000 <= arr[i] <= 1000`).; It may use a large amount of memory if the range of possible values is large, even if the input array itself is small.
### Explanation
By using arrays as direct-access tables, we can achieve a very fast, constant-time lookup for both counting frequencies and checking for their uniqueness.

**Algorithm Steps:**
1.  Define an offset, `OFFSET = 1000`, to handle negative numbers.
2.  Create an integer array `freqCounts` of size `2 * OFFSET + 1` (i.e., 2001), initialized to all zeros.
3.  Iterate through each number `num` in the input `arr`. For each `num`, increment the count at the mapped index: `freqCounts[num + OFFSET]++`.
4.  Create a boolean array `seenFreqs` of size `arr.length + 1` (or 1001, based on constraints), initialized to all `false`. This array will track if a frequency has been encountered before.
5.  Iterate through the `freqCounts` array.
6.  For each `count` in `freqCounts`:
7.  If the `count` is 0, continue to the next one.
8.  If `seenFreqs[count]` is `true`, it means we have already seen another number with the same frequency. Return `false`.
9.  If `seenFreqs[count]` is `false`, set it to `true` to mark this frequency as seen.
10. If the loop finishes without finding any duplicate frequencies, return `true`.

```java
class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        // Constraint: -1000 <= arr[i] <= 1000
        // We can use an array as a frequency map.
        // Map values from -1000..1000 to indices 0..2000
        int[] freqCounts = new int[2001];
        int offset = 1000;
        for (int num : arr) {
            freqCounts[num + offset]++;
        }

        // Constraint: 1 <= arr.length <= 1000
        // The maximum frequency can be 1000.
        // Use a boolean array to check for uniqueness of frequencies.
        boolean[] seenFreqs = new boolean[1001];
        for (int count : freqCounts) {
            if (count > 0) {
                if (seenFreqs[count]) {
                    // This frequency has been seen before.
                    return false;
                }
                seenFreqs[count] = true;
            }
        }

        return true;
    }
}
```
### Algorithm
- Given the constraint that numbers are in `[-1000, 1000]`, create an integer array `freqCounts` of size 2001 to act as a frequency map. Use an offset of 1000 to map numbers to non-negative indices (e.g., number `-1000` maps to index `0`, `0` maps to `1000`, `1000` maps to `2000`).
- Iterate through the input `arr` and populate `freqCounts`. For each `num`, increment `freqCounts[num + 1000]`.
- The maximum possible frequency is `arr.length`, which is at most 1000. Create a boolean array `seenFreqs` of size 1001 to track which frequencies have been seen.
- Iterate through the `freqCounts` array.
- For each `count` in `freqCounts` that is greater than 0 (meaning it's an actual frequency of a number from `arr`):
  - If `seenFreqs[count]` is already `true`, it means this frequency has appeared before. Return `false`.
  - Otherwise, mark this frequency as seen by setting `seenFreqs[count]` to `true`.
- If the loop completes without returning, all frequencies were unique. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean uniqueOccurrences(int[] arr) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : arr) {
      cnt.merge(x, 1, Integer : : sum);
    }
    return new HashSet<>(cnt.values()).size() == cnt.size();
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool uniqueOccurrences(vector<int> &arr) {
    unordered_map<int, int> cnt;
    for (int &x : arr) {
      ++cnt[x];
    }
    unordered_set<int> vis;
    for (auto &[_, v] : cnt) {
      if (vis.count(v)) {
        return false;
      }
      vis.insert(v);
    }
    return true;
  }
};

```

### Python

```python
class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool: cnt = Counter(arr) return len(set(cnt . values())) == len(cnt)

```