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) { Mapmap = 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 Dictionarydict = 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; } }