LeetCode 1133: Largest Unique Number - Interview Prep Ep 41
Largest Unique Number - Video Solution
Watch 9 video solutions for Largest Unique Number, a easy level problem involving Array, Hash Table, Sorting. This walkthrough by Fisher Coder has 1,357 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
Given an integer array nums, return the largest integer that only occurs once. If no integer occurs once, return -1.
Example 1:
Input: nums = [5,7,3,9,4,9,8,3,1] Output: 8 Explanation: The maximum integer in the array is 9 but it is repeated. The number 8 occurs only once, so it is the answer.
Example 2:
Input: nums = [9,9,8,8] Output: -1 Explanation: There is no number that occurs only once.
Constraints:
1 <= nums.length <= 20000 <= nums[i] <= 1000
Approach Overview
Problem Overview: You receive an integer array and need the largest value that appears exactly once. If every number occurs more than once, return -1. The challenge is identifying uniqueness while still retrieving the maximum value efficiently.
Approach 1: Sorting + Scan (O(n log n) time, O(1) extra space)
A straightforward strategy sorts the array first. After sorting, identical values appear in consecutive positions. Traverse the sorted array and count the length of each block of equal numbers. If a block has size one, it represents a unique value. Track the largest such value while scanning. This method works well when sorting is already required elsewhere in the pipeline, but the O(n log n) sorting cost is unnecessary for this specific task.
Approach 2: Counting + Reverse Traversal (O(n) time, O(n) space)
The optimal solution uses a frequency count with a hash table. First iterate through the array and record how many times each number appears using a dictionary or map. After building the frequency map, scan the numbers again and track the largest value whose count equals one. Many implementations also optimize by iterating values in descending order or performing a reverse traversal after computing counts. The key insight: uniqueness is determined purely by frequency, and a hash lookup makes this check O(1).
This approach separates the problem into two simple passes: counting and selection. The first pass builds frequency information; the second pass finds the maximum unique value. Because each element is processed a constant number of times, the total runtime is linear. The memory cost is proportional to the number of distinct elements.
If the value range is small (for example 0–1000, which often appears in this problem), the counting structure can also be implemented using a fixed-size array instead of a map. This reduces overhead and behaves like classic counting sort logic from sorting algorithms.
Recommended for interviews: Interviewers expect the counting approach. Starting with the sorting idea demonstrates baseline reasoning, but the hash-based frequency method shows stronger algorithmic judgment. It reduces the time complexity from O(n log n) to O(n) while keeping the implementation simple and readable.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Scan | O(n log n) | O(1) | When modifying the array order is acceptable and simplicity matters more than optimal runtime |
| Hash Map Counting + Reverse Traversal | O(n) | O(n) | Best general solution for unsorted arrays when you need linear time |
| Fixed-Size Frequency Array | O(n) | O(k) | When the value range is small and bounded (e.g., 0–1000) |