Grokking the Engineering Manager Coding Interview

0% completed

​

Solution: Unique Number of Occurrences (easy)

Problem Statement

Given an array of integers, determine if the number of times each distinct integer appears in the array is unique.

In other words, the occurrences of each integer in the array should be distinct from the occurrences of every other integer.

Examples:

    • Input: [4, 5, 4, 6, 6, 6]
    • Expected Output: true
    • Justification: The number 4 appears 2 times, 5 appears 1 time, and 6 appears 3 times. All these occurrences (1, 2, 3) are unique.
    • Input: [7, 8, 8, 9, 9, 9, 10, 10]
    • Expected Output: false

.....

.....

.....

Like the course? Get enrolled and start learning!
Pavel Kostenko

Pavel Kostenko

· 2 years ago

In the solution

Space Complexity:

  1. Count Map: We use a hashmap (or dictionary) to store the count of occurrences of each number. In the worst case, if all numbers in the array are unique, the size of the count map is (n). So, the space complexity for the count map is (O(n)).
  2. Unique Counts Set: We use a hashset to store unique counts. In the worst case, if all numbers in the array have a unique count (which is highly unlikely and would mean that each number repeats a unique number of times), the size of the set is (n). So, the space complexity for the unique counts set is (O(n)).

Combining the two data structures, the overall space complexity is (O(n) + O(n) = O(n)).

We can do better

Space complextity for Unique Counts Set does not grows linearly, it grows sub l

Tuan Kiet (Keith) Nguyen

Tuan Kiet (Keith) Nguyen

· a month ago

from collections import Counter
class Solution:
    def uniqueOccurrences(self, arr):
        return len(Counter(arr)) == len(set(Counter(arr).values()))