Skip to content

1767. Find The Subtasks That Did Not Execute

Summary

The solution uses a recursive Common Table Expression (CTE) to generate all possible subtasks for each task, then filters out the ones that were executed.

The recursive CTE works in two parts:

  1. Base case: Start with the original tasks table, which contains each task and its maximum subtask_id
  2. Recursive case: For each task, generate all subtasks by decrementing the subtask_id until it reaches 1

This creates a complete set of all possible (task_id, subtask_id) pairs. Finally, we use a NOT IN clause to exclude the subtasks that appear in the executed table, leaving only the subtasks that did not execute.

See Work with recursive CTEs in BigQuery for more details on recursive CTEs.

Implementation

with recursive task_subtasks (task_id, subtask_id) as (
    select
        *
    from tasks

    union

    select
        task_id,
        subtask_id - 1
    from task_subtasks
    where subtask_id > 1
)

select
    task_id,
    subtask_id
from task_subtasks
where (task_id, subtask_id) not in (
    select
        *
    from executed
)