Skip to main content
Talentd

Largest Unique Number - Solution & Explanation

EasyPremiumFree on FleetCodeArrayHash TableSorting6 min readAsked at: Amazon
Practice this problem

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 <= 2000
  • 0 <= 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.

Solution

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.

Code

PythonJavaC++GoTypeScriptJavaScript

Python

Java

C++

Go

TypeScript

JavaScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + ScanO(n log n)O(1)When modifying the array order is acceptable and simplicity matters more than optimal runtime
Hash Map Counting + Reverse TraversalO(n)O(n)Best general solution for unsorted arrays when you need linear time
Fixed-Size Frequency ArrayO(n)O(k)When the value range is small and bounded (e.g., 0–1000)

Video Solution

LeetCode 1133: Largest Unique Number - Interview Prep Ep 41 • Fisher Coder • 1,357 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Largest Unique Number easy or hard?
Largest Unique Number is categorized as an Easy problem. It mainly tests familiarity with arrays and hash table frequency counting, a foundational technique used across many coding interview questions.
Largest Unique Number Python/Java solution
Most implementations follow the same pattern: count frequencies using a dictionary (Python) or HashMap (Java), then find the largest key with count equal to one. The algorithm remains O(n) regardless of language.
How to solve Largest Unique Number in O(n)?
Iterate through the array and store counts in a hash map or frequency array. After building the counts, check each value and track the maximum number whose count equals one. Hash lookups are O(1), so the entire algorithm completes in linear time.
What is the best approach for Largest Unique Number?
The most efficient approach uses frequency counting with a hash map. First count how many times each value appears, then scan for the largest number whose frequency equals one. This runs in O(n) time with O(n) space and avoids the O(n log n) cost of sorting.
Is Largest Unique Number asked at Google/Amazon/Meta?
Problems involving frequency counting and hash maps appear frequently in interviews at companies like Amazon, Meta, and Google. While this exact problem may vary, the underlying pattern—tracking element frequencies to detect uniqueness—is very common.
What data structure is used in Largest Unique Number?
The typical solution uses a hash table (dictionary or map) to store frequencies of numbers. If the value range is small, a fixed-size counting array can replace the hash map for faster lookups and lower overhead.
What is the time complexity of Largest Unique Number?
The optimal solution runs in O(n) time because each element is processed during the counting pass and checked once more when determining the largest unique value. Space complexity is O(n) in the worst case due to the frequency map storing distinct elements.

Ready to solve this problem?

Practice Largest Unique Number with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays