Find the Missing IDs - Solution & Explanation

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.