1207. Unique Number of Occurrences

Description of Problem

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique or false otherwise.

Example 1:

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

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

Solution

Code (Rust)

impl Solution {
    pub fn unique_occurrences(arr: Vec<i32>) -> bool {
        use std::collections::HashMap;
        use std::collections::HashSet;
        let mut counting = HashMap::new();

        for a in arr.into_iter() {
            if let Some(x) = counting.get_mut(&a) {
                *x += 1;
            }else{
                counting.insert(a, 1);
            }
        }

        let vec: Vec<i32> = counting.into_values().collect();
        let m = vec.len();
        let set: HashSet<i32> = vec.into_iter().collect();
        let n = set.len();

        m == n
    }
}

Complexity

• n is length of arr
• Assume HashMap query costs constant time

Time Complexity

• \(T(n) = \Theta(3n) = \Theta(n) \)
  1. arr into HashMap
  2. arr into Vector
  3. arr into Set

Auxiliary Space

• \(S(n) = O(2n) = O(n) \)
  • Vector and HashSet