1207. Unique Number of Occurrences - Solution

Q: Is Unique Number of Occurrences easy or hard?

LeetCode classifies this problem as Easy. The challenge mainly tests understanding of frequency counting and set-based uniqueness checks. Developers comfortable with hash maps and basic array traversal typically solve it quickly.

Q: Unique Number of Occurrences Python/Java solution

In Python, use collections.Counter or a dictionary to count frequencies, then compare the length of the frequency list with the length of a set built from it. In Java, use HashMap for counting and HashSet for uniqueness checks. Both implementations run in O(n) time.

The problem

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

Approach overview

Problem Overview: You receive an integer array and need to verify whether the frequency of every value is unique. If two different numbers appear the same number of times, the result is false. Otherwise, return true.

Approach 1: Hash Map and Set (O(n) time, O(n) space)

The direct solution uses a frequency counter. Iterate through the array and store counts in a hash map where the key is the number and the value is its occurrence count. After building the map, iterate over the frequency values and insert them into a set. A set automatically removes duplicates, so if any frequency repeats, the set size will be smaller than the number of unique elements.

This works because hash lookups and insertions run in constant average time. The key insight is separating the problem into two steps: counting occurrences and verifying uniqueness of those counts. The array is scanned once to build frequencies and once more to validate uniqueness, giving O(n) time complexity and O(n) space for the hash structures. This method is commonly implemented with a hash table from the Hash Table family while iterating over the Array.

Approach 2: Sorting and Comparison (O(n log n) time, O(n) space)

Another option avoids a set by sorting the frequency values. First compute counts using a hash map. Extract the frequencies into a list and sort them. After sorting, duplicate frequencies become adjacent, so a single linear scan can detect whether two consecutive counts are equal.

The main cost comes from sorting the frequency list, which takes O(k log k) where k is the number of distinct elements. In the worst case k = n, giving O(n log n) time complexity. Space usage remains O(n) due to the frequency map and the list used for sorting. This approach is sometimes preferred when you already rely on sorting for additional processing or want a simple comparison-based check.

Recommended for interviews: The hash map + set approach is the expected solution. It demonstrates correct use of frequency counting and constant-time membership checks. Interviewers often accept the sorting method, but the linear-time hash solution shows stronger understanding of hash-based data structures and optimal complexity.

Approach 1: Hash Map and Set

In this approach, we will first traverse the array to count the occurrences of each element using a hash map. Then, we will use a set to check if these occurrences are unique. If the size of the set matches the size of the occurrence counts, it implies all occurrences are unique.

Python

def uniqueOccurrences(arr):
    from collections import Counter
    count = Counter(arr)
    occurrences = set(count.values())
    return len(occurrences) == len(count)

arr = [1, 2, 2, 1, 1, 3]
print(uniqueOccurrences(arr))

Java

import java.util.HashMap;
import java.util.HashSet;

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

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 1, 1, 3};
        System.out.println(uniqueOccurrences(arr));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <unordered_set>

bool uniqueOccurrences(std::vector<int>& arr) {
    std::unordered_map<int, int> countMap;
    for (int num : arr) {
        ++countMap[num];
    }
    std::unordered_set<int> occurrences;
    for (const auto& pair : countMap) {
        if (!occurrences.insert(pair.second).second) {
            return false;
        }
    }
    return true;
}

int main() {
    std::vector<int> arr = {1, 2, 2, 1, 1, 3};
    std::cout << (uniqueOccurrences(arr) ? "true" : "false") << std::endl;
    return 0;
}

JavaScript

function uniqueOccurrences(arr) {
    const countMap = new Map();
    for (const num of arr) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }
    const occurrences = new Set(countMap.values());
    return occurrences.size === countMap.size;
}

const arr = [1, 2, 2, 1, 1, 3];
console.log(uniqueOccurrences(arr));

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

bool uniqueOccurrences(int* arr, int arrSize) {
    int count[2001] = {0};
    int hash[1001] = {0};
    
    for(int i = 0; i < arrSize; i++) {
        count[arr[i] + 1000]++;
    }
    
    for(int i = 0; i < 2001; i++) {
        if(count[i] > 0) {
            if(hash[count[i]])
                return false;
            hash[count[i]] = 1;
        }
    }
    
    return true;
}

int main() {
    int arr[] = {1, 2, 2, 1, 1, 3};
    int arrSize = sizeof(arr) / sizeof(arr[0]);
    printf("%s\n", uniqueOccurrences(arr, arrSize) ? "true" : "false");
    return 0;
}

using System;
using System.Collections.Generic;

public class Program {
    public static bool UniqueOccurrences(int[] arr) {
        Dictionary<int, int> countMap = new Dictionary<int, int>();
        foreach (int num in arr) {
            if (countMap.ContainsKey(num)) countMap[num]++;
            else countMap[num] = 1;
        }
        HashSet<int> occurrences = new HashSet<int>();
        foreach (int count in countMap.Values) {
            if (!occurrences.Add(count)) return false;
        }
        return true;
    }

    public static void Main() {
        int[] arr = {1, 2, 2, 1, 1, 3};
        Console.WriteLine(UniqueOccurrences(arr));
    }
}

The Python version uses a Counter from collections to count occurrences and then compares the size of the set of these counts to ensure uniqueness.

Complexity

Time Complexity: O(n), as we iterate over the array and then the unique counts.
Space Complexity: O(n), for the Counter and set.

Try this approach in the editor

Approach 2: Sorting and Comparison

This alternative approach starts by counting occurrences just like the first one. After that, it stores these counts in a list, sorts the list, and then checks for any consecutive equal elements, which would indicate duplicate occurrences.

Python

def uniqueOccurrences(arr):
    from collections import Counter
    count = Counter(arr)
    occurrences = sorted(count.values())
    for i in range(1, len(occurrences)):
        if occurrences[i] == occurrences[i - 1]:
            return False
    return True

arr = [1, 2, 2, 1, 1, 3]
print(uniqueOccurrences(arr))

Java

import java.util.*;

public class UniqueOccurrences {
    public static boolean uniqueOccurrences(int[] arr) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int num : arr) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        List<Integer> occurrences = new ArrayList<>(countMap.values());
        Collections.sort(occurrences);
        for (int i = 1; i < occurrences.size(); i++) {
            if (occurrences.get(i).equals(occurrences.get(i - 1))) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 1, 1, 3};
        System.out.println(uniqueOccurrences(arr));
    }
}

C++

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

bool uniqueOccurrences(std::vector<int>& arr) {
    std::unordered_map<int, int> countMap;
    for (int num : arr) {
        ++countMap[num];
    }

    std::vector<int> occurrenceList;
    for (const auto& pair : countMap) {
        occurrenceList.push_back(pair.second);
    }
    
    std::sort(occurrenceList.begin(), occurrenceList.end());
    
    for (size_t i = 1; i < occurrenceList.size(); ++i) {
        if (occurrenceList[i] == occurrenceList[i - 1]) {
            return false;
        }
    }
    return true;
}

int main() {
    std::vector<int> arr = {1, 2, 2, 1, 1, 3};
    std::cout << (uniqueOccurrences(arr) ? "true" : "false") << std::endl;
    return 0;
}

JavaScript

function uniqueOccurrences(arr) {
    const countMap = new Map();
    for (const num of arr) {
        countMap.set(num, (countMap.get(num) || 0) + 1);
    }
    const occurrences = Array.from(countMap.values()).sort((a, b) => a - b);
    for (let i = 1; i < occurrences.length; i++) {
        if (occurrences[i] === occurrences[i - 1]) {
            return false;
        }
    }
    return true;
}

const arr = [1, 2, 2, 1, 1, 3];
console.log(uniqueOccurrences(arr));

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int cmpfunc (const void * a, const void * b) {
   return (*(int*)a - *(int*)b);
}

bool uniqueOccurrences(int* arr, int arrSize) {
    int count[2001] = {0};
    int occ[1001] = {0};
    int idx = 0;

    for(int i = 0; i < arrSize; i++) {
        count[arr[i] + 1000]++;
    }

    for(int i = 0; i < 2001; i++) {
        if(count[i] > 0) {
            occ[idx++] = count[i];
        }
    }

    qsort(occ, idx, sizeof(int), cmpfunc);

    for(int i = 1; i < idx; i++) {
        if(occ[i] == occ[i - 1])
            return false;
    }

    return true;
}

int main() {
    int arr[] = {1, 2, 2, 1, 1, 3};
    int arrSize = sizeof(arr) / sizeof(arr[0]);
    printf("%s\n", uniqueOccurrences(arr, arrSize) ? "true" : "false");
    return 0;
}

using System;
using System.Collections.Generic;
using System.Linq;

public class Program {
    public static bool UniqueOccurrences(int[] arr) {
        Dictionary<int, int> countMap = new Dictionary<int, int>();
        foreach (int num in arr) {
            if (countMap.ContainsKey(num)) countMap[num]++;
            else countMap[num] = 1;
        }
        List<int> occurrences = countMap.Values.ToList();
        occurrences.Sort();
        for (int i = 1; i < occurrences.Count; i++) {
            if (occurrences[i] == occurrences[i - 1]) return false;
        }
        return true;
    }

    public static void Main() {
        int[] arr = {1, 2, 2, 1, 1, 3};
        Console.WriteLine(UniqueOccurrences(arr));
    }
}

The Python approach sorts the occurrence counts and checks for duplicates in a single pass of the sorted list.

Complexity

Time Complexity: O(n log n), mainly because of sorting.
Space Complexity: O(n), due to storage of the occurrence count list.

Try this approach in the editor

Approach 3: Hash Table

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.

TypeScript

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;
}

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
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Hash Map and Set	Time Complexity: O(n), as we iterate over the array and then the unique counts. Space Complexity: O(n), for the Counter and set.
Sorting and Comparison	Time Complexity: O(n log n), mainly because of sorting. Space Complexity: O(n), due to storage of the occurrence count list.
Hash Table	–

Complexity analysis

Approach	Time	Space	When to Use
Hash Map and Set	O(n)	O(n)	General case. Fastest solution using frequency counting and set uniqueness check.
Sorting and Comparison	O(n log n)	O(n)	Useful when frequency values are already being sorted or when avoiding a set.

Frequently asked questions

Is Unique Number of Occurrences easy or hard?

LeetCode classifies this problem as Easy. The challenge mainly tests understanding of frequency counting and set-based uniqueness checks. Developers comfortable with hash maps and basic array traversal typically solve it quickly.

Unique Number of Occurrences Python/Java solution

In Python, use collections.Counter or a dictionary to count frequencies, then compare the length of the frequency list with the length of a set built from it. In Java, use HashMap<Integer, Integer> for counting and HashSet<Integer> for uniqueness checks. Both implementations run in O(n) time.

How to solve Unique Number of Occurrences in O(n)?

Use a hash map to count how many times each number appears. Then iterate through the frequency values and insert them into a set. If a frequency already exists in the set, two numbers share the same occurrence count and the answer is false. Otherwise, all counts are unique, producing a true result in O(n) time.

What is the best approach for Unique Number of Occurrences?

The hash map and set approach is the most efficient and commonly expected solution. First count each number's frequency using a hash map, then insert the counts into a set to ensure all frequencies are unique. If the number of frequencies equals the set size, all counts are unique. This runs in O(n) time and O(n) space.

Is Unique Number of Occurrences asked at Google/Amazon/Meta?

Frequency counting and hash table validation problems appear frequently in interviews at companies like Amazon, Google, and Meta. While this exact problem may vary, the pattern of counting elements and verifying constraints using hash structures is a common interview topic.

What data structure is used in Unique Number of Occurrences?

The primary data structures are a hash map and a set. The hash map stores element frequencies, and the set checks whether those frequencies repeat. Both provide constant-time average insert and lookup operations, enabling an O(n) solution.

What is the time complexity of Unique Number of Occurrences?

The optimal solution runs in O(n) time where n is the array length. Building the frequency map requires one pass through the array, and inserting counts into a set is another linear pass. Hash operations are constant time on average, so the overall complexity remains O(n) with O(n) additional space.

Unique Number of Occurrences solution and explanation

The problem

Approach overview

Approach 1: Hash Map and Set

Approach 2: Sorting and Comparison

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Unique Number of Occurrences solution and explanation

The problem

Approach overview

Approach 1: Hash Map and Set

Approach 2: Sorting and Comparison

Approach 3: Hash Table

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems