Difficulty: Easy
Category: Array, Hash Table
Companies: Amazon, Google, Microsoft

Given an array of integers arr, return true if the number of occurrences of each value in the array is unique, or false otherwise.

Examples

Example 1:

Input: arr = [1,2,2,1,1,3]
Output: true
Explanation: The value 1 has 3 occurrences, 2 has 2 occurrences, and 3 has 1 occurrence. No two values have the same number of occurrences.

Example 2:

Input: arr = [1,2]
Output: false
Explanation: The value 1 has 1 occurrence, and 2 has 1 occurrence. Two values have the same number of occurrences.

Example 3:

Input: arr = [-3,0,1,-3,1,1,1,-3,10,0]
Output: true
Explanation: The value -3 has 3 occurrences, 0 has 2 occurrences, 1 has 4 occurrences, and 10 has 1 occurrence. No two values have the same number of occurrences.

Constraints

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

Solution Approaches

Approach 1: Hash Map + Hash Set (Recommended)

Algorithm:

  1. Count frequency of each element using hash map
  2. Store all frequencies in a hash set
  3. Check if hash set size equals hash map size (no duplicate frequencies)

Time Complexity: O(n)
Space Complexity: O(n)

class Solution:
    def uniqueOccurrences(self, arr: list[int]) -> bool:
        freqs = {}

        for num in arr:
            freqs[num] = freqs.get(num, 0) + 1

        occurs = set(freqs.values())
        return len(occurs) == len(freqs)

Solution Explanation

Approach: Prefix sum (this problem)

Key idea: Difficulty:** Easy

How the code works: Difficulty: Easy Category: Array, Hash Table

  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.

Walkthrough — input arr = [1,2,2,1,1,3], expected output true:

The value 1 has 3 occurrences, 2 has 2 occurrences, and 3 has 1 occurrence. No two values have the same number of occurrences.

Implementation Details

Hash Set Insert Behavior

class Solution:
    def uniqueOccurrences(self, arr: list[int]) -> bool:
        freqs = {}

        for num in arr:
            freqs[num] = freqs.get(num, 0) + 1

        occurs = set()
        for freq in freqs.values():
            if freq in occurs:
                return False
            occurs.add(freq)

        return True

Array Offset Technique

class Solution:
    def uniqueOccurrences(self, arr: list[int]) -> bool:
        freq = [0] * 2001  # for values [-1000, 1000]

        for num in arr:
            freq[num + 1000] += 1

        seen = [0] * 1001  # frequency range

        for f in freq:
            if f > 0:
                if seen[f] > 0:
                    return False
                seen[f] = 1

        return True

Edge Cases

  1. Single Element: [1] → true (frequency 1 is unique)
  2. All Same Elements: [1,1,1] → true (frequency 3 is unique)
  3. All Different Elements: [1,2,3] → true (all frequencies are 1)
  4. Duplicate Frequencies: [1,2,2,3] → false (both 1 and 3 have frequency 1)

Follow-up Questions

  • What if the array could contain very large numbers?
  • How would you handle floating-point numbers?
  • What if you needed to find which frequencies are duplicated?
  • How would you optimize for very large arrays?

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Optimization Techniques

  1. Early Termination: Stop as soon as duplicate frequency is found
  2. Space Optimization: Use arrays instead of hash maps for small ranges
  3. Memory Efficiency: Avoid storing unnecessary data
  4. Cache Performance: Array-based approach has better cache locality

Code Quality Notes

  1. Readability: First approach is most readable and maintainable
  2. Performance: Array approach is fastest for small ranges
  3. Scalability: Hash map approach works for any range
  4. Robustness: All approaches handle edge cases correctly

Key Takeaways

  • Pattern: Prefix sum (this problem)
  • Difficulty:** Easy
  • Category:** Array, Hash Table

References

Template Reference

Thinking Process

Difficulty: Easy

Category: Array, Hash Table

  • Clarify if the array is sorted, has negatives, or allows duplicates.
  • Prefix sums answer range queries; hash maps answer pair/count queries.
  • In-place tricks use swap/write index instead of extra arrays.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Prefix sum (this problem) O(n) O(n) Range queries, subarray sum
Sort + scan O(n log n) O(1) Intervals, meeting rooms
Kadane’s algorithm O(n) O(1) Maximum subarray
Hash map counting O(n) O(n) Frequency, two-sum variants