Unique Number of Occurrences

EASY

Description

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

Approaches

Checkout 3 different approaches to solve Unique Number of Occurrences. Click on different approaches to view the approach and algorithm in detail.

Sorting-Based Approach

This approach relies on sorting to solve the problem. First, the input array is sorted, which conveniently groups all identical numbers next to each other. Then, a single pass through the sorted array is enough to count the occurrences of each unique number. These counts are stored in a separate list. To check if the counts themselves are unique, this list of counts is also sorted. A final pass over the sorted counts list can easily reveal any duplicates by checking adjacent elements. If any duplicates are found, the function returns false; otherwise, it returns true.

Algorithm

Sort the input array arr to group identical elements together.
Initialize an empty list, counts, to store the frequency of each unique number.
Iterate through the sorted array. For each unique number, count its occurrences and add the count to the counts list.
After populating the counts list, sort it as well.
Iterate through the sorted counts list. If any two adjacent elements are identical, it means a frequency is not unique, so return false.
If the entire counts list is traversed without finding duplicates, return true.

The core idea is to transform the problem of checking unique occurrences into a simpler problem of checking for duplicates in a sorted list. By sorting the initial array, we can easily compute the frequencies. By sorting the list of frequencies, we can easily check for uniqueness.

Algorithm Steps:

Sort the input array arr.
Initialize an ArrayList<Integer> named counts.
Iterate through the sorted arr using an index i.
Inside the loop, count the occurrences of the current element arr[i] by checking the subsequent elements.
Add the final count to the counts list.
Advance the index i past the block of identical elements.
After the loop, sort the counts list.
Iterate through the sorted counts list from the first element to the second-to-last element.
In each iteration, compare counts.get(j) with counts.get(j + 1). If they are equal, return false.
If the loop completes, it means no two frequencies were the same, so return true.

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

class Solution {
    public boolean uniqueOccurrences(int[] arr) {
        Arrays.sort(arr);
        List<Integer> counts = new ArrayList<>();
        int i = 0;
        while (i < arr.length) {
            int count = 1;
            while (i + 1 < arr.length && arr[i] == arr[i + 1]) {
                count++;
                i++;
            }
            counts.add(count);
            i++;
        }

        Collections.sort(counts);
        for (int j = 0; j < counts.size() - 1; j++) {
            if (counts.get(j).equals(counts.get(j + 1))) {
                return false;
            }
        }
        return true;
    }
}

Complexity Analysis

Time Complexity: O(N log N), where N is the number of elements in the array. The initial sort of the array dominates the time complexity. Counting frequencies takes O(N), and sorting the frequencies takes O(K log K), where K <= N.Space Complexity: O(K), where K is the number of unique elements in `arr`. In the worst case (all elements are unique), the space complexity is O(N) to store the counts. Sorting algorithms might also use O(log N) to O(N) auxiliary space depending on the implementation.

Pros and Cons

Pros:

The logic is straightforward and relies on the fundamental concept of sorting.
It does not require complex data structures like hash maps.

Cons:

The time complexity of O(N log N) is suboptimal compared to other approaches.
It requires modifying the input array by sorting it, or using extra space to store a sorted copy.
It involves multiple traversals and sorting operations, making it more complex to implement correctly.

Code Solutions

Checking out 3 solutions in different languages for Unique Number of Occurrences. Click on different languages to view the code.

class Solution {
public
  boolean uniqueOccurrences(int[] arr) {
    Map<Integer, Integer> cnt = new HashMap<>();
    for (int x : arr) {
      cnt.merge(x, 1, Integer : : sum);
    }
    return new HashSet<>(cnt.values()).size() == cnt.size();
  }
}

Video Solution

Watch the video walkthrough for Unique Number of Occurrences

Data Structures:

ArrayHash Table

Companies:

Datadog |