Skip to main content
Talentd

Find the Subtasks That Did Not Execute - Solution & Explanation

HardPremiumFree on FleetCodeDatabase4 min readAsked at: Google
Practice this problem

Problem Statement

Table: Tasks

+----------------+---------+
| Column Name    | Type    |
+----------------+---------+
| task_id        | int     |
| subtasks_count | int     |
+----------------+---------+
task_id is the column with unique values for this table.
Each row in this table indicates that task_id was divided into subtasks_count subtasks labeled from 1 to subtasks_count.
It is guaranteed that 2 <= subtasks_count <= 20.

 

Table: Executed

+---------------+---------+
| Column Name   | Type    |
+---------------+---------+
| task_id       | int     |
| subtask_id    | int     |
+---------------+---------+
(task_id, subtask_id) is the combination of columns with unique values for this table.
Each row in this table indicates that for the task task_id, the subtask with ID subtask_id was executed successfully.
It is guaranteed that subtask_id <= subtasks_count for each task_id.

 

Write a solution to report the IDs of the missing subtasks for each task_id.

Return the result table in any order.

The result format is in the following example.

 

Example 1:

Input: 
Tasks table:
+---------+----------------+
| task_id | subtasks_count |
+---------+----------------+
| 1       | 3              |
| 2       | 2              |
| 3       | 4              |
+---------+----------------+
Executed table:
+---------+------------+
| task_id | subtask_id |
+---------+------------+
| 1       | 2          |
| 3       | 1          |
| 3       | 2          |
| 3       | 3          |
| 3       | 4          |
+---------+------------+
Output: 
+---------+------------+
| task_id | subtask_id |
+---------+------------+
| 1       | 1          |
| 1       | 3          |
| 2       | 1          |
| 2       | 2          |
+---------+------------+
Explanation: 
Task 1 was divided into 3 subtasks (1, 2, 3). Only subtask 2 was executed successfully, so we include (1, 1) and (1, 3) in the answer.
Task 2 was divided into 2 subtasks (1, 2). No subtask was executed successfully, so we include (2, 1) and (2, 2) in the answer.
Task 3 was divided into 4 subtasks (1, 2, 3, 4). All of the subtasks were executed successfully.

Approach Overview

Problem Overview: Each task has a subtasks_count, meaning subtasks are numbered from 1 to subtasks_count. The Executed table records which subtasks actually ran. Your job is to return every (task_id, subtask_id) pair that should exist but does not appear in the execution log.

Approach 1: Recursive Table Generation + LEFT JOIN (O(T * S) time, O(T * S) space)

This approach constructs the complete list of expected subtasks first, then removes the ones that executed. Use a recursive common table expression (CTE) to generate subtask numbers from 1 up to the maximum subtasks_count. Join this generated sequence with the Tasks table so each task expands into its valid subtask range. This effectively creates the full expected set of (task_id, subtask_id) pairs.

Next, perform a LEFT JOIN between this generated dataset and the Executed table on both task_id and subtask_id. Rows where the execution side is NULL represent subtasks that never ran. This pattern—generate the full search space and filter missing rows—is common in SQL and database problems involving gaps or missing records.

The key insight is that the database does not store the missing subtasks explicitly. You must derive the expected rows first. Recursive CTEs make this possible by iteratively building a numeric sequence inside the query. The complexity is proportional to the total number of generated subtasks across all tasks. For typical constraints this remains efficient because the generation is linear.

This solution also keeps the logic entirely in SQL. No procedural loops are required. Databases optimize joins and filtering well, so the query stays readable and performant.

Recommended for interviews: Interviewers expect a solution that first generates the complete subtask range and then detects missing entries with a LEFT JOIN. Recursive CTE generation shows strong understanding of recursion in SQL and how to model implicit data. Simpler brute-force enumeration demonstrates the idea, but the recursive CTE version is the clean and scalable approach typically discussed in system design and database interviews.

Solution

We can generate a table recursively that contains all pairs of (parent task, child task), and then use a left join to find the pairs that have not been executed.

Code

MySQL

MySQL

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Manual Number Table + LEFT JOINO(T * S)O(S)When a prebuilt numbers table already exists in the database
Recursive CTE Generation + LEFT JOINO(T * S)O(T * S)General SQL solution when no numbers table exists; commonly used in MySQL and interview settings

Video Solution

GOOGLE LeetCode Hard 1767 “Subtasks That Did Not Execute" Interview SQL Question Explanation | EDS • Everyday Data Science • 2,496 views views

Watch 1 more video solutions →

Frequently Asked Questions

Is Find the Subtasks That Did Not Execute easy or hard?
The problem is rated Hard because it requires generating implicit rows that do not exist in the database. You must understand recursive CTEs, sequence generation, and join-based gap detection. Developers comfortable with advanced SQL patterns usually solve it quickly, but it can be tricky for beginners.
Find the Subtasks That Did Not Execute Python/Java solution
This problem is designed for SQL rather than Python or Java. The intended solution runs directly in the database using recursive CTE generation and a LEFT JOIN. Application languages would typically just execute the SQL query and return the result set.
How to solve Find the Subtasks That Did Not Execute in O(n)?
Treat the total number of expected subtasks as n. Use a recursive CTE to generate subtask IDs from 1 to subtasks_count, join them with Tasks to create the expected dataset, then LEFT JOIN with Executed. Filtering rows where Executed.subtask_id is NULL returns the missing subtasks in linear time relative to the generated rows.
What is the best approach for Find the Subtasks That Did Not Execute?
The most reliable approach generates the full list of expected subtasks and then filters the missing ones using a LEFT JOIN. A recursive CTE creates numbers from 1 to subtasks_count for each task, forming all possible (task_id, subtask_id) pairs. Joining this set with the Executed table and selecting rows where the execution record is NULL reveals the subtasks that never ran.
What data structure is used in Find the Subtasks That Did Not Execute?
The solution relies on relational database structures rather than traditional in-memory data structures. Key SQL concepts include recursive common table expressions (CTEs), joins, and set-based filtering. The generated sequence behaves like a temporary numbers table used to enumerate subtask IDs.
What is the time complexity of Find the Subtasks That Did Not Execute?
The time complexity is O(T * S), where T is the number of tasks and S is the average number of subtasks per task. The recursive CTE generates all required subtask numbers and the database performs a join against the Executed table. Space complexity is also O(T * S) because the generated subtask combinations must exist temporarily during query execution.
Is Find the Subtasks That Did Not Execute asked at Google, Amazon, or Meta?
Database gap-detection problems like this appear frequently in SQL interview rounds at companies such as Amazon, Google, and Meta. Candidates are often asked to identify missing records, generate sequences, or compare expected versus actual data using joins and window logic.

Ready to solve this problem?

Practice Find the Subtasks That Did Not Execute with our built-in code editor and test cases.

Practice on FleetCode
Previous

Combine Two Tables

Next

Second Highest Salary