Unique Number of Occurrences: Coding Interview Problem - Data Structures and Algorithms (DSA) Guide

Problem Statement

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

Example

For the array arr = [1,2,2,1,1,3], the number of occurrences are: 1 appears 3 times, 2 appears 2 times, and 3 appears 1 time. Since these frequencies (3, 2, 1) are unique, the answer is true.

Intuition

Imagine you’re counting items in different baskets. For this scenario to be true, no two baskets can have the same count of items. If they do, then the condition isn’t met.

Think of the array elements as items that you’re placing into baskets. Each unique item has its own basket, and you’re counting how many are in each basket. To satisfy the problem’s conditions, each basket’s item count should be distinct.

Brute Force Solution

One simple approach is to use two hash maps. The first counts the occurrences of each number, and the second tracks the frequencies of these occurrences. If any frequency is more than 1, return false.

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

public class UniqueOccurrencesChecker {
    public static void main(String[] args) {
        int[] arr = {1, 2, 2, 1, 1, 3};
        System.out.println(uniqueOccurrencesBruteForce(arr)); // Output should be true
    }

    public static boolean uniqueOccurrencesBruteForce(int[] arr) {
        // Create a map to hold the count of occurrences of each number
        Map<Integer, Integer> count = new HashMap<>();
        
        // Count occurrences of each number in the array
        for (int num : arr) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        // Create another map to track the frequencies of occurrences
        Map<Integer, Integer> frequency = new HashMap<>();
        
        // For each occurrence count, check if it has appeared before
        for (int occ : count.values()) {
            // If the frequency of an occurrence count is found to be more than 1, return false
            if (frequency.put(occ, frequency.getOrDefault(occ, 0) + 1) != null) {
                return false;
            }
        }

        // If no repeated frequencies were found, return true
        return true;
    }
}

The time complexity of this approach is O(n), but we’re using extra space to store the count and frequencies.

Optimal Solution

Instead of using two hash maps, we can use a single hash map to count occurrences and then use a hash set to check for unique frequencies.

Since sets only store unique values, any repetition will indicate a non-unique frequency.

Approach:

Count the occurrences of each number in the array using a hash map.
Insert these occurrences into a hash set. If the size of the set matches the size of the hash map, it means each frequency was unique.

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class UniqueOccurrencesChecker {
    public static boolean uniqueOccurrencesOptimal(int[] arr) {
        // Create a map to hold the count of occurrences of each number
        Map<Integer, Integer> count = new HashMap<>();
        
        // Count occurrences of each number in the array
        for (int num : arr) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }

        // Create a set to store unique occurrence counts
        Set<Integer> uniqueFrequencies = new HashSet<>(count.values());

        // If the number of unique occurrence counts equals the number of unique numbers, 
        // then each number had a unique occurrence count
        return uniqueFrequencies.size() == count.size();
    }
}