1133. Largest Unique Number
Problem Description
The problem presents us with a simple task: Given an array of integers called nums
, we are to find the highest value integer that appears exactly once in the array. If all integers appear more than once or if the array is empty, the function should return -1
.
For example, if the input array is [5, 7, 3, 9, 4, 9, 8, 3, 1]
, the function should return 8
, as it is the largest integer that appears only once.
This is essentially a frequency problem where we need to count how many times each number appears, and then find the largest number that has a frequency of 1.
Intuition
The intuition behind the solution is to keep track of the frequency of each element in the array and then search for the elements with a frequency of 1, starting from the largest potential number and moving downwards. The search stops when we find the first number that meets this criterion, as that would be the largest unique number.
To apply this solution approach efficiently:
- We use the
Counter
class from Python'scollections
module to quickly count the frequency of each integer in the input array. - After we have the frequency of each number, we iterate from the maximum possible integer value down to 0. This ensures that the first integer we find with a frequency of 1 is the largest such integer.
- We use a generator expression within the
next
function which goes through the numbers in the decreasing order checking for the conditioncnt[x] == 1
. - If no integer with a frequency of 1 is found, the
next
function returns-1
as specified by its default parameter.
With this approach, we can efficiently solve the problem in linear time with respect to the number of elements in the array, which is quite optimal for this type of problem.
Learn more about Sorting patterns.
Solution Approach
The implementation consists of a few straightforward steps:
-
Import the
Counter
from thecollections
module. TheCounter
is a subclass ofdict
specifically designed to count hashable objects. It's an unordered collection where elements are stored as dictionary keys and their counts are stored as dictionary values. -
The
cnt = Counter(nums)
creates aCounter
object with the frequency of each integer from thenums
array. For example, ifnums
is[1, 2, 2, 3]
,cnt
would beCounter({2: 2, 1: 1, 3: 1})
. -
The core of the implementation is the line
return next((x for x in range(1000, -1, -1) if cnt[x] == 1), -1)
. This line uses a generator expression within thenext
function.-
The generator expression gives us a way to iterate through each integer from
1000
down to0
(range(1000, -1, -1)
). We're starting from1000
because, according to the constraints of the problem, the values innums
will not exceed1000
. -
For each number
x
in this range, we check ifcnt[x] == 1
. This condition is true only for numbers that occur exactly once innums
. If the condition is met,x
is yielded by the generator. -
The
next
function is used to find the first item in the sequence that satisfies the condition. If such an item is found, it's returned immediately, making the process efficient because we don't need to count or iterate through the whole range if we've already found our largest unique number. -
The second argument to
next
is-1
, which acts as the default value returned if the generator does not yield any value (which would be the case if there are no unique numbers).
-
This compact and efficient implementation bypasses the need for sorting or additional loops, as it directly makes use of the Counter
to access the frequency and uses the range
function in descending order to find the largest unique number.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
To illustrate the solution approach, let's take a small example. Suppose our input array is [4, 6, 2, 6, 4]
.
- First, we import the
Counter
class from thecollections
module. - We then create a
Counter
object to count the frequency of each integer in our array:
After creating thefrom collections import Counter nums = [4, 6, 2, 6, 4] cnt = Counter(nums) # Counter({4: 2, 6: 2, 2: 1})
Counter
object, it shows that both 4 and 6 occur twice, and 2 occurs once. - We then proceed to find the highest unique integer in
nums
by iterating from the highest possible value (1000) to the lowest in the array, checking if the frequency equals 1. For this example, our array doesn't go up to 1000, so we would just be interested in the range from the highest value innums
which is 6, down to the smallest 2:highest_unique = next((x for x in range(6, 1, -1) if cnt[x] == 1), -1)
- In our
range
, we start checking from 6 to 2:- Check if
cnt[6] == 1
: This isFalse
ascnt[6]
is2
. - Move to the next value,
5
, but it does not exist in ourCounter
, so move on. - Check if
cnt[4] == 1
: This isFalse
ascnt[4]
is2
. - Check if
cnt[3] == 1
: As3
is not in ourCounter
, we move on. - Check if
cnt[2] == 1
: This isTrue
ascnt[2]
is1
.
- Check if
- Since we have found that
2
is the largest value that occurs exactly once, we don't need to check any further. We can now return2
as the result.
The next
function will yield 2
and since it's the first number that satisfies our condition, this is the value that would be returned from our function call.
If no such unique value is found, the default -1
will be returned, signaling that there are no elements that occur exactly once.
Thus, in our small example, the function would return 2
as the highest value integer that appears exactly once.
Solution Implementation
1from collections import Counter
2
3class Solution:
4 def largestUniqueNumber(self, nums: list[int]) -> int:
5 # Count the occurrences of each number in nums
6 # using a Counter, which is a dictionary subclass
7 number_counts = Counter(nums)
8
9 # Traverse the range from 1000 (inclusive) to -1 (exclusive)
10 # in descending order to find the largest unique number
11 for num in range(1000, -1, -1):
12 # Check if the number appears exactly once
13 if number_counts[num] == 1:
14 # If the number is unique, return it
15 return num
16
17 # Return -1 if no unique number is found
18 return -1
19
1class Solution {
2
3 // Method to find the largest unique number in an array
4 public int largestUniqueNumber(int[] nums) {
5 // Array to store the count of each number, assuming the values are within [0, 1000]
6 int[] count = new int[1001];
7
8 // Loop through each number in the given array 'nums' and increment its count
9 for (int num : nums) {
10 count[num]++;
11 }
12
13 // Iterate from the largest possible value (1000) down to 0
14 for (int i = 1000; i >= 0; i--) {
15 // Check if the count of the current number is exactly 1 (unique)
16 if (count[i] == 1) {
17 // If a unique number is found, return it as it will be the largest one due to the reverse iteration
18 return i;
19 }
20 }
21
22 // If no unique number is found, return -1 as specified by the problem
23 return -1;
24 }
25}
26
1#include <vector>
2using namespace std;
3
4class Solution {
5public:
6 // Function to find the largest unique number from the vector
7 int largestUniqueNumber(vector<int>& nums) {
8 // Initialize an array to count occurrences of each number, given the maximal value of 1000.
9 int frequency[1001] = {}; // Indexed from 0 to 1000
10
11 // Populate the frequency array with the count of each number from 'nums'.
12 for (int num : nums) {
13 ++frequency[num];
14 }
15
16 // Iterate from the end of the frequency array (starting from the largest possible value - 1000)
17 // to find the first number with a frequency of 1 (unique number).
18 for (int i = 1000; i >= 0; --i) {
19 if (frequency[i] == 1) {
20 // If a unique number is found, return it as the largest unique number
21 return i;
22 }
23 }
24
25 // If no unique number is found, return -1.
26 return -1;
27 }
28};
29
1function largestUniqueNumber(nums: number[]): number {
2 // Initialize an array of size 1001 to count the occurrences of each number.
3 const count = new Array(1001).fill(0);
4
5 // Iterate over the input array and increment the count at the index equal to the number.
6 for (const num of nums) {
7 ++count[num];
8 }
9
10 // Iterate backward from the largest possible number (1000)
11 // to find the first number that has a count of 1.
12 for (let i = 1000; i >= 0; --i) {
13 if (count[i] === 1) {
14 return i; // Return the largest unique number.
15 }
16 }
17
18 // If no unique number is found, return -1.
19 return -1;
20}
21
Time and Space Complexity
Time Complexity
The time complexity of the provided code consists of two parts: creating the counter and finding the largest unique number.
-
Creating the Counter: The
Counter
function fromcollections
module is used to count the frequency of each element in the input listnums
. The time complexity of this operation isO(n)
, wheren
is the length of the input listnums
, as it requires a single pass over all elements to count their frequencies. -
Finding the Largest Unique Number: The generator expression inside
next
iterates from1000
to0
, which is a constant range, and checks if the count of each number is exactly1
. The worst-case time complexity of this operation isO(1)
because we're iterating over a fixed range independent of the input size.
Combining both, the overall time complexity is O(n + 1)
, which simplifies to O(n)
because asymptotic analysis drops constant terms.
Space Complexity
The space complexity also consists of two parts: the space used by the Counter
and the space for the generator expression.
-
Counter Space: The
Counter
object will hold at mostn
unique numbers and their counts, so in the worst case, where all numbers innums
are unique, the space complexity isO(n)
. -
Generator Expression Space: The generator expression does not create an additional list; it simply iterates over the range and yields values one by one. Therefore, its space complexity is
O(1)
.
Overall, the space complexity of the algorithm is O(n)
, dominated by the space required for the Counter
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Want a Structured Path to Master System Design Too? Donāt Miss This!