Problem Description

The Biggest Single Number problem requires you to find the largest integer in a list that appears exactly once. Given an array of integers nums, return the biggest number that occurs only once. If no such number exists, return -1.

• Each element in nums is an integer (positive, negative, or zero).
• There may be multiple numbers that appear only once; you must return the largest among them.
• If all numbers appear more than once (or the list is empty), return -1.
• Do not reuse or combine elements; each element is considered individually.

Thought Process

At first glance, you might think of checking each number and counting how many times it appears in the array. For every number, you could count its occurrences and, if it appears only once, keep track of the largest such number. However, this brute-force approach would be inefficient, especially for large arrays, because it would require scanning the entire array for every unique number.

To optimize, we need a way to efficiently determine how many times each number appears. This leads us to the idea of using a data structure that can count occurrences quickly, such as a hash map (dictionary). With a hash map, we can count all occurrences in a single pass, then scan through the map to find the largest number with a count of one.

Solution Approach

Let's break down the solution step by step:

1. Count Occurrences:
   • Use a hash map (dictionary) to count how many times each number appears in nums.
   • This allows us to process the entire array in one pass, updating the count for each number.
2. Find the Biggest Unique Number:
   • Iterate through the keys in the hash map.
   • For each number that has a count of exactly one, compare it to the current maximum unique number found.
   • Keep track of the largest such number.
3. Return the Result:
   • If at least one number appeared exactly once, return the largest one.
   • If no number appeared exactly once, return -1.

This approach is efficient because counting is done in O(n) time, and finding the maximum is O(m), where m is the number of unique numbers (at most n).

Example Walkthrough

Let's look at a sample input:

• nums = [5, 3, 9, 3, 5, 7, 8]

1. Count Occurrences:
   • 5: appears 2 times
   • 3: appears 2 times
   • 9: appears 1 time
   • 7: appears 1 time
   • 8: appears 1 time
2. Find the Biggest Unique Number:
   • Unique numbers: 9, 7, 8
   • The largest among them is 9
3. Return:
   • Return 9

If the input was [4, 4, 4, 4], then no number appears exactly once, so we would return -1.

Code Implementation

class Solution:
    def singleNumber(self, nums):
        from collections import Counter
        count = Counter(nums)
        max_unique = -1
        for num in count:
            if count[num] == 1:
                max_unique = max(max_unique, num)
        return max_unique
      

#include <unordered_map>
#include <vector>
#include <algorithm>

class Solution {
public:
    int singleNumber(std::vector<int>& nums) {
        std::unordered_map<int, int> count;
        for (int num : nums) {
            count[num]++;
        }
        int max_unique = -1;
        for (auto& p : count) {
            if (p.second == 1) {
                max_unique = std::max(max_unique, p.first);
            }
        }
        return max_unique;
    }
};
      

import java.util.*;

class Solution {
    public int singleNumber(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            count.put(num, count.getOrDefault(num, 0) + 1);
        }
        int maxUnique = -1;
        for (int num : count.keySet()) {
            if (count.get(num) == 1) {
                maxUnique = Math.max(maxUnique, num);
            }
        }
        return maxUnique;
    }
}
      

var singleNumber = function(nums) {
    const count = {};
    for (const num of nums) {
        count[num] = (count[num] || 0) + 1;
    }
    let maxUnique = -1;
    for (const num in count) {
        if (count[num] === 1) {
            maxUnique = Math.max(maxUnique, Number(num));
        }
    }
    return maxUnique;
};
      

Time and Space Complexity

Brute-force Approach:

• For each unique number, scan the entire array to count occurrences.
• If there are n elements and m unique numbers, time complexity is O(n * m).
• Space complexity is O(1) if not storing counts, but usually O(m) if storing unique numbers.

• Counting all occurrences: O(n), where n is the number of elements.
• Finding the maximum unique number: O(m), where m is the number of unique numbers (m ≤ n).
• Total time complexity: O(n).
• Space complexity: O(m), for storing the counts in the hash map.

The optimized approach is much more efficient, especially for large arrays, because it avoids repeated scanning.

Summary

The key insight for the Biggest Single Number problem is to efficiently count the occurrences of each number using a hash map, then select the largest number that appears exactly once. This approach is both simple and efficient, requiring only two passes over the data. It avoids unnecessary repeated work and leverages the power of hash maps for fast lookups and updates. The result is a solution that is easy to understand, implement, and scales well with input size.