LeetCode 619 - Biggest Single Number

The problem gives us a database table named MyNumbers that contains a single column, num. The table may contain duplicate values because there is no primary key restriction. Our task is to find the largest number that appears exactly once in the table.

leetcodeeasydatabase

LeetCode Problem 619

Difficulty: 🟢 Easy
Topics: Database

Solution

Problem Understanding

The problem gives us a database table named MyNumbers that contains a single column, num. The table may contain duplicate values because there is no primary key restriction. Our task is to find the largest number that appears exactly once in the table.

A number is considered a "single number" if its frequency in the table is exactly one. If multiple numbers satisfy this condition, we must return the largest among them. If no number appears exactly once, the query should return null.

The input is not provided as arrays or objects like traditional algorithm problems. Instead, the input is represented as rows in a SQL table. Each row contains one integer value. The output is expected to be a single-row table with one column named num.

For example, if the table contains:

| num |

|---|---|

| 1 |

| 2 |

| 2 |

| 5 |

then 1 and 5 are single numbers because they each appear once. Since 5 is larger, the result should be:

| num |

|---|---|

| 5 |

An important detail is that the result must still contain a row even when no valid number exists. In that case, SQL should return null.

The problem constraints are small and straightforward because this is primarily a SQL aggregation problem. The key operation is counting how many times each number appears.

There are several important edge cases:

  • Every number appears multiple times, so the answer should be null.
  • Only one number exists in the table, making it automatically the largest single number.
  • Negative numbers could appear, so we cannot assume all values are positive.
  • Multiple unique values may exist, requiring us to select the maximum among them.
  • The table may contain many duplicates, so a naive repeated scan approach becomes inefficient.

Approaches

Brute Force Approach

A brute force solution would examine every distinct number individually and count how many times it appears in the table using a nested query.

Conceptually, the algorithm would work like this:

  1. Iterate through every distinct number.
  2. For each number, scan the entire table again to count occurrences.
  3. Keep track of numbers whose count equals one.
  4. Return the maximum among them.

This approach is correct because it explicitly verifies the frequency of every number. However, it is inefficient because the table may be scanned repeatedly for every distinct value.

If there are n rows and many unique numbers, the repeated counting operation leads to quadratic behavior.

Optimal Approach

The better solution uses SQL aggregation functions.

The key insight is that SQL already provides efficient grouping and counting operations through GROUP BY and COUNT. Instead of repeatedly scanning the table, we can compute frequencies for all numbers in a single aggregation pass.

The optimized process is:

  1. Group rows by num.
  2. Count how many times each number appears.
  3. Filter groups whose count equals one using HAVING.
  4. Select the maximum value among the remaining numbers.

This is efficient because the counting work is centralized into one grouped aggregation instead of repeated scans.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Repeatedly scans the table for each number
Optimal O(n) O(n) Uses SQL aggregation with GROUP BY and COUNT

Algorithm Walkthrough

Optimal SQL Algorithm

  1. Group all rows by the num column.

This step collects identical numbers together so we can compute their frequencies efficiently. 2. Count how many rows belong to each group.

Using COUNT(*), we determine how many times each number appears in the table. 3. Filter groups whose frequency is exactly one.

The HAVING COUNT(*) = 1 clause removes all duplicated numbers and keeps only single numbers. 4. Compute the maximum remaining number.

Among all valid single numbers, we select the largest one using the MAX() aggregate function. 5. Return the result.

If no valid rows remain after filtering, MAX() naturally returns NULL, which matches the problem requirement.

Why it works

The algorithm works because grouping partitions the table into sets of identical numbers. The count of each group exactly represents the frequency of that number in the table. Filtering by COUNT(*) = 1 guarantees that only single numbers remain. Taking the maximum of those remaining values therefore produces the largest single number.

Python Solution

Although this is a SQL problem, LeetCode database problems are typically solved directly with SQL. There is no actual Python class stub for execution. Still, for completeness, here is the SQL query represented inside a Python string.

query = """
SELECT MAX(num) AS num
FROM (
    SELECT num
    FROM MyNumbers
    GROUP BY num
    HAVING COUNT(*) = 1
) AS single_numbers;
"""

The query works in two stages.

The inner query groups the table by num and filters out every number whose frequency is not exactly one. After this step, only valid single numbers remain.

The outer query applies MAX(num) to retrieve the largest single number. If the inner query returns no rows, MAX() automatically returns NULL.

Go Solution

As with the Python section, database problems on LeetCode are solved using SQL rather than Go. For completeness, here is the SQL query represented as a Go string.

package main

func main() {
	query := `
SELECT MAX(num) AS num
FROM (
    SELECT num
    FROM MyNumbers
    GROUP BY num
    HAVING COUNT(*) = 1
) AS single_numbers;
`
	_ = query
}

The Go version simply stores the SQL query as a raw string literal. The actual logic remains entirely inside SQL.

One small Go-specific detail is the use of backticks for multiline raw strings, which avoids escaping quotation marks or newline characters.

Worked Examples

Example 1

Input table:

| num |

|---|---|

| 8 |

| 8 |

| 3 |

| 3 |

| 1 |

| 4 |

| 5 |

| 6 |

Step 1, Group and count frequencies

num count
8 2
3 2
1 1
4 1
5 1
6 1

Step 2, Keep only single numbers

num count
1 1
4 1
5 1
6 1

Step 3, Take the maximum

MAX(1, 4, 5, 6) = 6

Final output:

| num |

|---|---|

| 6 |

Example 2

Input table:

| num |

|---|---|

| 8 |

| 8 |

| 7 |

| 7 |

| 3 |

| 3 |

| 3 |

Step 1, Group and count frequencies

num count
8 2
7 2
3 3

Step 2, Keep only single numbers

No rows remain because every number appears more than once.

Step 3, Take the maximum

Since there are no valid rows, MAX() returns NULL.

Final output:

| num |

|---|---|

| null |

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each row is processed during grouping and counting
Space O(n) The grouping operation may store counts for all distinct numbers

The time complexity is linear because the database engine scans the table once while building grouped frequency counts. The space complexity depends on how many distinct numbers exist because the database must maintain aggregation data for each unique value.

Test Cases

# Example 1: multiple single numbers
assert largest_single([8, 8, 3, 3, 1, 4, 5, 6]) == 6

# Example 2: no single numbers
assert largest_single([8, 8, 7, 7, 3, 3, 3]) is None

# Single element table
assert largest_single([10]) == 10

# All elements unique
assert largest_single([1, 2, 3, 4]) == 4

# Negative numbers
assert largest_single([-1, -2, -2, -3]) == -1

# Mixed duplicates and singles
assert largest_single([5, 5, 4, 4, 9, 1]) == 9

# Large duplicate count
assert largest_single([2, 2, 2, 2, 3]) == 3

# No valid single after filtering
assert largest_single([1, 1, 2, 2]) is None
Test Why
[8, 8, 3, 3, 1, 4, 5, 6] Validates standard mixed input
[8, 8, 7, 7, 3, 3, 3] Validates null output when no single number exists
[10] Validates single-row input
[1, 2, 3, 4] Validates all unique values
[-1, -2, -2, -3] Validates handling of negative numbers
[5, 5, 4, 4, 9, 1] Validates choosing the maximum single number
[2, 2, 2, 2, 3] Validates heavy duplication
[1, 1, 2, 2] Validates complete elimination after filtering

Edge Cases

No Single Numbers Exist

One of the most important edge cases occurs when every number appears multiple times. A naive implementation might accidentally return 0, an empty row, or fail entirely. The SQL solution handles this naturally because MAX() applied to an empty result set returns NULL.

Only One Row in the Table

If the table contains exactly one row, that number automatically appears once and must be returned. Some incorrect solutions overcomplicate the counting logic and fail on minimal inputs. The grouping approach works correctly because the single group has a count of one.

Multiple Single Numbers

Another subtle case occurs when several numbers appear exactly once. The problem specifically asks for the largest single number, not just any valid number. The use of MAX(num) guarantees that the highest valid value is selected correctly.

Negative Values

Although examples only show positive integers, SQL integer columns may contain negative numbers. An incorrect implementation might initialize the answer with 0, which would fail if all numbers are negative. Using SQL's MAX() directly avoids this issue because it correctly compares all integer values regardless of sign.