algoadvance

Leetcode 1207. Unique Number of Occurrences

Problem Statement

  1. Unique Number of Occurrences

Given an array of integers arr, write a function that returns true if the number of occurrences of each value in the array is unique, or false otherwise.

Example:

Example 1:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 occurrences, and 3 has 1 occurrence. 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:

Clarifying Questions

  1. Q: Can the array contain negative numbers?
    • A: Yes, the array can contain integers in the range [-1000, 1000].
  2. Q: What should be returned if the array is empty?
    • A: Since the constraint guarantees at least one element, this situation will not occur.
  3. Q: Are there any special values or edge cases to consider?
    • A: Consider cases where all the elements are the same or where all elements are unique.

Strategy

  1. Count Occurrences: Use a hash map to count the occurrences of each number in the array.
  2. Check Uniqueness: Use a set to check whether these counts are unique.

Steps:

  1. Traverse the array and count occurrences using a hash map.
  2. Traverse the hash map to see if all occurrence counts are unique by storing them in a set.
  3. If all counts are unique, return true; otherwise, return false.

Code

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

bool uniqueOccurrences(std::vector<int>& arr) {
    std::unordered_map<int, int> countMap;
    
    // Count the occurrences of each number
    for (int num : arr) {
        countMap[num]++;
    }
    
    std::unordered_set<int> occurrences;
    
    // Check if occurrences are unique
    for (const auto& pair : countMap) {
        if (occurrences.find(pair.second) != occurrences.end()) {
            return false;
        }
        occurrences.insert(pair.second);
    }
    
    return true;
}

int main() {
    std::vector<int> arr1 = {1, 2, 2, 1, 1, 3};
    std::cout << uniqueOccurrences(arr1) << std::endl;  // Output: true

    std::vector<int> arr2 = {1, 2};
    std::cout << uniqueOccurrences(arr2) << std::endl;  // Output: false

    std::vector<int> arr3 = {-3, 0, 1, -3, 1, 1, 1, -3, 10, 0};
    std::cout << uniqueOccurrences(arr3) << std::endl;  // Output: true
    
    return 0;
}

Time Complexity

Time Complexity:

Space Complexity:

Thus, the overall time complexity is ( O(n) ) and the space complexity is ( O(n) ).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI