Biggest Single Number

Difficulty: Easy | Acceptance: 71.20% | Paid: No Topics: Database

Table: MyNumbers

+-------------+------+ | Column Name | Type | +-------------+------+ | num | int | +-------------+------+ There is no primary key for this table. Each row in this table contains a single integer num.

Write a solution to find the largest number that appears exactly once in the MyNumbers table. If there is no such number, return null.

The result format is in the following example.

• Examples
• Constraints
• Approach 1: Hash Map Frequency Count
• Approach 2: Sorting
• Approach 3: Set Operations

Examples

Example 1:

Input: MyNumbers table: +-----+ | num | +-----+ | 8 | | 8 | | 3 | | 3 | | 1 | | 4 | | 5 | | 6 | +-----+

Output: +-----+ | num | +-----+ | 6 | +-----+

Explanation: The number 6 is the largest number that appears exactly once.

Example 2:

Input: MyNumbers table: +-----+ | num | +-----+ | 8 | | 1 | | 2 | | 2 | | 5 | +-----+

Output: +-----+ | num | +-----+ | 8 | +-----+

Explanation: The numbers 1, 5, and 8 appear exactly once. 8 is the largest among them.

Example 3:

Input: MyNumbers table: +-----+ | num | +-----+ | 8 | | 8 | | 7 | | 7 | +-----+

Output: +------+ | num | +------+ | null | +------+

Explanation: There is no number that appears exactly once.

Constraints

-10⁹ <= num <= 10⁹

Approach 1: Hash Map Frequency Count

Intuition We iterate through the list of numbers and count the frequency of each number using a hash map. Then, we iterate through the map to find the maximum number that has a frequency of exactly 1.

Steps

• Initialize an empty hash map (or dictionary) to store the frequency of each number.
• Iterate through the input list of numbers. For each number, increment its count in the hash map.
• Initialize a variable to store the result (e.g., max_num), set to null or a minimum value.
• Iterate through the entries in the hash map. If a number’s count is 1 and it is greater than the current max_num, update max_num.
• Return max_num.

from typing import List, Optional

class Solution:
    def biggestSingleNumber(self, nums: List[int]) -> Optional[int]:
        freq = {}
        for num in nums:
            freq[num] = freq.get(num, 0) + 1
        
        max_num = None
        for num, count in freq.items():
            if count == 1:
                if max_num is None or num > max_num:
                    max_num = num
        return max_num

Complexity

• Time: O(N) where N is the number of elements in the input list. We iterate through the list once to build the map and once through the map to find the max.
• Space: O(N) to store the frequency map.
• Notes: This approach is very efficient and easy to understand. It requires extra space proportional to the number of unique elements.

Approach 2: Sorting

Intuition If we sort the numbers in descending order, the first number we encounter that is not equal to its neighbors is the largest single number.

Steps

• Sort the input list of numbers in descending order.
• Iterate through the sorted list.
• For each number at index i, check if it is equal to the number at i-1 or i+1 (handling boundary conditions).
• If it is not equal to either neighbor, it is the largest single number. Return it immediately.
• If the loop finishes without finding a unique number, return null.

from typing import List, Optional

class Solution:
    def biggestSingleNumber(self, nums: List[int]) -> Optional[int]:
        if not nums:
            return None
        
        nums.sort(reverse=True)
        n = len(nums)
        
        for i in range(n):
            is_unique = True
            if i > 0 and nums[i] == nums[i-1]:
                is_unique = False
            if i < n - 1 and nums[i] == nums[i+1]:
                is_unique = False
            
            if is_unique:
                return nums[i]
        
        return None

Complexity

• Time: O(N log N) due to the sorting step.
• Space: O(1) or O(N) depending on the sorting algorithm’s space complexity (e.g., quicksort vs timsort).
• Notes: This approach modifies the original array (or creates a copy). It is slower than the hash map approach for large N but uses less space if sorting is done in-place.

Approach 3: Set Operations

Intuition We can use two sets: one to track numbers we have seen, and another to track numbers we have seen more than once (duplicates). The result is the maximum number present in the “seen” set but not in the “duplicates” set.

Steps

• Initialize an empty set seen and an empty set duplicates.
• Iterate through the input list.
• If the current number is in seen, add it to duplicates.
• Otherwise, add it to seen.
• After processing all numbers, iterate through seen. If a number is not in duplicates, it is a candidate. Track the maximum candidate.
• Return the maximum candidate or null if no candidate exists.

from typing import List, Optional

class Solution:
    def biggestSingleNumber(self, nums: List[int]) -> Optional[int]:
        seen = set()
        duplicates = set()
        
        for num in nums:
            if num in seen:
                duplicates.add(num)
            else:
                seen.add(num)
        
        max_num = None
        for num in seen:
            if num not in duplicates:
                if max_num is None or num > max_num:
                    max_num = num
                    
        return max_num

Complexity

• Time: O(N) average time complexity for set insertions and lookups.
• Space: O(N) to store the sets.
• Notes: This approach is conceptually clean and separates the logic of identifying duplicates from finding the maximum. It uses more memory than the single hash map approach because it stores two sets.