LeetCode 1133 - Largest Unique Number

The problem is asking us to identify the largest integer in an array that occurs exactly once. In other words, among all integers that are unique (appear only one time), we need to find the maximum. If no such integer exists, the output should be -1.

leetcodeeasyarrayhash-tablesorting

LeetCode Problem 1133

Difficulty: 🟢 Easy
Topics: Array, Hash Table, Sorting

Solution

Problem Understanding

The problem is asking us to identify the largest integer in an array that occurs exactly once. In other words, among all integers that are unique (appear only one time), we need to find the maximum. If no such integer exists, the output should be -1. The input nums is a list of integers, each ranging from 0 to 1000, and the array length can go up to 2000. This tells us that the input size is relatively small, so algorithms with O(n log n) or even O(n^2) time could be acceptable, but an O(n) solution using extra space is likely better and more elegant.

Important edge cases include arrays where all elements are repeated (return -1), arrays with only one element (return that element), and arrays where the largest element itself is repeated, so we must carefully check uniqueness rather than simply picking the max.

Approaches

The brute-force approach would iterate through the array, and for each element, count how many times it occurs in the array. Then we would track the largest element that occurs exactly once. While correct, this approach requires scanning the entire array for every element, resulting in O(n^2) time complexity, which is inefficient for larger arrays.

The optimal approach uses a hash map to count the occurrences of each number. Once we have the counts, we can iterate over the hash map to find the maximum number with a count of exactly one. This approach leverages the fact that we can efficiently track counts in O(n) time and space. It is simple, readable, and fast for the given constraints.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Count occurrences for each number individually
Optimal O(n) O(n) Use a hash map to count occurrences, then find max unique

Algorithm Walkthrough

  1. Initialize an empty hash map (dictionary in Python, map in Go) to store the counts of each integer in the array.
  2. Iterate over the array, and for each number, increment its count in the hash map. This ensures that every number has its frequency tracked efficiently.
  3. Initialize a variable largest_unique to -1 to store the largest unique number found.
  4. Iterate through the hash map entries. For each number with a count of exactly one, compare it with largest_unique. If it is larger, update largest_unique.
  5. After processing all entries, return largest_unique. If no number occurred exactly once, the variable remains -1, which correctly handles that case.

Why it works: The algorithm works because the hash map guarantees that every number's occurrence is counted accurately. By iterating over the map and considering only numbers with count one, we ensure that we only evaluate unique numbers. The maximum among these numbers is therefore the largest unique number.

Python Solution

from typing import List

class Solution:
    def largestUniqueNumber(self, nums: List[int]) -> int:
        count_map = {}
        for num in nums:
            count_map[num] = count_map.get(num, 0) + 1
        
        largest_unique = -1
        for num, count in count_map.items():
            if count == 1 and num > largest_unique:
                largest_unique = num
                
        return largest_unique

This Python solution first counts all numbers using a dictionary. The get method provides a default value of 0 if the key does not exist, simplifying the increment operation. Then it scans through all key-value pairs, checking for uniqueness and keeping track of the largest number found. This directly implements the algorithm outlined above.

Go Solution

func largestUniqueNumber(nums []int) int {
    countMap := make(map[int]int)
    for _, num := range nums {
        countMap[num]++
    }
    
    largestUnique := -1
    for num, count := range countMap {
        if count == 1 && num > largestUnique {
            largestUnique = num
        }
    }
    
    return largestUnique
}

In Go, we use a map to count occurrences. The increment operation countMap[num]++ automatically handles initialization for missing keys. The logic to find the largest unique number is identical to the Python version. Go does not require type hints for map values because the map declaration specifies it.

Worked Examples

Example 1: nums = [5,7,3,9,4,9,8,3,1]

  1. Count occurrences: {5:1,7:1,3:2,9:2,4:1,8:1,1:1}
  2. Check unique numbers: [5,7,4,8,1]
  3. Find maximum among them: 8
  4. Output: 8

Example 2: nums = [9,9,8,8]

  1. Count occurrences: {9:2,8:2}
  2. No unique numbers
  3. Output: -1

Complexity Analysis

Measure Complexity Explanation
Time O(n) Count occurrences in O(n), then iterate over the map in O(n)
Space O(n) Hash map stores up to n keys in the worst case

Using a hash map ensures we only scan the input twice: once for counting and once for finding the maximum, giving linear time complexity.

Test Cases

# Provided examples
assert Solution().largestUniqueNumber([5,7,3,9,4,9,8,3,1]) == 8  # example 1
assert Solution().largestUniqueNumber([9,9,8,8]) == -1  # example 2

# Single element array
assert Solution().largestUniqueNumber([42]) == 42  # only one number, must return it

# All unique numbers
assert Solution().largestUniqueNumber([1,2,3,4,5]) == 5  # largest unique

# Largest element repeated
assert Solution().largestUniqueNumber([1,2,5,3,5,4]) == 4  # 5 repeats, 4 is largest unique

# Multiple duplicates, one unique
assert Solution().largestUniqueNumber([2,2,3,3,1]) == 1  # only 1 is unique

# Array with all same elements
assert Solution().largestUniqueNumber([7,7,7,7]) == -1  # no unique
Test Why
[5,7,3,9,4,9,8,3,1] Standard case with multiple duplicates
[9,9,8,8] No unique numbers
[42] Single-element edge case
[1,2,5,3,5,4] Largest element repeats, must choose next largest unique
[2,2,3,3,1] Only one unique number
[7,7,7,7] All elements repeated, return -1

Edge Cases

One important edge case is an array with a single element. The algorithm correctly handles this because the hash map will have one entry with a count of 1, which will be returned.

Another edge case is when the largest number in the array is repeated. A naive implementation that simply returns the maximum would fail here. Our approach explicitly checks for counts equal to 1, so it avoids this pitfall.

Finally, an array where all elements are duplicates requires careful handling. The initialization of largest_unique to -1 ensures that if no element meets the uniqueness criterion, the function correctly returns -1. This prevents returning an incorrect maximum from the array.