Unique Number of Occurrences

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 small, so even a quadratic solution passes. A single linear counting pass is cleaner.

Think about it first

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


def uniqueOccurrences(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 passes, but it repeats work a hash map does once. At larger scale (10^5+ elements) it would time out.

Approach 2 — Counter + set of frequencies

The insight: the question “are all frequencies distinct?” is the same as “does the list of frequencies contain a duplicate?” A set answers this: inserting the frequencies into a set shrinks the collection exactly when two values share 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


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

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

1. Counter pass: freq = {1: 3, 2: 2, 3: 1} — three distinct values.
2. Frequencies: [3, 2, 1]; as a set: {3, 2, 1} — still size 3.
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 compare neighbors. Same answer, a different duplicate-detection tool, and useful in languages without cheap hash sets.

from collections import Counter
from typing import List


def uniqueOccurrences(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]:

1. Frequencies [3, 2, 1] → sorted [1, 2, 3].
2. 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.