1207. Unique Number of Occurrences

LeetCode Problem Link (opens new window)

You are given an integer array arr. Help to count the occurrences of each number in the array.

If the occurrences of each number are unique, return true. Otherwise, return false.

Example 1:

• Input: arr = [1,2,2,1,1,3]
• Output: true
• Explanation: In this array, 1 occurs 3 times, 2 occurs 2 times, and 3 occurs 1 time. No two numbers have the same count.

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

Approach

This problem is a classic application of the Hashing technique on arrays. If you are unfamiliar with the use of arrays in hashing, you can refer to these articles: 0242.Valid Anagram (opens new window) and 0383.Ransom Note (opens new window)

You can further understand the use of set in hashing by reading 0349.Intersection of Two Arrays (opens new window), and the use of map by reading 0001.Two Sum (opens new window)

Returning to this problem, since the problem constrains -1000 <= arr[i] <= 1000, we can use an array for hashing, taking arr[i] as the index of the hash table (array). But what if arr[i] is negative since negative numbers cannot be used as array indexes?

Here, we can define an array of size 2001, for example int count[2001];, and when counting, add 1000 to all arr[i], so we can track the frequency of arr[i].

The problem requires checking if there are duplicate frequencies, so we need to define another hash table (array) to record if a frequency has appeared before, bool fre[1001]; A boolean type is sufficient here because the problem constrains 1 <= arr.length <= 1000, so the size of the hash table should be 1000.

As shown in the diagram:

The C++ code is as follows:

class Solution {
public:
    bool uniqueOccurrences(vector<int>& arr) {
        int count[2001] = {0}; // Count the frequency of numbers
        for (int i = 0; i < arr.size(); i++) {
            count[arr[i] + 1000]++;
        }
        bool fre[1001] = {false}; // Check if the same frequency appeared
        for (int i = 0; i <= 2000; i++) {
            if (count[i]) {
                if (fre[count[i]] == false) fre[count[i]] = true;
                else return false;
            }
        }
        return true;
    }
};

Other Language Versions

Java:

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        int[] count = new int[2001];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] + 1000]++; // Prevent negative numbers as indexes
        }
        boolean[] flag = new boolean[1002]; // Mark if the same frequency has appeared
        for (int i = 0; i <= 2000; i++) {
            if (count[i] > 0) {
                if (flag[count[i]] == false) {
                    flag[count[i]] = true;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
}

Python:

Using Arrays for Hashing Method 1:

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        count = [0] * 2001
        for i in range(len(arr)):
            count[arr[i] + 1000] += 1 # Prevent negative numbers as indexes
        freq = [False] * 1001 # Mark if the same frequency has appeared
        for i in range(2001):
            if count[i] > 0:
                if freq[count[i]] == False:
                    freq[count[i]] = True
                else:
                    return False
        return True

Using Map for Hashing Method 2:

class Solution:
    def uniqueOccurrences(self, arr: List[int]) -> bool:
        ref = dict()

        for i in range(len(arr)):
            ref[arr[i]] = ref.get(arr[i], 0) + 1

        value_list = sorted(ref.values())

        for i in range(len(value_list) - 1):
            if value_list[i + 1] == value_list[i]:
                return False 

        return True 

JavaScript:

Method 1: Using Arrays

var uniqueOccurrences = function(arr) {
    const count = new Array(2001).fill(0); // -1000 <= arr[i] <= 1000
    for(let i = 0; i < arr.length; i++) {
        count[arr[i] + 1000]++; // Prevent negative numbers as indexes
    }
    const fre = new Array(1001).fill(false); // Mark if the same frequency has appeared
    for(let i = 0; i <= 2000; i++) {
        if(count[i] > 0) {
            if(fre[count[i]] === false) fre[count[i]] = true; 
            else return false; 
        }
    }
    return true;
};

// Method 2: Using Map and Set
var uniqueOccurrences = function(arr) {
    let map = new Map();
    arr.forEach(x => {
        map.set(x, (map.get(x) || 0) + 1); 
    })
    return map.size === new Set(map.values()).size;
};

TypeScript:

Using Arrays:

function uniqueOccurrences(arr: number[]): boolean {
    const countArr: number[] = new Array(2001).fill(0);
    for (let i = 0, length = arr.length; i < length; i++) {
        countArr[arr[i] + 1000]++;
    }
    const flagArr: boolean[] = new Array(1001).fill(false);
    for (let count of countArr) {
        if (count === 0) continue;
        if (flagArr[count] === true) return false;
        flagArr[count] = true;
    }
    return true;
};

Using Map and Set:

function uniqueOccurrences(arr: number[]): boolean {
    const countMap: Map<number, number> = new Map();
    arr.forEach(val => {
        countMap.set(val, (countMap.get(val) || 0) + 1);
    })
    return countMap.size === new Set(countMap.values()).size;
};

Go:

func uniqueOccurrences(arr []int) bool {
    count := make(map[int]int) // Count the frequency of numbers
    for _, v := range arr {
        count[v] += 1
    }
    fre := make(map[int]struct{}) // Check if the same frequency appeared
    for _, v := range count {
        if _, ok := fre[v]; ok {
            return false
        }
        fre[v] = struct{}{}
    }
    return true
}

Rust

use std::collections::{HashMap, HashSet};
impl Solution {
    pub fn unique_occurrences(arr: Vec<i32>) -> bool {
        let mut hash = HashMap::<i32, i32>::new();
        for x in arr {
            *hash.entry(x).or_insert(0) += 1;
        }
        let mut set = HashSet::<i32>::new();
        for (_k, v) in hash {
            if set.contains(&v) {
                return false
            } else {
                set.insert(v);
            }
        }
        true
    }
}