LeetCode Problem 1207

Difficulty: 🟢 Easy
Topics: Array, Hash Table

Solution

LeetCode 1207 - Unique Number of Occurrences

Problem Understanding

The problem gives us an integer array arr and asks whether every distinct number appears a unique number of times.

In other words, we first count how many times each value occurs in the array. After we have all the frequencies, we must verify that no two different values share the same frequency.

For example, consider:

arr = [1,2,2,1,1,3]

The frequencies are:

• 1 appears 3 times
• 2 appears 2 times
• 3 appears 1 time

Since the counts {3, 2, 1} are all different, the answer is true.

Now consider:

arr = [1,2]

Both 1 and 2 appear exactly once. Since two different values share the same occurrence count, the answer is false.

The input array can contain both positive and negative integers. The constraints are relatively small:

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

These limits tell us several important things:

• The array is small enough that even moderately inefficient solutions may pass.
• However, the intended solution should still use efficient counting techniques.
• Since values can repeat many times, frequency counting is the core operation.
• Negative numbers do not change the logic, because hash maps handle them naturally.

There are also several edge cases worth identifying early:

• Arrays where every value is unique, meaning every frequency is 1
• Arrays where all elements are identical
• Arrays containing negative values
• Arrays where two different numbers accidentally share the same count
• Arrays of length 1, which should always return true

The problem guarantees that the array is non-empty, so we never need to handle a completely empty input.

Approaches

Brute Force Approach

A brute force solution would manually count occurrences for every element by repeatedly scanning the array.

For each distinct value, we could:

1. Traverse the entire array to count how many times it appears.
2. Store that count.
3. Compare it against the counts of all previously processed values.

This approach is correct because every value's frequency is explicitly computed and compared. However, it performs many repeated scans of the array.

If there are n elements, and we repeatedly scan the array for counts, the total work can grow to O(n²).

Although n <= 1000 is small enough that this may still pass, it is inefficient and unnecessary.

Optimal Approach

The key observation is that we only need two pieces of information:

1. The frequency of each value
2. Whether any frequency appears more than once

A hash map is ideal for counting frequencies because it allows constant average time insertion and lookup.

Once we build the frequency map, we can place all frequency values into a hash set. Since a set only stores unique values, we can compare:

• the number of distinct elements
• the number of distinct frequencies

If these counts are equal, then every occurrence count is unique.

This reduces the solution to linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Repeatedly scans the array to count frequencies
Optimal	O(n)	O(n)	Uses a hash map for counting and a set for uniqueness checking

Algorithm Walkthrough

1. Create a hash map called frequency_map.

This map stores how many times each integer appears in the array. The key is the integer value, and the value is its occurrence count. 2. Traverse the array once.

For each number:

• If it already exists in the map, increment its count.
• Otherwise, initialize its count to 1.

After this step, the map contains the frequency of every distinct value. 3. Extract all frequency counts.

The values of the hash map represent the occurrence counts we care about. 4. Insert the frequencies into a hash set.

A set automatically removes duplicates. If two numbers have the same occurrence count, the set size becomes smaller than the number of map entries. 5. Compare sizes.

• If the number of frequencies in the set equals the number of keys in the map, all frequencies are unique.
• Otherwise, at least two values share the same frequency.

6. Return the result.

Why it works

The algorithm works because every distinct number contributes exactly one frequency count. A set only keeps unique values, so if two numbers share the same occurrence count, the duplicate frequency is collapsed into one set entry. Therefore:

• Equal sizes mean all frequencies are unique.
• Different sizes mean at least one frequency is duplicated.

This directly matches the problem requirement.

Python Solution

from typing import List

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

        for number in arr:
            frequency_map[number] = frequency_map.get(number, 0) + 1

        frequencies = set(frequency_map.values())

        return len(frequencies) == len(frequency_map)

The implementation begins by creating a dictionary called frequency_map. This dictionary stores how many times each number appears in the array.

The loop iterates through every element in arr. For each number, the count is updated using:

frequency_map.get(number, 0) + 1

This retrieves the current count if the number already exists, or uses 0 as the default value if it does not.

After counting is complete, the dictionary values are converted into a set:

frequencies = set(frequency_map.values())

Because sets only contain unique elements, duplicate occurrence counts are automatically removed.

Finally, the code compares:

len(frequencies) == len(frequency_map)

If these sizes match, every frequency was unique.

Go Solution

func uniqueOccurrences(arr []int) bool {
	frequencyMap := make(map[int]int)

	for _, number := range arr {
		frequencyMap[number]++
	}

	frequencySet := make(map[int]bool)

	for _, frequency := range frequencyMap {
		if frequencySet[frequency] {
			return false
		}

		frequencySet[frequency] = true
	}

	return true
}

The Go implementation follows the same logic as the Python version.

A map[int]int is used to count frequencies. Go automatically initializes missing integer map values to 0, so incrementing with:

frequencyMap[number]++

works naturally.

Instead of using a dedicated set type, Go simulates a set with:

map[int]bool

If a frequency already exists in the set map, the function immediately returns false.

Go does not require special handling for empty versus nil slices here because the problem guarantees at least one element. Integer overflow is also not a concern because the maximum frequency is only 1000.

Worked Examples

Example 1

arr = [1,2,2,1,1,3]

Step 1: Build Frequency Map

Current Number	Frequency Map
1	{1: 1}
2	{1: 1, 2: 1}
2	{1: 1, 2: 2}
1	{1: 2, 2: 2}
1	{1: 3, 2: 2}
3	{1: 3, 2: 2, 3: 1}

Step 2: Extract Frequencies

[3, 2, 1]

Step 3: Insert Into Set

{1, 2, 3}

Step 4: Compare Sizes

Structure	Size
Frequency Map	3
Frequency Set	3

Since the sizes match, return:

true

Example 2

arr = [1,2]

Step 1: Build Frequency Map

Current Number	Frequency Map
1	{1: 1}
2	{1: 1, 2: 1}

Step 2: Extract Frequencies

[1, 1]

Step 3: Insert Into Set

{1}

Step 4: Compare Sizes

Structure	Size
Frequency Map	2
Frequency Set	1

The sizes differ, so return:

false

Example 3

arr = [-3,0,1,-3,1,1,1,-3,10,0]

Step 1: Build Frequency Map

Number	Count
-3	3
0	2
1	4
10	1

Step 2: Frequencies

[3, 2, 4, 1]

Step 3: Convert to Set

{1, 2, 3, 4}

Step 4: Compare Sizes

Structure	Size
Frequency Map	4
Frequency Set	4

Return:

true

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	One pass to count frequencies and another pass over distinct values
Space	O(n)	Hash map and set may each store up to n distinct elements

The algorithm processes each element in the array exactly once while building the frequency map. The second phase iterates through the distinct values, which is at most n.

The extra memory comes from storing frequencies and unique counts in hash-based data structures.

Test Cases

solution = Solution()

assert solution.uniqueOccurrences([1, 2, 2, 1, 1, 3]) is True
# Standard example with unique frequencies

assert solution.uniqueOccurrences([1, 2]) is False
# Both numbers appear once

assert solution.uniqueOccurrences([-3, 0, 1, -3, 1, 1, 1, -3, 10, 0]) is True
# Includes negative numbers and multiple frequencies

assert solution.uniqueOccurrences([5]) is True
# Single element array

assert solution.uniqueOccurrences([7, 7, 7, 7]) is True
# Only one distinct number

assert solution.uniqueOccurrences([1, 1, 2, 2]) is False
# Two numbers share the same frequency

assert solution.uniqueOccurrences([1, 1, 1, 2, 2, 3]) is True
# Frequencies are 3, 2, and 1

assert solution.uniqueOccurrences([1, 1, 2, 2, 3, 3]) is False
# All frequencies are duplicated

assert solution.uniqueOccurrences([0, 0, 0, -1, -1, 2]) is True
# Mix of zero, negative, and positive values

assert solution.uniqueOccurrences(list(range(1000))) is False
# Every number appears once

Test Case Summary

Test	Why
[1,2,2,1,1,3]	Standard valid example
[1,2]	Detects duplicate frequency counts
[-3,0,1,-3,1,1,1,-3,10,0]	Verifies negative numbers work correctly
[5]	Smallest valid input size
[7,7,7,7]	Single distinct value
[1,1,2,2]	Two values share frequency 2
[1,1,1,2,2,3]	Frequencies are all unique
[1,1,2,2,3,3]	Multiple duplicated frequencies
[0,0,0,-1,-1,2]	Mixed integer values
list(range(1000))	Large input where all frequencies are 1

Edge Cases

One important edge case is an array containing only one element. In this situation, there is only one frequency, which is automatically unique. A careless implementation might overcomplicate the logic or incorrectly assume at least two distinct values exist. The current solution handles this naturally because both the map and set contain exactly one entry.

Another important case is when every number appears exactly once. For example:

[1,2,3,4]

All frequencies become 1, meaning the set only contains one value while the map contains four keys. Some incorrect implementations only check adjacent values or forget to verify duplicates globally. Using a set guarantees all duplicate frequencies are detected.

A third edge case involves negative numbers and zero. Since array values range from -1000 to 1000, the implementation must correctly count negative integers as hash map keys. Both Python dictionaries and Go maps fully support negative integer keys, so no additional logic is required.

A final subtle case occurs when many different numbers share the same frequency. For example:

[1,1,2,2,3,3]

Every value appears twice. A naive implementation might stop checking too early or fail to compare all counts. The set-based approach immediately reveals the issue because all three frequencies collapse into a single set value.