Unique Number of Occurrences — Double Hash Validation in One Pass

Problem Statement#

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique, or false otherwise.

Constraints:

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

Example 1:
Input:  arr = [1, 2, 2, 1, 1, 3]
Output: true
Explanation: 1 occurs 3 times, 2 occurs 2 times, 3 occurs 1 time.
             All occurrence counts are distinct: {3, 2, 1}.

Example 2:
Input:  arr = [1, 2]
Output: false
Explanation: Both 1 and 2 occur 1 time. Not unique.

Example 3:
Input:  arr = [-3, 0, 1, -3, 1, 1, 1, -3, 10, 0]
Output: true
Explanation: -3→3, 0→2, 1→4, 10→1. Counts {3,2,4,1} are all distinct.

Why This Problem Matters#

Unique Number of Occurrences is a clean demonstration of the double-hash pattern: use one hash structure to compute a property (element frequency), then use a second hash structure to verify a constraint on those properties (frequency uniqueness). This two-layer approach appears throughout software engineering: validating database constraints, checking data integrity in ETL pipelines, and verifying schema properties in distributed systems.

The problem is rated Easy, but it tests a conceptual nuance that separates candidates who think in abstractions from those who think only in loops. The key question is: after building the frequency map, how do you check if all values are distinct? The elegant answer is to convert the values to a set and compare the set size to the map size. If the sizes differ, at least two elements share the same frequency. If they are equal, all frequencies are distinct.

Companies like Amazon use this problem to verify that candidates know when to use sets for deduplication. A candidate who proposes a nested loop (for each pair of values, check if their frequencies are equal) solves the problem in O(n^2) and signals that they do not think in terms of appropriate data structures. The O(n) solution — frequency map + set comparison — is immediate once you have the right mental model.

The pattern of "compute a map, then check a property of the map's values" is also the foundation of several harder problems: checking if a matrix row's frequency map matches a column's frequency map (Equal Row and Column Pairs), verifying that a sorted rearrangement is possible (Task Scheduler), and validating schedule uniqueness in constraint satisfaction problems.

The Core Insight#

The algorithm has two phases:

Phase 1 — Build frequency map: For each element in arr, count how many times it appears. This gives a map from element to count.

Phase 2 — Verify frequency uniqueness: Collect all frequency values. If any two elements have the same frequency, the values are not unique. Check this by inserting frequency values into a set: if the set size equals the number of distinct elements, all frequencies are unique. If the set is smaller, at least two frequencies are equal.

In code: len(set(freq.values())) == len(freq) — if converting frequency values to a set reduces the count, there are duplicates.

Why does this work? A set automatically deduplicates. If all frequency values are distinct, the set has the same size as the original collection of frequencies. If any two are equal, the set is smaller.

An alternative: len(set(freq.values())) == len(set(freq.keys())) — but set(freq.keys()) is just set(freq) which equals len(freq) since keys are already unique. So the canonical form is len(set(freq.values())) == len(freq).

Visual Dry Run#

Input: arr = [1, 2, 2, 1, 1, 3]

Phase 1 — Frequency map:

freq = {1: 3, 2: 2, 3: 1}

Phase 2 — Frequency uniqueness check:

Frequency values: [3, 2, 1] Set of frequency values: {3, 2, 1}

len({3, 2, 1}) = 3 == len(freq) = 3 → True

All frequencies are distinct. Return true.

Input: arr = [1, 2]

Phase 1: freq = {1: 1, 2: 1}

Phase 2: Frequency values: [1, 1] Set: {1}

len({1}) = 1 ≠ len(freq) = 2 → False

Two elements share frequency 1. Return false.

Solution (Optimal)#

from collections import Counter
 
def uniqueOccurrences(arr: list[int]) -> bool:
    # Phase 1: Count occurrences of each element
    freq = Counter(arr)
 
    # Phase 2: Check if all occurrence counts are distinct
    # Convert frequency values to a set; if size matches, all are unique
    return len(set(freq.values())) == len(freq)
 
 
# Explicit two-pass version for clarity
def uniqueOccurrences_explicit(arr: list[int]) -> bool:
    # Build frequency map
    freq = {}
    for x in arr:
        freq[x] = freq.get(x, 0) + 1
 
    # Check uniqueness of frequency values
    seen_counts = set()
    for count in freq.values():
        if count in seen_counts:
            return False
        seen_counts.add(count)
    return True

var uniqueOccurrences = function(arr) {
    // Phase 1: Build frequency map
    const freq = new Map();
    for (const x of arr) {
        freq.set(x, (freq.get(x) || 0) + 1);
    }
 
    // Phase 2: Check if all frequency values are distinct
    const freqValues = [...freq.values()];
    return new Set(freqValues).size === freqValues.length;
};

Complexity Analysis

The frequency map + set comparison is optimal at O(n) time and O(n) space. The number of distinct frequencies is at most n (each element could have a unique count), so the set comparison is O(n) as well.

Common Mistakes#

• Confusing len(set(arr)) with len(set(freq.values())). len(set(arr)) is the number of distinct values in the array. len(set(freq.values())) is the number of distinct occurrence counts. These are different things.
• Checking frequency keys instead of frequency values. set(freq.keys()) gives the distinct elements, not distinct frequencies. Always check .values().
• Using a list comprehension that removes the uniqueness guarantee. [freq[x] for x in arr] gives a frequency for each element in the original array (with repetitions). You want frequencies for each distinct element: list(freq.values()).
• Not handling negative integers. The constraint allows arr[i] in [-1000, 1000]. Negative integers are valid map keys — no special handling needed.
• Assuming the maximum frequency is bounded by arr.length. This is always true (a single element can appear at most len(arr) times), but it does not affect the algorithm.

Follow-up Questions#

What if you need to return the value with the unique occurrence count? Find the occurrence count that appears exactly once across all frequency values. Use a second frequency map on the values of the first.

What if you need to find which elements have duplicate occurrence counts? Invert the logic: for each frequency value, collect all elements with that frequency. Return elements whose frequency value appears more than once in the frequency map's values.

How would you extend this to a stream of integers? Maintain a frequency map that updates with each new integer. On each "check unique" query, convert the map values to a set and compare sizes. Each query is O(k) where k is the number of distinct elements seen so far.

What is the maximum number of distinct elements for which unique occurrence counts are possible? If k elements have unique occurrence counts, the counts are at least {1, 2, 3, ..., k}, summing to k*(k+1)/2. The array length must be at least this sum. For arr.length = 1000, the maximum k satisfies k*(k+1)/2 ≤ 1000, giving k ≤ 44.

How does this differ from checking if a sequence is a permutation of 1..n? Permutation check verifies that specific values (1 through n) each appear exactly once. Unique occurrence check verifies that whatever occurrence counts exist, they are all distinct from each other — a different constraint.

Key Takeaways#

• LC 1207 Unique Number of Occurrences is a two-step hash problem: count, then check uniqueness.
• Step 1: build a frequency Counter/Map for the input array in O(n).
• Step 2: compare len(set(counter.values())) == len(counter.values()) — if equal, all frequencies are distinct.
• Time and space are both O(n); negative integers, zero, and duplicates are all fine.
• Single pass plus one set conversion suffices — no sorting needed.
• The "double-hashing" pattern (hash to count, hash to dedupe values) appears in LC 350, LC 451, and many ranking problems.
• Equivalent one-liner: return len(set(Counter(arr).values())) == len(set(arr)) (Python) — concise and idiomatic.

Related Problems#

• LC 1207 — Unique Number of Occurrences: This problem.
• LC 242 — Valid Anagram: Check if two strings have identical character frequency maps — related frequency comparison.
• LC 2215 — Find the Difference of Two Arrays: Find elements unique to each array — set difference.
• LC 347 — Top K Frequent Elements: Find elements by frequency rank — frequency map with ordering.
• LC 451 — Sort Characters By Frequency: Sort characters by their occurrence count in descending order.
• LC 2053 — Kth Distinct String in an Array: Find strings with exactly frequency 1 — direct application of frequency maps.