Leetcode 1207: Unique Number of Occurrences

Category: Easy

Problem

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.

https://leetcode.com/problems/unique-number-of-occurrences/

Examples:

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.

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

1 2	Input: arr = [1,2] Output: false

Example 3

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true

1 2	Input: arr = [-3,0,1,-3,1,1,1,-3,10,0] Output: true

Constraints:

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

Solution Approach

In this problem, we need to find if the numbers in the array given have a unique number of occurrence or not. That is we need to find if we encounter the number and keep a count of that, the count should be unique.

To do the same we can make use of set and map in java. A set is a type of collection which only hold unique element and rejects all the element which it encounters the second time. So that will be a good way to store the occurrence of a number. A map on the other hand stores key-value pairs where each key is unique. So that can be used to store the mapping between the number and its occurrence.

Now coming to the solution, we iterate through the array and store its element and its occurrence in a map using get and getOrDefault methods of the HashMap in Java. Then we create a set and store the value of the key-value pair of the map in it. If in case we encounter the key whose value is the same and already present in the set then we straightaway return false. In the end, if that is not the case for all the elements in the map, we return true.

Solution Code

class Solution {
  public boolean uniqueOccurrences(int[] arr) {
    HashMap<Integer, Integer> map = new HashMap<>();
    for (int i=0; i<arr.length; i++){
      map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);
    }
    
    HashSet<Integer> set = new HashSet<>();
    for(Integer key: map.keySet()){
      if(set.contains(map.get(key))) return false;
      set.add(map.get(key));
    }
    return true;
  }
}

class Solution {

public boolean uniqueOccurrences(int[] arr) {

HashMap<Integer, Integer> map = new HashMap<>();

for (int i=0; i<arr.length; i++){

map.put(arr[i], map.getOrDefault(arr[i], 0) + 1);

}

HashSet<Integer> set = new HashSet<>();

for(Integer key: map.keySet()){

if(set.contains(map.get(key))) return false;

set.add(map.get(key));

}

return true;

}

For more Leetcode explained solutions visit Leetcode Solutions. If you like capture the flag challenges visit here.

Check out my socials below in the footer. Feel free to ask any doubts in the comment section or contact me via Contact page I will surely respond. Happy Leetcoding 🙂