619. Biggest Single Number - Solution

The problem

Table: MyNumbers

+-------------+------+
| Column Name | Type |
+-------------+------+
| num         | int  |
+-------------+------+
This table may contain duplicates (In other words, there is no primary key for this table in SQL).
Each row of this table contains an integer.

A single number is a number that appeared only once in the MyNumbers table.

Find the largest single number. If there is no single number, report null.

The result format is in the following example.

Example 1:

Input: 
MyNumbers table:
+-----+
| num |
+-----+
| 8   |
| 8   |
| 3   |
| 3   |
| 1   |
| 4   |
| 5   |
| 6   |
+-----+
Output: 
+-----+
| num |
+-----+
| 6   |
+-----+
Explanation: The single numbers are 1, 4, 5, and 6.
Since 6 is the largest single number, we return it.

Example 2:

Input: 
MyNumbers table:
+-----+
| num |
+-----+
| 8   |
| 8   |
| 7   |
| 7   |
| 3   |
| 3   |
| 3   |
+-----+
Output: 
+------+
| num  |
+------+
| null |
+------+
Explanation: There are no single numbers in the input table so we return null.

Approach overview

Problem Overview: You are given a list (or database column) of integers. The task is to return the largest number that appears exactly once. If every number appears more than once, the result should be null. The core challenge is identifying unique values while still tracking the maximum among them.

Approach 1: Using HashMap / Dictionary for Count Tracking (Time: O(n), Space: O(n))

This approach performs a frequency count of each number using a hash map. First iterate through the array (or records) and update a dictionary where key = number and value = frequency. After building the frequency map, iterate through all entries and check which numbers have a count of 1. Track the maximum among those unique numbers. Hash lookups run in constant time, so the entire counting and scanning process remains linear.

The key insight is separating the problem into two steps: frequency counting and maximum selection. This approach works for any unsorted dataset and avoids repeated scanning of the array. It is the most straightforward implementation in languages like Python, Java, and C++ using built-in map structures.

Approach 2: Using Sorting for Efficient Search (Time: O(n log n), Space: O(1) or O(n))

This method first sorts the numbers using a sorting algorithm. Once sorted, duplicate values appear next to each other. You can scan from the largest element toward the beginning and check whether the current value differs from both its neighbors. If a value appears exactly once, it must not match the previous or next element in the sorted order.

Starting the scan from the end allows you to stop immediately when the first valid unique number is found, which guarantees it is the largest. Sorting increases time complexity to O(n log n), but the logic after sorting becomes very simple and avoids additional data structures. This approach is useful when the dataset is already sorted or when memory usage must remain minimal.

Problems like this often appear in database-style questions where aggregation and uniqueness are required. Understanding counting patterns with hash maps or ordering with sorting helps solve many similar interview problems.

Recommended for interviews: The hash map counting approach is usually expected because it achieves O(n) time with straightforward logic. Mentioning the sorting alternative demonstrates awareness of tradeoffs, but interviewers typically prefer the linear-time solution since it scales better for large datasets.

Approach 1: Using HashMap/Dictionary for Count Tracking

This approach involves using a hash map or dictionary to count the number of occurrences of each integer in the array. After counting, we identify numbers that appeared only once and find the maximum among them. This way, we can efficiently determine the largest single number.

Python

def biggest_single_number(nums):
    num_count = {}
    for num in nums:
        if num in num_count:
            num_count[num] += 1
        else:
            num_count[num] = 1

    max_num = float('-inf')
    for num, count in num_count.items():
        if count == 1:
            max_num = max(max_num, num)

    return None if max_num == float('-inf') else max_num

numbers = [8, 8, 3, 3, 1, 4, 5, 6]
result = biggest_single_number(numbers)
print('null' if result is None else result)

Java

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public static Integer biggestSingleNumber(int[] nums) {
        Map<Integer, Integer> numCount = new HashMap<>();
        for (int num : nums) {
            numCount.put(num, numCount.getOrDefault(num, 0) + 1);
        }

        Integer maxNum = null;
        for (Map.Entry<Integer, Integer> entry : numCount.entrySet()) {
            if (entry.getValue() == 1) {
                if (maxNum == null || entry.getKey() > maxNum) {
                    maxNum = entry.getKey();
                }
            }
        }

        return maxNum;
    }

    public static void main(String[] args) {
        int[] nums = {8, 8, 3, 3, 1, 4, 5, 6};
        Integer result = biggestSingleNumber(nums);
        System.out.println(result != null ? result : "null");
    }
}

C++

#include <iostream>
#include <map>
#include <vector>
using namespace std;

int biggestSingleNumber(vector<int>& nums) {
    map<int, int> numCount;
    for (auto num : nums) {
        numCount[num]++;
    }

    int maxNum = INT_MIN;
    for (auto [num, count] : numCount) {
        if (count == 1) {
            maxNum = max(maxNum, num);
        }
    }

    return maxNum == INT_MIN ? -1 : maxNum;
}

int main() {
    vector<int> nums = {8, 8, 3, 3, 1, 4, 5, 6};
    int result = biggestSingleNumber(nums);
    if (result == -1) {
        cout << "null" << endl;
    } else {
        cout << result << endl;
    }
    return 0;
}

JavaScript

function biggestSingleNumber(nums) {
    const numCount = {};
    for (const num of nums) {
        numCount[num] = (numCount[num] || 0) + 1;
    }

    let maxNum = -Infinity;
    for (const [num, count] of Object.entries(numCount)) {
        if (count === 1) {
            maxNum = Math.max(maxNum, parseInt(num));
        }
    }

    return maxNum === -Infinity ? null : maxNum;
}

const nums = [8, 8, 3, 3, 1, 4, 5, 6];
const result = biggestSingleNumber(nums);
console.log(result !== null ? result : "null");

#include <stdio.h>
#include <stdlib.h>

struct element {
    int num;
    int count;
};

int compare(const void *a, const void *b) {
    return ((struct element *)b)->num - ((struct element *)a)->num;
}

int biggestSingleNumber(int* nums, int numsSize) {
    if (numsSize == 0) return -1;
    
    struct element elements[numsSize];
    int elementsSize = 0;
    int found;
    
    for (int i = 0; i < numsSize; i++) {
        found = 0;
        for (int j = 0; j < elementsSize; j++) {
            if (elements[j].num == nums[i]) {
                elements[j].count++;
                found = 1;
                break;
            }
        }
        if (!found) {
            elements[elementsSize].num = nums[i];
            elements[elementsSize].count = 1;
            elementsSize++;
        }
    }
    
    qsort(elements, elementsSize, sizeof(struct element), compare);

    for (int i = 0; i < elementsSize; i++) {
        if (elements[i].count == 1) {
            return elements[i].num;
        }
    }
    return -1;
}

int main() {
    int nums[] = {8, 8, 3, 3, 1, 4, 5, 6};
    int result = biggestSingleNumber(nums, sizeof(nums)/sizeof(nums[0]));
    if (result == -1) {
        printf("null\n");
    } else {
        printf("%d\n", result);
    }
    return 0;
}

using System;
using System.Collections.Generic;

class Program {
    public static int? BiggestSingleNumber(int[] nums) {
        Dictionary<int, int> numCount = new Dictionary<int, int>();
        foreach (int num in nums) {
            if (numCount.ContainsKey(num)) {
                numCount[num]++;
            } else {
                numCount[num] = 1;
            }
        }

        int? maxNum = null;
        foreach (var pair in numCount) {
            if (pair.Value == 1) {
                if (maxNum == null || pair.Key > maxNum) {
                    maxNum = pair.Key;
                }
            }
        }

        return maxNum;
    }

    static void Main() {
        int[] nums = {8, 8, 3, 3, 1, 4, 5, 6};
        int? result = BiggestSingleNumber(nums);
        Console.WriteLine(result != null ? result.ToString() : "null");
    }
}

This Python script uses a dictionary to tally occurrences of each number. We iterate over the dictionary to find numbers with only one occurrence and determine the largest among them.

Complexity

Time Complexity: O(n) on average, O(n) in worst case due to dictionary operations.
Space Complexity: O(n) for storing number counts in a dictionary.

Try this approach in the editor

Approach 2: Using Sorting for Efficient Search

This approach involves sorting the numbers first. After sorting, we can iterate through the list to count numbers that appear consecutively more than once and skip them. The largest number with only one occurrence is then the answer.

Python

def biggest_single_number(nums):
    if not nums:
        return None
    nums.sort(reverse=True)

    i = 0
    while i < len(nums):
        if (i == 0 or nums[i] != nums[i - 1]) and \
           (i == len(nums) - 1 or nums[i] != nums[i + 1]):
            return nums[i]
        i += 1

    return None

numbers = [8, 8, 3, 3, 1, 4, 5, 6]
result = biggest_single_number(numbers)
print('null' if result is None else result)

Java

import java.util.Arrays;

public class Solution {
    public static Integer biggestSingleNumber(int[] nums) {
        if (nums.length == 0) return null;
        Arrays.sort(nums);

        for (int i = nums.length - 1; i >= 0; i--) {
            if ((i == 0 || nums[i] != nums[i - 1]) &&
                (i == nums.length - 1 || nums[i] != nums[i + 1])) {
                return nums[i];
            }
        }

        return null;
    }

    public static void main(String[] args) {
        int[] nums = {8, 8, 3, 3, 1, 4, 5, 6};
        Integer result = biggestSingleNumber(nums);
        System.out.println(result != null ? result : "null");
    }
}

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int biggestSingleNumber(vector<int>& nums) {
    if (nums.empty()) return -1;
    
    sort(nums.begin(), nums.end(), greater<int>());

    for (size_t i = 0; i < nums.size(); ++i) {
        if ((i == 0 || nums[i] != nums[i - 1]) && 
            (i == nums.size() - 1 || nums[i] != nums[i + 1])) {
            return nums[i];
        }
    }

    return -1;
}

int main() {
    vector<int> nums = {8, 8, 3, 3, 1, 4, 5, 6};
    int result = biggestSingleNumber(nums);
    cout << (result == -1 ? "null" : to_string(result)) << endl;
    return 0;
}

JavaScript

function biggestSingleNumber(nums) {
    if (!nums.length) return null;
    nums.sort((a, b) => b - a);

    for (let i = 0; i < nums.length; i++) {
        if ((i === 0 || nums[i] !== nums[i - 1]) &&
            (i === nums.length - 1 || nums[i] !== nums[i + 1])) {
            return nums[i];
        }
    }

    return null;
}

const nums = [8, 8, 3, 3, 1, 4, 5, 6];
const result = biggestSingleNumber(nums);
console.log(result !== null ? result : "null");

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(int *)b - *(int *)a;
}

int biggestSingleNumber(int* nums, int numsSize) {
    if (numsSize == 0) return -1;
    
    qsort(nums, numsSize, sizeof(int), compare);

    for (int i = 0; i < numsSize; i++) {
        if ((i == 0 || nums[i] != nums[i - 1]) && 
            (i == numsSize - 1 || nums[i] != nums[i + 1])) {
            return nums[i];
        }
    }

    return -1;
}

int main() {
    int nums[] = {8, 8, 3, 3, 1, 4, 5, 6};
    int result = biggestSingleNumber(nums, sizeof(nums)/sizeof(nums[0]));
    if (result == -1) {
        printf("null\n");
    } else {
        printf("%d\n", result);
    }
    return 0;
}

using System;
using System.Linq;

class Program {
    public static int? BiggestSingleNumber(int[] nums) {
        if (nums.Length == 0) return null;
        Array.Sort(nums);

        for (int i = nums.Length - 1; i >= 0; i--) {
            if ((i == 0 || nums[i] != nums[i - 1]) &&
                (i == nums.Length - 1 || nums[i] != nums[i + 1])) {
                return nums[i];
            }
        }

        return null;
    }

    static void Main() {
        int[] nums = {8, 8, 3, 3, 1, 4, 5, 6};
        int? result = BiggestSingleNumber(nums);
        Console.WriteLine(result != null ? result.ToString() : "null");
    }
}

This Python script first sorts the list in descending order. It then iterates through the sorted list, identifying the largest single number using simple comparisons.

Complexity

Time Complexity: O(n log n) due to sorting.
Space Complexity: O(1) as sorting is done in place.

Try this approach in the editor

Approach 3: Grouping and Subquery

We can first group the MyNumbers table by num and count the number of occurrences of each number. Then, we can use a subquery to find the maximum number among the numbers that appear only once.

MySQL

# Write your MySQL query statement below
SELECT MAX(num) AS num
FROM
    (
        SELECT num
        FROM MyNumbers
        GROUP BY 1
        HAVING COUNT(1) = 1
    ) AS t;

Try this approach in the editor

Approach 4: Grouping and `CASE` Expression

Similar to Solution 1, we can first group the MyNumbers table by num and count the number of occurrences of each number. Then, we can use a CASE expression to find the numbers that appear only once, sort them in descending order by number, and take the first one.

MySQL

# Write your MySQL query statement below
SELECT
    CASE
        WHEN COUNT(1) = 1 THEN num
        ELSE NULL
    END AS num
FROM MyNumbers
GROUP BY num
ORDER BY 1 DESC
LIMIT 1;

Try this approach in the editor

Complexity comparison

Approach	Complexity
Using HashMap/Dictionary for Count Tracking	Time Complexity: O(n) on average, O(n) in worst case due to dictionary operations. Space Complexity: O(n) for storing number counts in a dictionary.
Using Sorting for Efficient Search	Time Complexity: O(n log n) due to sorting. Space Complexity: O(1) as sorting is done in place.
Grouping and Subquery	–
Grouping and `CASE` Expression	–

Complexity analysis

Approach	Time	Space	When to Use
HashMap / Dictionary Frequency Count	O(n)	O(n)	General case when input is unsorted and fast lookup is needed
Sorting + Neighbor Check	O(n log n)	O(1) to O(n)	When the data is already sorted or when minimizing extra data structures

Frequently asked questions

Is Biggest Single Number easy or hard?

Biggest Single Number is classified as an Easy problem. The core idea is simple frequency counting using a hash map or identifying unique values after sorting, both of which are common beginner-level patterns in coding interviews.

Biggest Single Number Python/Java solution

In Python, use a dictionary or collections.Counter to count frequencies and then compute the maximum number with count 1. In Java, use a HashMap<Integer, Integer> to store counts and iterate through the entry set to find the largest key with value equal to one.

How to solve Biggest Single Number in O(n)?

Iterate through the numbers and store frequencies in a hash map where each number maps to its count. Then iterate through the map and track the maximum key whose value equals 1. Because both passes are linear and hash lookups are constant time, the overall complexity remains O(n).

What is the best approach for Biggest Single Number?

The most efficient approach uses a hash map (dictionary) to count the frequency of each number. After counting, iterate through the map and select the largest value with frequency equal to 1. This method runs in O(n) time with O(n) space and works for any unsorted dataset.

Is Biggest Single Number asked at Google/Amazon/Meta?

Problems involving frequency counting and identifying unique elements are common in interviews at companies like Amazon, Google, and Meta. While this exact question is from a database-focused problem set, the underlying pattern using hash maps frequently appears in coding interviews.

What data structure is used in Biggest Single Number?

A hash map (dictionary) is the primary data structure used to store the frequency of each number. It allows constant-time insertion and lookup, making it ideal for counting occurrences and quickly identifying numbers that appear exactly once.

What is the time complexity of Biggest Single Number?

The optimal solution runs in O(n) time using a hash map to count occurrences and then scanning the map for the largest unique value. A sorting-based alternative takes O(n log n) time because the array must be sorted before checking for unique elements.

Biggest Single Number solution and explanation

The problem

Approach overview

Approach 1: Using HashMap/Dictionary for Count Tracking

Approach 2: Using Sorting for Efficient Search

Approach 3: Grouping and Subquery

Approach 4: Grouping and `CASE` Expression

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Biggest Single Number solution and explanation

The problem

Approach overview

Approach 1: Using HashMap/Dictionary for Count Tracking

Approach 2: Using Sorting for Efficient Search

Approach 3: Grouping and Subquery

Approach 4: Grouping and `CASE` Expression

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems