Leetcode – Unique Number of Occurrences Solution

Spread the love

The “Unique Number of Occurrences” problem on LeetCode is an interesting challenge that can serve as an excellent exercise to practice your skills in Python, particularly in dealing with lists and dictionaries. It examines your ability to manipulate data structures, count frequencies, and ensure uniqueness — all essential skills for tackling more complicated problems in computer science.

In this article, we will conduct a deep dive into multiple approaches to solve this problem, from brute-force methods to more optimized solutions. We will assess their time and space complexities, and through code examples, we will understand how to implement these algorithms.

Problem Statement

Description

Given an integer array arr, the task is to return True if the number of occurrences of each value in the array is unique, otherwise return False.

Constraints

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

Understanding the Problem

At a glance, the problem seems straightforward: count the occurrences of each number in the array and ensure that these counts are unique. If they are unique, return True, otherwise False.

Approaches

Approach 1: Using Two Dictionaries

A simple approach would involve using two dictionaries: one to keep track of the occurrences of each number and another to keep track of the frequency of these occurrences.

Algorithm

  1. Create an empty dictionary num_count to count the occurrences of each number in arr.
  2. Create another empty dictionary freq_count to count the occurrences of each frequency.
  3. Traverse through the array to populate num_count.
  4. Traverse through num_count to populate freq_count.
  5. Check if all frequencies are unique.

Python Code Implementation

def uniqueOccurrences(arr):
    num_count = {}
    freq_count = {}

    for num in arr:
        num_count[num] = num_count.get(num, 0) + 1
    
    for freq in num_count.values():
        freq_count[freq] = freq_count.get(freq, 0) + 1

    return all(value == 1 for value in freq_count.values())

# Test the function
print(uniqueOccurrences([1, 2, 2, 1, 1, 3]))  # Output should be True
print(uniqueOccurrences([1, 2]))  # Output should be False

Time Complexity

The time complexity for this approach is O(n), where n is the length of the array arr.

Space Complexity

The space complexity is O(n) for the dictionaries.

Approach 2: Using One Dictionary and a Set

While the above method is straightforward, it involves traversing dictionaries multiple times. We can optimize the process by using only one dictionary and a set.

Algorithm

  1. Create an empty dictionary num_count to count the occurrences of each number in arr.
  2. Create an empty set unique_freq to keep track of unique frequencies.
  3. Traverse through the array to populate num_count while also updating unique_freq.
  4. Check if the size of unique_freq is equal to the size of num_count.

Python Code Implementation

def uniqueOccurrences(arr):
    num_count = {}
    unique_freq = set()

    for num in arr:
        num_count[num] = num_count.get(num, 0) + 1

    for freq in num_count.values():
        unique_freq.add(freq)

    return len(unique_freq) == len(num_count)

# Test the function
print(uniqueOccurrences([1, 2, 2, 1, 1, 3]))  # Output should be True
print(uniqueOccurrences([1, 2]))  # Output should be False

Time Complexity

The time complexity for this approach is O(n).

Space Complexity

The space complexity is O(n), but the extra space needed for the set is smaller than the additional dictionary in Approach 1.

Conclusion

The “Unique Number of Occurrences” problem serves as a good introduction to frequency counting and basic data structure manipulation in Python. The approaches discussed above offer their own advantages: the first approach is straightforward but slightly less efficient in terms of space, while the second approach optimizes for space by using a set to keep track of unique frequencies.

Leave a Reply