algoadvance

Leetcode 1207. Unique Number of Occurrences

Problem Statement

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:

  1. Example 1:
    • Input: arr = [1,2,2,1,1,3]
    • Output: true Explanation: The value 1 has 3 occurrences, value 2 has 2 occurrences, and value 3 has 1 occurrence. No two values have the same number of occurrences.
  2. Example 2:
    • Input: arr = [1,2]
    • Output: false Explanation: Both values 1 and 2 occur exactly once.
  3. 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 negative numbers.
  2. Q: Are there any constraints on the values within the array?
    • A: Yes, the values range between -1000 and 1000.

Strategy

  1. Count occurrences: Use a HashMap to count the occurrences of each number in the array.
  2. Store occurrences: Use a HashSet to store the counts of occurrences.
  3. Check uniqueness: If the size of the HashSet of occurrences is the same as the size of the HashMap of elements, it means all counts are unique.

Detailed Steps:

  1. Create a HashMap<Integer, Integer> to count the occurrences of each element in the array.
  2. Iterate through the array and update the counts in the HashMap.
  3. Create a HashSet<Integer> to store the values of these counts.
  4. Iterate through the values of the HashMap and add them to the HashSet.
  5. Compare the size of the HashMap and the HashSet. If they are equal, return true, else return false.

Code

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

public class UniqueNumberOccurrences {
    public boolean uniqueOccurrences(int[] arr) {
        // Step 1: Count occurrences
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int num : arr) {
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
        }
        
        // Step 2: Store counts in a HashSet
        HashSet<Integer> countSet = new HashSet<>();
        for (int count : countMap.values()) {
            countSet.add(count);
        }
        
        // Step 3: Check if countSet size is the same as countMap size
        return countSet.size() == countMap.size();
    }

    public static void main(String[] args) {
        UniqueNumberOccurrences solution = new UniqueNumberOccurrences();
        
        // Test case 1
        int[] arr1 = {1, 2, 2, 1, 1, 3};
        System.out.println(solution.uniqueOccurrences(arr1)); // true
        
        // Test case 2
        int[] arr2 = {1, 2};
        System.out.println(solution.uniqueOccurrences(arr2)); // false
        
        // Test case 3
        int[] arr3 = {-3, 0, 1, -3, 1, 1, 1, -3, 10, 0};
        System.out.println(solution.uniqueOccurrences(arr3)); // true
    }
}

Time Complexity

The time complexity of this approach is O(n), where n is the number of elements in the array. This is because:

  1. We pass through the array once to count occurrences, which is O(n).
  2. We then pass through the values of the HashMap to add the counts to the HashSet, which is also O(n).

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

The space complexity is O(n) due to the usage of the HashMap and the HashSet, which can both contain at most n elements in the worst case.

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