Unique Number of Occurrences

Easy
589.

Unique Number of Occurrences

Unique Number of Occurrences is an easy coding problem on arrays and hash table, asked in Amazon and TCS interviews.

Given an array of integers arr, return true if the number of occurrences of each value is unique — no two distinct values occur the same number of times.

Example 1

Input
arr = [1,2,2,1,1,3]
Output
true
Explanation
1 occurs three times, 2 twice and 3 once — all different.

Example 2

Input
arr = [1,2]
Output
false
Explanation
Both values occur once.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {boolean}
 */
var uniqueOccurrences = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Unique Number of Occurrences — Problem & Solution

Unique Number of Occurrences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Unique Number of Occurrences is an easy coding problem on arrays and hash table, asked in Amazon and TCS interviews.

  • Difficulty: Easy
  • Topics: Arrays, Hash Table
  • Asked at: Amazon, TCS
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of integers arr, return true if the number of occurrences of each value is unique — no two distinct values occur the same number of times.

Example 1

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: 1 occurs three times, 2 twice and 3 once — all different.

Example 2

Input: arr = [1,2]
Output: false
Explanation: Both values occur once.

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

Hints for Unique Number of Occurrences

  1. Hint 1

    Two passes: count the values, then check the counts for duplicates.

  2. Hint 2

    A set of the counts is the cleanest way to test uniqueness.

  3. Hint 3

    Return false the moment a count repeats.

How to solve Unique Number of Occurrences

Build the frequency map, then treat its values as the thing to deduplicate. If inserting a count into a set ever collides, two values share a frequency.

Approach

  1. Count occurrences of every distinct value.
  2. Walk the counts, inserting each into a set.
  3. Return false on the first collision, true otherwise.

Why it works

Uniqueness of the multiset of counts is exactly the property asked for, and a set answers it in one linear pass.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Comparing the count map's size with the array length answers a different question.
  • Sorting the counts and checking neighbours also works — just remember to sort the values, not the keys.

Reference solution

Python

from typing import List

def uniqueOccurrences(arr: List[int]) -> bool:
    count = {}
    for x in arr:
        count[x] = count.get(x, 0) + 1
    counts = list(count.values())
    return len(counts) == len(set(counts))

Java

public static boolean uniqueOccurrences(int[] arr) {
    HashMap<Integer, Integer> count = new HashMap<>();
    for (int x : arr) count.put(x, count.getOrDefault(x, 0) + 1);
    HashSet<Integer> seen = new HashSet<>();
    for (int c : count.values()) {
        if (!seen.add(c)) return false;
    }
    return true;
}

C++

bool uniqueOccurrences(vector<int>& arr) {
    unordered_map<int, int> count;
    for (int x : arr) count[x]++;
    unordered_set<int> seen;
    for (auto& e : count) {
        if (seen.count(e.second)) return false;
        seen.insert(e.second);
    }
    return true;
}

JavaScript

var uniqueOccurrences = function(arr) {
    const count = {};
    for (let i = 0; i < arr.length; i++) {
        const k = String(arr[i]);
        count[k] = (count[k] || 0) + 1;
    }
    const seen = {};
    const keys = Object.keys(count);
    for (let i = 0; i < keys.length; i++) {
        const c = String(count[keys[i]]);
        if (seen[c] === true) return false;
        seen[c] = true;
    }
    return true;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets