Problem Description

You are given an integer array nums. Your task is to find the largest integer in the array that appears exactly once. If there is no integer that appears exactly once in the array, you should return -1.

For example:

• If nums = [5, 7, 3, 9, 4, 9, 8, 3, 1], the numbers that appear once are 5, 7, 4, 8, 1. Among these, 8 is the largest, so you would return 8.
• If nums = [9, 9, 8, 8], no number appears exactly once, so you would return -1.

The solution uses a Counter to count the frequency of each number in the array. It then filters out all numbers that appear exactly once (where count equals 1) and returns the maximum among them. If no such number exists, the default=-1 parameter ensures that -1 is returned.

Intuition

To find the largest number that appears exactly once, we need to know two things about each number in the array: how many times it appears, and what its value is. This naturally leads us to think about counting frequencies.

The key insight is that we need to:

1. Count how many times each number appears
2. Filter out only those numbers that appear exactly once
3. Find the maximum among these unique numbers

Since we're looking for the maximum value among numbers with a specific property (appearing exactly once), we can approach this by first organizing our data to identify which numbers meet our criteria, then selecting the largest one.

Using a frequency counter like Counter gives us a clean way to map each number to its occurrence count. Once we have this mapping, we can iterate through it and consider only those entries where the count is 1. Among all such numbers, we want the maximum value.

The elegance of this approach is that it handles both requirements simultaneously - checking uniqueness and finding the maximum - in a single pass through the counter. If no numbers appear exactly once, we need to return -1, which is handled by the default parameter in the max function.

Learn more about Sorting patterns.

Solution Approach

The solution uses a counting approach to track the frequency of each number in the array. Here's how the implementation works:

1. Count Frequencies: We use Python's Counter from the collections module to count how many times each number appears in the array. This creates a dictionary-like object where keys are the numbers and values are their counts.

   cnt = Counter(nums)

2. Filter and Find Maximum: We use a generator expression to iterate through all items in the counter, filtering only those numbers whose count equals 1. The max function then finds the largest among these unique numbers.

   return max((x for x, v in cnt.items() if v == 1), default=-1)

   • cnt.items() gives us pairs of (number, count)
   • if v == 1 filters only numbers that appear exactly once
   • x for x, v extracts just the numbers (not their counts)
   • max() finds the largest value among these filtered numbers
   • default=-1 ensures we return -1 if no number appears exactly once

The reference approach mentions an alternative using an array of length 1001 for counting, which would work if we know the data range is limited (e.g., numbers between 0 and 1000). This array-based approach would:

• Use indices to represent numbers and values to represent counts
• Traverse the array in reverse order (from largest to smallest index)
• Return the first index where the count equals 1

Both approaches achieve the same result with time complexity of O(n) where n is the length of the input array. The Counter approach is more general and handles any integer range, while the array approach can be more efficient for limited ranges.

Example Walkthrough

Let's walk through the solution with a small example: nums = [4, 3, 2, 3, 1, 2]

Step 1: Count Frequencies First, we count how many times each number appears:

• Number 1 appears 1 time
• Number 2 appears 2 times
• Number 3 appears 2 times
• Number 4 appears 1 time

Using Counter(nums), we get: {4: 1, 3: 2, 2: 2, 1: 1}

Step 2: Filter Numbers Appearing Once We iterate through the counter and identify numbers with count = 1:

• Number 4: count is 1 ✓ (include)
• Number 3: count is 2 ✗ (exclude)
• Number 2: count is 2 ✗ (exclude)
• Number 1: count is 1 ✓ (include)

So our filtered list of unique numbers is: [4, 1]

Step 3: Find Maximum Among the numbers that appear exactly once (4 and 1), we find the maximum:

• max([4, 1]) = 4

Therefore, we return 4.

Edge Case Example: If nums = [5, 5, 3, 3], after counting we get {5: 2, 3: 2}. No number has count = 1, so the generator expression produces an empty sequence. The default=-1 parameter ensures we return -1 in this case.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the input array nums. This consists of:

• O(n) to build the Counter dictionary by iterating through all elements in nums
• O(n) in the worst case for the max function to iterate through all unique elements in the Counter (at most n elements)

The space complexity is O(M), where M is the number of unique elements in the array. The Counter dictionary stores each unique element as a key with its frequency as the value. In the worst case where all elements are unique, M = n. However, given the problem constraint that values are bounded (typically M ≤ 1000 for this LeetCode problem), the space complexity can also be expressed as O(min(n, M)) or simply O(M) when M is a constant upper bound.

Note: The reference answer mentions O(n + M) for time complexity, which could be interpreted as accounting for both the iteration through the array (n) and potential operations dependent on the range of values (M), but since we're using a hash-based Counter, the time complexity is more accurately O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Forgetting to Handle Empty Sequences in max()

One of the most common mistakes is using max() on a potentially empty sequence without the default parameter:

Incorrect Code:

def largestUniqueNumber(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    # This will raise ValueError if no unique numbers exist!
    return max(num for num, freq in frequency_map.items() if freq == 1)

Problem: When no numbers appear exactly once (e.g., nums = [9, 9, 8, 8]), the generator expression produces an empty sequence, causing max() to raise a ValueError: max() arg is an empty sequence.

Solution: Always include the default parameter when the sequence might be empty:

return max((num for num, freq in frequency_map.items() if freq == 1), default=-1)

2. Inefficient Double-Pass Approach

Some might attempt to first collect all unique numbers, then find the maximum in a separate step:

Inefficient Code:

def largestUniqueNumber(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    unique_nums = [num for num, freq in frequency_map.items() if freq == 1]
    return max(unique_nums) if unique_nums else -1

Problem: This creates an unnecessary intermediate list, using extra memory and requiring two passes over the filtered data.

Solution: Use a generator expression with max() directly to process in a single pass without creating an intermediate list.

3. Manual Maximum Tracking with Incorrect Initialization

When manually tracking the maximum unique number, incorrect initialization can lead to bugs:

Incorrect Code:

def largestUniqueNumber(self, nums: List[int]) -> int:
    frequency_map = Counter(nums)
    max_unique = 0  # Wrong initialization!
    for num, freq in frequency_map.items():
        if freq == 1:
            max_unique = max(max_unique, num)
    return max_unique if max_unique != 0 else -1

Problem: If all unique numbers are negative (e.g., nums = [-1, -2, -2, -3]), this would incorrectly return 0 instead of -1.

Solution: Initialize with negative infinity or track whether any unique number was found:

max_unique = float('-inf')
found_unique = False
for num, freq in frequency_map.items():
    if freq == 1:
        max_unique = max(max_unique, num)
        found_unique = True
return max_unique if found_unique else -1