Skip to content

1207. Unique Number of Occurrences

Description

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

Solutions

Solution 1: Hash Table

Thinking

With \(n \le 1000\) it suffices to count each value and test that those frequencies are unique. One pass builds the counts; a set of the frequencies has the same size as the number of distinct values iff every frequency appears once.

We use a hash table \(cnt\) to count the frequency of each number in the array \(arr\), and then use another hash table \(vis\) to count the types of frequencies. Finally, we check whether the sizes of \(cnt\) and \(vis\) are equal.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of the array \(arr\).

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

1
2
3
4
5
6
7
8
9
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();
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
func uniqueOccurrences(arr []int) bool {
    cnt := map[int]int{}
    for _, x := range arr {
        cnt[x]++
    }
    vis := map[int]bool{}
    for _, v := range cnt {
        if vis[v] {
            return false
        }
        vis[v] = true
    }
    return true
}

1
2
3
4
5
6
7
function uniqueOccurrences(arr: number[]): boolean {
    const cnt: Map<number, number> = new Map();
    for (const x of arr) {
        cnt.set(x, (cnt.get(x) || 0) + 1);
    }
    return cnt.size === new Set(cnt.values()).size;
}

Comments