1207. Unique Number of Occurrences

EasyArrayHash Table
Leetcode Link

Problem Description

In this problem, we are given an array of integers, arr. Our task is to determine whether the array has the property that no two different numbers appear the same number of times. In other words, each integer's frequency (how often it occurs in the array) should be unique. If this property holds, we return true, otherwise, we return false.

For example, suppose the input array is [1, 2, 2, 1, 1, 3]. Here, the number 1 occurs three times, number 2 occurs twice, and number 3 occurs once. Since all these frequencies (3, 2, 1) are unique, our function would return true.

However, if we have an array like [1, 2, 2, 3, 3, 3], where 1 occurs once, 2 occurs twice, and 3 also occurs three times, we see that the frequencies are not unique. In this case, our function would return false.

Intuition

To solve this problem, we can follow these steps:

  1. Count the occurrences of each value in the array.
  2. Check if the counts are all unique.

The intuition behind the solution lies in the frequency counting mechanic. We can use a data structure that allows us to count the occurrence of each element efficiently. The Python Counter class from the collections module is perfect for this job as it creates a dictionary with array elements as keys and their counts as values.

Once we have the counts, we need to check if they are unique. We can convert the counts into a set, which only contains unique elements. If the length of the set of counts (unique frequencies) is equal to the length of the original dictionary of counts, then all frequencies were unique, and we can return true. Otherwise, we return false.

Let's illustrate this with our [1, 2, 2, 1, 1, 3] example:

  • Step 1: Counter(arr) would give us {1: 3, 2: 2, 3: 1} indicating that 1 appears thrice, 2 appears twice, and 3 appears once.
  • Step 2: We check with len(set(cnt.values())) == len(cnt) which compares len({3, 2, 1}) to len({1: 3, 2: 2, 3: 1}). Since both lengths are 3, they are equal, and the function returns true.

This simple yet efficient approach helps us to determine the uniqueness of each number's occurrences in the given array.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

Which technique can we use to find the middle of a linked list?

Solution Approach

The solution implementation harnesses the Python collections.Counter class to count the frequency of each element in the input array arr. The Counter class essentially implements a hash table (dictionary) under the hood, which allows efficient frequency counting of hashable objects. Here's a breakdown of the implementation steps according to the provided code:

Step by Step Implementation:

  1. The Counter(arr) creates a dictionary-like object, where keys are the elements from arr, and the values are their respective counts. This step uses a hash table internally to store the counts, offering O(n) time complexity for counting all elements in the array, where n is the length of the array.

    For example, if arr = [1, 2, 2, 3], Counter(arr) would produce Counter({2: 2, 1: 1, 3: 1}).

  2. The expression set(cnt.values()) takes all the values from the dictionary returned by Counter(arr)—which are the frequencies of elements—and converts them into a set. Since a set can only contain unique elements, this casting effectively filters out any duplicate counts.

    Continuing the example above, set(cnt.values()) converts [2, 1, 1] to {1, 2}.

  3. The comparison len(set(cnt.values())) == len(cnt) is checking whether the number of unique frequencies (length of the set) is equal to the number of distinct elements in arr (length of the Counter dictionary). An equality indicates that all frequencies are unique.

    In our continuing example, len({1, 2}) == len(Counter({2: 2, 1: 1, 3: 1})) reduces to 2 == 3, which is False, reflecting that not all occurrences are unique since 1 and 3 both occur once.

This solution is both elegant and efficient, utilizing the properties of sets and hash tables to check for the uniqueness of the elements' frequencies in the array. There's no need for additional loops or explicit checks for duplicates; the data structures do the heavy lifting. The overall time complexity is O(n), dominated by the counting process. The space complexity is also O(n), as it's necessary to store the counts of elements which, in the worst case, can be as many as the number of elements in the array if all are unique.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Which of these pictures shows the visit order of a depth-first search?

Example Walkthrough

Let's walk through a small example to illustrate the solution approach. Suppose we have the input array arr = [4, 5, 4, 6, 6, 6]. We want to determine if no two different numbers in the array have the same frequency.

Following the steps outlined in the solution approach:

Step 1: Utilize the Counter class to count the occurrences of each element in arr.

We execute cnt = Counter(arr) and get Counter({4: 2, 6: 3, 5: 1}). This tells us that the number 4 appears twice, 6 appears three times, and 5 appears once.

Step 2: Convert the counts to a set to check uniqueness.

We convert the values, which are the frequencies, to a set using set(cnt.values()) and obtain {1, 2, 3}. This set represents the unique frequencies of the numbers in our array.

Step 3: Compare the length of the set of counts to the length of the dictionary of counts to determine if the frequencies are all unique.

We perform the comparison len(set(cnt.values())) == len(cnt). The length of our set {1, 2, 3} is 3, and the length of our Counter dictionary {4: 2, 6: 3, 5: 1} is also 3.

Since 3 == 3, we can affirm that all counts are unique and therefore return true for our input array.

The array [4, 5, 4, 6, 6, 6] confirms our solution's criteria, meaning that no two different numbers in our array appear the same number of times. Hence, our illustrated function returns true.

Solution Implementation

1from collections import Counter
2from typing import List
3
4class Solution:
5    def uniqueOccurrences(self, arr: List[int]) -> bool:
6        # Create a Counter object that counts occurrences of each element in the array.
7        element_count = Counter(arr)
8      
9        # Convert the values of the Counter (which represent the occurrences of each unique element) to a set.
10        # This will remove any duplicate counts.
11        unique_occurrences = set(element_count.values())
12      
13        # Check if the number of unique occurrences is equal to the number of unique elements.
14        # If they are equal, it means that no two elements have the same number of occurrences.
15        return len(unique_occurrences) == len(element_count)
16
1class Solution {
2    // This method checks if all elements in the array have unique occurrence counts.
3    public boolean uniqueOccurrences(int[] arr) {
4        // Create a hashmap to store the counts of each number.
5        Map<Integer, Integer> countMap = new HashMap<>();
6      
7        // Iterate over the array and populate the countMap.
8        for (int number : arr) {
9            // If the number is already in the map, increment its count, otherwise insert it with count 1.
10            countMap.merge(number, 1, Integer::sum);
11        }
12      
13        // Create a hashset containing all the values (occurrence counts) from the countMap.
14        Set<Integer> occurrenceSet = new HashSet<>(countMap.values());
15      
16        // If the size of the set (unique occurrences) is the same as the size of the map (unique numbers),
17        // it means that all occurrence counts are unique and we return true. Otherwise, return false.
18        return occurrenceSet.size() == countMap.size();
19    }
20}
21
1#include <vector>
2#include <unordered_map>
3#include <unordered_set>
4using namespace std;
5
6class Solution {
7public:
8    // Function to check if the array has a unique number of occurrences for each element
9    bool uniqueOccurrences(vector<int>& arr) {
10        // Map to store the frequency of each element
11        unordered_map<int, int> frequencyMap;
12      
13        // Increment the frequency count for each element in arr
14        for (int element : arr) {
15            ++frequencyMap[element];
16        }
17      
18        // Set to store unique occurrence counts
19        unordered_set<int> occurrencesSet;
20      
21        // Iterate through the frequency map
22        for (auto& keyValue : frequencyMap) {
23            int occurrence = keyValue.second; // Get the occurrence/frequency count of the element
24          
25            // Check if the occurrence count is already in the occurrences set
26            if (occurrencesSet.count(occurrence)) {
27                // If already present, it's not unique and returns false
28                return false;
29            }
30            // If not present, add the occurrence count to the set
31            occurrencesSet.insert(occurrence);
32        }
33      
34        // All occurrence counts were unique, return true
35        return true;
36    }
37};
38
1// This function checks if all the elements in the array 'arr' have unique occurrences
2function uniqueOccurrences(arr: number[]): boolean {
3    // Create a Map to count occurrences of each element
4    const occurrenceCount: Map<number, number> = new Map();
5  
6    // Iterate over each element in the array
7    for (const num of arr) {
8        // If the element is already in the Map, increment its occurrence count
9        // Otherwise, add the element with an occurrence count of 1
10        occurrenceCount.set(num, (occurrenceCount.get(num) || 0) + 1);
11    }
12
13    // Create a Set from the values of the Map
14    // This will automatically remove any duplicate occurrence counts
15    const uniqueCounts: Set<number> = new Set(occurrenceCount.values());
16
17    // Compare the size of the Set (unique counts) with the size of the Map (all counts)
18    // If they are equal, all occurrence counts are unique
19    return uniqueCounts.size === occurrenceCount.size;
20}
21
Not Sure What to Study? Take the 2-min Quiz：

A heap is a ...?

Time and Space Complexity

The time complexity of the given code is O(n), where n is the length of the array arr. This is because counting the occurrences of each element in the array with Counter(arr) requires a single pass over all elements in arr, and then converting the counts into a set and comparing the sizes involves operations that are also O(n) in the worst case.

The space complexity of the code is also O(n). The counter object cnt will store as many entries as there are unique elements in arr. In the worst case, where all elements are unique, the space required for the counter would be O(n). Additionally, when the counts are converted to a set to ensure uniqueness, it occupies another space that could at most be O(n), if all counts are unique.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What's the output of running the following function using the following tree as input? 

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12
1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18
1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

Recommended Readings

LeetCode Patterns - Top Patterns for Coding Interviews

Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture

Recursion Review

Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first

Runtime to Algo Cheat Sheet

Runtime Overview When learning about algorithms and data structures you'll frequently encounter the term time complexity This concept is fundamental in computer science and offers insights into how long an algorithm takes to complete given a certain input size What is Time Complexity Time complexity represents the amount of time

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA 👨‍🏫