Unique Number of Occurrences — InterviewPrepKit

Solving tips

Recognize two composed sub-problems: count each value's frequency, then check that the frequencies have no duplicates.
Build a Counter, then return len(freq) == len(set(freq.values())) — deduplicating the frequencies shrinks the set exactly when two values collide on a count. O(n) time, O(n) space.
Alternative duplicate check: sort the frequency list and compare adjacent pairs (useful without cheap hash sets).
Pitfall: deduplicate the frequencies (freq.values()), not the values themselves; compare against len(freq), not len(arr).

Problem

Given an integer array arr, decide whether every distinct value appears a different number of times. Return True if no two distinct values share the same frequency, False otherwise.

Examples

arr = [1, 2, 2, 1, 1, 3] → True — 1 appears 3 times, 2 appears twice, 3 appears once: frequencies {3, 2, 1} are all different.
arr = [1, 2] → False — both values appear exactly once.
arr = [-3, 0, 1, -3, 1, 1, 8, 8, -3, 4] → False — both -3 and 1 appear 3 times, so two distinct values collide on the same frequency.

Constraints

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

The bounds are tiny — even a quadratic solution passes — but the clean answer is a single linear counting pass.

Think about it first

Hint 1

The problem is really two sub-problems: first compute the frequency of each distinct value, then check a property of those frequencies.

Hint 2

"No two frequencies are equal" is the same as saying the collection of frequencies contains no duplicates. How do you detect duplicates in one line?

Hint 3

Build a `Counter` of the array, then compare `len(counter.values())` with the size of `set(counter.values())` — if deduplicating shrinks the collection, two values shared a frequency.

TL;DR

Counter, then compare count of frequencies to count of distinct frequencies — O(n) time, O(n) space.

Approach 1 — Brute force

For every distinct value, count its occurrences with a fresh scan; then compare every pair of distinct values’ counts.

from typing import List


class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        distinct = []
        for x in arr:
            if x not in distinct:
                distinct.append(x)
        counts = [arr.count(x) for x in distinct]
        for i in range(len(counts)):
            for j in range(i + 1, len(counts)):
                if counts[i] == counts[j]:
                    return False
        return True

Complexity: O(n²) time (each arr.count is a full scan, plus the pairwise comparison), O(n) space.

With n <= 1000 this actually passes — the constraints don’t kill it, but it repeats work the hash map does once, and at interview scale (10^5+) it would time out.

Approach 2 — Counter + set of frequencies

The insight: the question “are all frequencies distinct?” is exactly “does the list of frequencies contain a duplicate?”, and a set detects duplicates for free — putting the frequencies into a set shrinks it precisely when two values collide on the same count.

collections.Counter is Python’s standard hash-map subclass that tallies how many times each element occurs in one pass.

from collections import Counter
from typing import List


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

Walkthrough on arr = [1, 2, 2, 1, 1, 3]:

Counter pass: freq = {1: 3, 2: 2, 3: 1} — three distinct values.
Frequencies: [3, 2, 1]; as a set: {3, 2, 1} — still size 3.
3 == 3 → return True.

And on arr = [1, 2]: freq = {1: 1, 2: 1} has 2 entries, but set(freq.values()) is {1} with size 1 — 2 != 1 → False.

Complexity: O(n) time, O(n) space for the counter and the set.

Approach 3 — Sort the frequencies

The insight: duplicates in a sorted list are always adjacent, so instead of a second hash set you can sort the frequency list and look at neighbors. Same answer, different duplicate-detection tool — worth knowing for languages without cheap hash sets.

from collections import Counter
from typing import List


class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        counts = sorted(Counter(arr).values())
        return all(a != b for a, b in zip(counts, counts[1:]))

Walkthrough on arr = [1, 2, 2, 1, 1, 3]:

Frequencies [3, 2, 1] → sorted [1, 2, 3].
Adjacent pairs (1, 2) and (2, 3) are both unequal → True.

Complexity: O(n + k log k) time where k is the number of distinct values, O(n) space.

Common pitfalls

Deduplicating the values instead of the frequencies — len(set(arr)) tells you nothing about occurrence counts.
Comparing len(set(freq.values())) against len(arr) instead of against len(freq) (the number of distinct values).
Forgetting that negative values are allowed — an array-indexed count table needs an offset, whereas a hash map does not care.

Pattern takeaway

Hash maps compose: one map answers “how often does each value occur?”, and feeding its values into a set answers a question about the counts themselves. When a problem asks about a property of frequencies, count first, then treat the frequencies as just another collection to query.