Solution For Unique Number Of Occurrences

Problem Statement:

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

Input:
– An array of integers, arr.

Output:
– Return true if and only if the number of occurrences of each value in the array is unique, else return false.

Example:
Input: arr = [1, 2, 2, 1, 1, 3] Output: true
Explanation:
– The occurrences of 1 is 3, which is unique.
– The occurrences of 2 is 2, which is unique.
– The occurrences of 3 is 1, which is unique.

Solution:

We can solve the problem by using some data structures such as hash tables and sets.

• We initialize an empty hash table (dictionary) called count.
• We iterate over each element in the input array arr.
  • For each element, we increment its count in the hash table. If the element is not present, we add it to the hash table with count 1.
• We initialize an empty set called counts_set.
• We iterate over the values in count hash table.
  • For each count, we add it to the counts_set. If the count is already present in counts_set, we return false since it means there are two or more values with the same count.
• If we have iterated over all the values in count hash table and have not returned false, we can safely return true since we have found unique counts for all values.

Pseudo-code:

def uniqueOccurrences(arr: List[int]) -> bool:
count = {}
counts_set = set()

for val in arr:
    if val not in count:
        count[val] = 1
    else:
        count[val] += 1

for val_count in count.values():
    if val_count in counts_set:
        return False
    else:
        counts_set.add(val_count)

return True

Time Complexity:

The time complexity of the above solution is O(n), where n is the length of the input array arr. This is because we iterate over the input array only once and also iterate over the values in count hash table only once.

Space Complexity:

The space complexity of the above solution is O(n), where n is the length of the input array arr. This is because we could potentially store all values of the input array arr in the count hash table.

Step by Step Implementation For Unique Number Of Occurrences

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

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        Map map = new HashMap<>(); 
        
        for (int i : arr) {
            map.put(i, map.getOrDefault(i, 0) + 1); 
        }
        
        return map.size() == new HashSet<>(map.values()).size(); 
    }
}

def uniqueOccurrences(arr):
    
    # create a dictionary to store the number of occurrences for each element
    num_occurrences = {}
    
    # iterate through the array and update the dictionary
    for num in arr:
        if num in num_occurrences:
            num_occurrences[num] += 1
        else:
            num_occurrences[num] = 1
    
    # get a list of the values in the dictionary
    occurrences = list(num_occurrences.values())
    
    # return True if there are no duplicate values, False otherwise
    return len(occurrences) == len(set(occurrences))

var uniqueOccurrences = function(arr) {
    // create a hashmap to store the number of occurrences for each number
    let map = {};
    
    // iterate over the input array
    for (let i = 0; i < arr.length; i++) {
        // if the number is not in the map, set its value to 1
        if (!(arr[i] in map)) {
            map[arr[i]] = 1;
        } else { // otherwise, increment its value
            map[arr[i]]++;
        }
    }
    
    // create a set to store the unique values
    let set = new Set();
    
    // iterate over the map keys
    for (let key in map) {
        // if the value is not in the set, add it
        if (!set.has(map[key])) {
            set.add(map[key]);
        } else { // otherwise, return false
            return false;
        }
    }
    
    // if we get to this point, all values in the map are unique, so return true
    return true;
};

class Solution {
public:
    bool uniqueOccurrences(vector& arr) {
        
        // Create a map to store the number of occurrences of each number
        map num_occurrences;
        
        // Iterate through the array and update the map
        for (int num : arr) {
            num_occurrences[num]++;
        }
        
        // Create a set to store the number of occurrences
        // A set will only allow unique values, so we can use it
        // to check if the number of occurrences is unique
        set occurrences;
        
        // Iterate through the map and update the set
        for (auto it = num_occurrences.begin(); it != num_occurrences.end(); it++) {
            occurrences.insert(it->second);
        }
        
        // Return whether the set's size is the same as the map's size
        // If so, then the number of occurrences must be unique
        return occurrences.size() == num_occurrences.size();
    }
};

public class Solution {
    public bool UniqueOccurrences(int[] arr) {
        // create a dictionary to store the number of occurrences for each number
        Dictionary dict = new Dictionary();
        
        // iterate through the array and add each number to the dictionary
        foreach(int num in arr) {
            if(!dict.ContainsKey(num)) {
                dict.Add(num, 1);
            }
            else {
                dict[num]++;
            }
        }
        
        // create a hashset to store the occurrences
        HashSet set = new HashSet();
        
        // iterate through the dictionary and add each occurrence to the hashset
        foreach(int key in dict.Keys) {
            if(!set.Contains(dict[key])) {
                set.Add(dict[key]);
            }
            else {
                return false;
            }
        }
        
        return true;
    }
}