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] <= 1000Problem 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.
Given the data range in the problem, we can use an array of length 1001 to count the occurrence of each number. Then, we traverse the array in reverse order to find the first number that appears only once. If no such number is found, we return -1.
The time complexity is O(n + M), and the space complexity is O(M). Here, n is the length of the array, and M is the maximum number that appears in the array. In this problem, M leq 1000.
Python
Java
C++
Go
TypeScript
JavaScript
| 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) |
LeetCode 1133: Largest Unique Number - Interview Prep Ep 41 • Fisher Coder • 1,339 views views
Watch 7 more video solutions →Practice Largest Unique Number with our built-in code editor and test cases.
Practice on FleetCode