Find the Missing IDs solution and explanation
2 more videos on this problem
The problem
Table: Customers
+---------------+---------+ | Column Name | Type | +---------------+---------+ | customer_id | int | | customer_name | varchar | +---------------+---------+ customer_id is the column with unique values for this table. Each row of this table contains the name and the id customer.
Write a solution to find the missing customer IDs. The missing IDs are ones that are not in the Customers table but are in the range between 1 and the maximum customer_id present in the table.
Notice that the maximum customer_id will not exceed 100.
Return the result table ordered by ids in ascending order.
The result format is in the following example.
Example 1:
Input: Customers table: +-------------+---------------+ | customer_id | customer_name | +-------------+---------------+ | 1 | Alice | | 4 | Bob | | 5 | Charlie | +-------------+---------------+ Output: +-----+ | ids | +-----+ | 2 | | 3 | +-----+ Explanation: The maximum customer_id present in the table is 5, so in the range [1,5], IDs 2 and 3 are missing from the table.
Approach overview
Problem Overview: The table contains customer IDs that should form a continuous sequence starting from 1, but some rows are missing. The task is to return every ID that does not appear in the table while staying within the existing ID range.
Approach 1: Recursive Sequence + LEFT JOIN (O(n) time, O(n) space)
The key idea is to generate the full sequence of expected IDs and compare it with the existing rows. In MySQL, a WITH RECURSIVE CTE builds numbers starting from 1 and continues until the maximum ID present in the table. After generating this sequence, perform a LEFT JOIN with the customer table and filter rows where the join result is NULL. Those represent IDs that were never inserted. This approach works well because it explicitly constructs the expected dataset, making the gap detection trivial. The recursive generation and join each scan roughly n elements, giving O(n) time complexity and O(n) auxiliary space for the generated sequence.
Approach 2: Numbers Table or Prebuilt Sequence (O(n) time, O(1) extra space)
If the database already has a numbers table (or a system table used to generate ranges), you can avoid recursion entirely. Join the numbers table containing values from 1 to MAX(id) against the customer table using a LEFT JOIN, then filter for rows where the customer ID is missing. This approach is common in production analytics environments where a permanent sequence table exists. Since the range is precomputed, the query mainly performs a scan and join operation, keeping time complexity around O(n) and requiring minimal additional memory.
Both strategies rely on the same insight: detecting gaps requires comparing the current dataset against the complete expected sequence. SQL itself does not naturally produce ranges, so the solution focuses on generating that sequence first, then using relational operations to expose the missing values.
Recommended for interviews: The recursive CTE solution is the most commonly expected answer. It demonstrates strong SQL fundamentals: sequence generation, recursion, and LEFT JOIN filtering. Interviewers want to see that you can model missing data problems by constructing the reference dataset first. Understanding this pattern is useful across many database and SQL problems, especially when working with sequences, logs, or ordered identifiers.
Solution
# Write your MySQL query statement below
WITH RECURSIVE
t AS (
SELECT
1 AS n
UNION ALL
SELECT
n + 1
FROM t
WHERE n < 100
)
SELECT
n AS ids
FROM t
WHERE
n < (
SELECT
MAX(customer_id)
FROM Customers
)
AND n NOT IN (
SELECT
customer_id
FROM Customers
);Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Recursive CTE + LEFT JOIN | O(n) | O(n) | General case in MySQL when you must generate the sequence dynamically |
| Numbers Table + LEFT JOIN | O(n) | O(1) | When a prebuilt numbers/sequence table already exists in the database |
Frequently asked questions
Is Find the Missing IDs easy or hard?
Find the Missing IDs is considered a Medium database problem. The challenge is recognizing that you must first generate the full ID range and then compare it with existing rows using joins or sequence generation.
Find the Missing IDs Python/Java solution
This problem is designed for SQL, but the same idea works in Python or Java by generating numbers from 1 to max_id and checking membership using a hash set. The algorithm still runs in O(n) time with O(n) space.
How to solve Find the Missing IDs in O(n)?
Generate a complete range of IDs using a recursive CTE starting from 1 up to MAX(id). Then LEFT JOIN this generated sequence with the customer table and filter rows where the customer ID is NULL. This linear scan approach identifies missing values efficiently.
What is the best approach for Find the Missing IDs?
The most common solution uses a recursive CTE to generate all IDs from 1 to the maximum ID in the table, then performs a LEFT JOIN with the existing records. Rows where the join result is NULL represent missing IDs. This approach runs in O(n) time and clearly exposes gaps in the sequence.
Is Find the Missing IDs asked at Google/Amazon/Meta?
Missing sequence or gap detection problems frequently appear in SQL interviews at companies like Amazon, Google, and Meta. Variations often involve detecting missing dates, order numbers, or user IDs using joins or window functions.
What data structure is used in Find the Missing IDs?
The solution relies on relational database operations rather than traditional data structures. It uses a generated numeric sequence combined with a LEFT JOIN to compare expected values against stored rows.
What is the time complexity of Find the Missing IDs?
The typical SQL solution runs in O(n) time where n is the maximum ID value. The recursive CTE generates n rows and the LEFT JOIN scans the dataset once to detect missing entries. Space complexity is O(n) due to the generated sequence.