Jobs

Interviews

Discussions

Largest Unique Number

Easy

Asked by:

13 views

Topics:

ArraysGreedy Algorithms

Given an array of integers nums, find the largest integer that appears only once.

To clarify:

If there is no number that appears only once, return -1.
If there are multiple numbers that appear only once, return the largest of them.

Example 1:

Input: nums = [5,7,3,9,4,0,5,8,3]
Output: 9
Explanation: 
There are unique numbers [7,9,4,0,8]
The largest of these is 9.

Example 2:

Input: nums = [9,9,8,8]
Output: -1
Explanation: 
There are no unique numbers.

Constraints:

1 <= nums.length <= 2000
0 <= nums[i] <= 1000

Try coding it in LeetCode

Largest Unique Number

Easy

Asked by:

13 views

Topics:

ArraysGreedy Algorithms

Given an array of integers nums, find the largest integer that appears only once.

To clarify:

If there is no number that appears only once, return -1.
If there are multiple numbers that appear only once, return the largest of them.

Example 1:

Input: nums = [5,7,3,9,4,0,5,8,3]
Output: 9
Explanation: 
There are unique numbers [7,9,4,0,8]
The largest of these is 9.

Example 2:

Input: nums = [9,9,8,8]
Output: -1
Explanation: 
There are no unique numbers.

Constraints:

1 <= nums.length <= 2000
0 <= nums[i] <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers in the input array? Can they be negative, zero, or positive?
What should I return if there are no unique numbers in the input array?
If there are multiple numbers that appear only once and are the largest among the unique numbers, which one should I return?
Can the input array be empty or null? If so, what should I return?
What is the maximum possible size of the input array?

Brute Force Solution

Approach

The brute force method for finding the largest unique number means checking every number in the input to see if it's unique. We start with the largest possible number and work our way down, stopping as soon as we find a unique one.

Here's how the algorithm would work step-by-step:

Look at each number in the collection of numbers.
Check if the number appears more than once in the collection.
If the number appears only once (it's unique), remember it as a possible answer.
If the number appears more than once, forget about it and move on to the next number.
Once you've checked all the numbers, pick the largest number from all the possible answers you remembered. If you didn't find any unique numbers, then there is no answer.

Code Implementation

def largest_unique_number_brute_force(numbers):
    possible_answers = []
    
    for number in numbers:
        is_unique = True

        # Check if the number appears more than once.
        for other_number in numbers:
            if number == other_number and numbers.index(number) != numbers.index(other_number):
                is_unique = False
                break

        # If the number is unique, remember it.
        if is_unique:
            possible_answers.append(number)

    # Need to handle the case where no number is unique.
    if not possible_answers:
        return -1
    
    # Find the largest among unique numbers.
    return max(possible_answers)

Big(O) Analysis

Time Complexity

O(n²) – The provided brute force approach iterates through each of the n numbers in the input array. For each number, it checks its uniqueness by comparing it with every other number in the array, requiring another n comparisons in the worst case. Therefore, the algorithm performs approximately n * n comparisons. This n * n operations approximates to O(n²).

Space Complexity

O(1) – The provided algorithm only stores a single variable to remember a 'possible answer'. The size of this variable is independent of the input array's size (N). Therefore, the auxiliary space used is constant, resulting in a space complexity of O(1).

Optimal Solution

Approach

To find the largest unique number in a list, we'll count how often each number appears. Then, we'll pick out the largest number that appears only once.

Here's how the algorithm would work step-by-step:

First, we need to count how many times each number shows up in the list.
Next, we look at our counts and find the numbers that only appear once.
From those unique numbers, we pick out the largest one.
If we didn't find any unique numbers (all numbers appeared more than once), then the answer is 'no such number'.

Code Implementation

def largest_unique_number(numbers):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    # Identify numbers appearing only once.
    unique_numbers = [number for number, count in number_counts.items() if count == 1]

    # Handle the case where there are no unique numbers.
    if not unique_numbers:
        return -1

    # Find the largest among the unique numbers.
    largest_unique = max(unique_numbers)

    return largest_unique

Big(O) Analysis

Time Complexity

O(n) – The first step involves counting the frequency of each number in the list, which requires iterating through the list once, taking O(n) time, where n is the number of elements in the list. Then we filter for numbers that appear only once, which again takes O(n) time as we iterate through the counts. Finally, finding the largest among the unique numbers takes at most O(n) time. Therefore, the dominant operation is iterating through the list, resulting in a time complexity of O(n).

Space Complexity

O(N) – The algorithm first counts the frequency of each number in the input list. This requires a hash map (or similar data structure) to store these counts, where the keys are the numbers and the values are their counts. In the worst case, all N numbers in the input list are unique, requiring space proportional to N to store them in the hash map. Therefore, the auxiliary space used by the algorithm is O(N).

Edge Cases

Case	How to Handle
Empty input array	Return -1 if the input array is empty as there is no largest unique number.
Array with all duplicate numbers	Return -1 since no number is unique, indicating no valid solution.
Array with only one number	Return that single number if its count is one; otherwise, return -1.
Array with negative numbers only	The algorithm should correctly identify the largest negative number if it appears only once; otherwise return -1.
Array with large numbers	The solution should handle the numbers in a reasonable range avoiding integer overflow with appropriate data types.
Array with mixed positive, negative, and zero values	The solution must correctly identify the largest unique number regardless of sign.
Array with many duplicate values but one unique number	The algorithm needs to efficiently count the occurrence of each number and find the largest unique one.
Array with numbers close to the integer limit	Verify chosen data type can represent extreme numbers to avoid overflow/underflow during processing.

Empty input array

How to Handle:

Return -1 if the input array is empty as there is no largest unique number.

Array with all duplicate numbers

How to Handle:

Return -1 since no number is unique, indicating no valid solution.

Array with only one number

How to Handle:

Return that single number if its count is one; otherwise, return -1.

Array with negative numbers only

How to Handle:

The algorithm should correctly identify the largest negative number if it appears only once; otherwise return -1.

Array with large numbers

How to Handle:

The solution should handle the numbers in a reasonable range avoiding integer overflow with appropriate data types.

Array with mixed positive, negative, and zero values

How to Handle:

The solution must correctly identify the largest unique number regardless of sign.

Array with many duplicate values but one unique number

How to Handle:

The algorithm needs to efficiently count the occurrence of each number and find the largest unique one.

Array with numbers close to the integer limit

How to Handle:

Verify chosen data type can represent extreme numbers to avoid overflow/underflow during processing.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the numbers in the input array? Can they be negative, zero, or positive?
What should I return if there are no unique numbers in the input array?
If there are multiple numbers that appear only once and are the largest among the unique numbers, which one should I return?
Can the input array be empty or null? If so, what should I return?
What is the maximum possible size of the input array?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at each number in the collection of numbers.
Check if the number appears more than once in the collection.
If the number appears only once (it's unique), remember it as a possible answer.
If the number appears more than once, forget about it and move on to the next number.
Once you've checked all the numbers, pick the largest number from all the possible answers you remembered. If you didn't find any unique numbers, then there is no answer.

Code Implementation

def largest_unique_number_brute_force(numbers):
    possible_answers = []
    
    for number in numbers:
        is_unique = True

        # Check if the number appears more than once.
        for other_number in numbers:
            if number == other_number and numbers.index(number) != numbers.index(other_number):
                is_unique = False
                break

        # If the number is unique, remember it.
        if is_unique:
            possible_answers.append(number)

    # Need to handle the case where no number is unique.
    if not possible_answers:
        return -1
    
    # Find the largest among unique numbers.
    return max(possible_answers)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

To find the largest unique number in a list, we'll count how often each number appears. Then, we'll pick out the largest number that appears only once.

Here's how the algorithm would work step-by-step:

First, we need to count how many times each number shows up in the list.
Next, we look at our counts and find the numbers that only appear once.
From those unique numbers, we pick out the largest one.
If we didn't find any unique numbers (all numbers appeared more than once), then the answer is 'no such number'.

Code Implementation

def largest_unique_number(numbers):
    number_counts = {}
    for number in numbers:
        number_counts[number] = number_counts.get(number, 0) + 1

    # Identify numbers appearing only once.
    unique_numbers = [number for number, count in number_counts.items() if count == 1]

    # Handle the case where there are no unique numbers.
    if not unique_numbers:
        return -1

    # Find the largest among the unique numbers.
    largest_unique = max(unique_numbers)

    return largest_unique

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty input array	Return -1 if the input array is empty as there is no largest unique number.
Array with all duplicate numbers	Return -1 since no number is unique, indicating no valid solution.
Array with only one number	Return that single number if its count is one; otherwise, return -1.
Array with negative numbers only	The algorithm should correctly identify the largest negative number if it appears only once; otherwise return -1.
Array with large numbers	The solution should handle the numbers in a reasonable range avoiding integer overflow with appropriate data types.
Array with mixed positive, negative, and zero values	The solution must correctly identify the largest unique number regardless of sign.
Array with many duplicate values but one unique number	The algorithm needs to efficiently count the occurrence of each number and find the largest unique one.
Array with numbers close to the integer limit	Verify chosen data type can represent extreme numbers to avoid overflow/underflow during processing.

Empty input array

How to Handle:

Return -1 if the input array is empty as there is no largest unique number.

Array with all duplicate numbers

How to Handle:

Return -1 since no number is unique, indicating no valid solution.

Array with only one number

How to Handle:

Return that single number if its count is one; otherwise, return -1.

Array with negative numbers only

How to Handle:

The algorithm should correctly identify the largest negative number if it appears only once; otherwise return -1.

Array with large numbers

How to Handle:

The solution should handle the numbers in a reasonable range avoiding integer overflow with appropriate data types.

Array with mixed positive, negative, and zero values

How to Handle:

The solution must correctly identify the largest unique number regardless of sign.

Array with many duplicate values but one unique number

How to Handle:

The algorithm needs to efficiently count the occurrence of each number and find the largest unique one.

Array with numbers close to the integer limit

How to Handle:

Verify chosen data type can represent extreme numbers to avoid overflow/underflow during processing.