Scale Engineer

Unique Number of Occurrences

Easy
#1128Time: 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: 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.1 company
Data structures
ArrayHash Table
Companies
Datadog

Prompt

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

3 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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:

  1. Sort the input array arr.
  2. Initialize an ArrayList<Integer> named counts.
  3. Iterate through the sorted arr using an index i.
  4. Inside the loop, count the occurrences of the current element arr[i] by checking the subsequent elements.
  5. Add the final count to the counts list.
  6. Advance the index i past the block of identical elements.
  7. After the loop, sort the counts list.
  8. Iterate through the sorted counts list from the first element to the second-to-last element.
  9. In each iteration, compare counts.get(j) with counts.get(j + 1). If they are equal, return false.
  10. 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

Time

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

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.

Trade-offs

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.

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem