What is the brute force approach and complexity for All Tasks Scheduling Orders?

Build all n! orders; keep each one where every pair has its first task before its second with time complexity O(N! · (N + E)) and space complexity O(N).

What is the optimal approach and complexity for All Tasks Scheduling Orders?

Kahn's free tasks as branches; place, recurse, then undo; keep every complete order with optimal time complexity O(N · N!) and space complexity O(N + E).

How do you identify the pattern for All Tasks Scheduling Orders?

Look for key signals in the prompt: "return all orders" indicates Not one order: keep searching after each full order, which is backtracking.; "tasks with prerequisites" indicates Each task waits for others, so track the in-degree and use Kahn's free tasks.; "n tasks, so n! orders" indicates The output can be huge, so the search should only explore valid picks..

All Tasks Scheduling Orders

Hard·Educative Pro OnlyMedium

Educative

Problem Statement

There are n tasks, numbered 0 to n − 1. Some tasks must be done before others. You get a list of pairs [a, b], which means task a must be done before task b.

Return every order in which all the tasks can be done, so that every pair is respected. The order of the orders in your answer does not matter.

If the pairs contradict each other (for example, a cycle), no order works, so return an empty list.

Input

n: the number of tasks. prereqs: a list of pairs [a, b] meaning a must be done before b.

Output

A list of orders. Each order is a list with all n task numbers, each once.

Example 1

Input: n = 3, prereqs = [[0, 1]]

Output: [[0, 1, 2], [0, 2, 1], [2, 0, 1]]

0 must come before 1. Task 2 has no rule, so it can go in any of the three places that keep 0 before 1.

Example 2

Input: n = 3, prereqs = [[0, 1], [1, 2]]

Output: [[0, 1, 2]]

0, then 1, then 2 is the only chain. There is one order.

Example 3

Input: n = 2, prereqs = [[0, 1], [1, 0]]

Output: []

0 before 1 and 1 before 0 cannot both hold, so no order exists.

Constraints

• Every value in a pair is between 0 and n − 1.
• A pair can repeat, and a pair may be empty (no prerequisites at all).

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“return all orders”

→ Not one order: keep searching after each full order, which is backtracking.

“tasks with prerequisites”

→ Each task waits for others, so track the in-degree and use Kahn's free tasks.

“n tasks, so n! orders”

→ The output can be huge, so the search should only explore valid picks.

Approach Complexity Ladder

Brute Force — try every order, keep the valid onesO(N! · (N + E))O(N)

Build all n! orders; keep each one where every pair has its first task before its second

Optimal — backtracking on KahnO(N · N!)O(N + E)

Kahn's free tasks as branches; place, recurse, then undo; keep every complete order

Brute Force Intuition

An order of all the tasks is a permutation of 0..n − 1. Generate every permutation. For each one, check that every pair [a, b] has a before b. Keep the permutations that pass.

Recognition rule for this sub-pattern:

The graph is hidden — derive edges from comparisons (adjacent words, sequences), then topo-sort.

Remember this · Topological Sort

Trigger

Prerequisites, dependencies, build order, "can all courses be finished?", ordering letters from sorted words.

Think

Is this a directed graph where some things must happen before others?

Key question

Which nodes currently have in-degree 0?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Topological Sort translate into production architectures and low-level memory mechanics.

LLD Practice

Task Scheduler & Workflow Orchestrator

Resolving DAG build pipelines and asynchronous task dependency resolution.

Explore Track

C++ Internals

Static vs Global Linkage & Init Order Fiasco

Why compilers resolve static global variables as a DAG to prevent runtime crashes.

Explore Track

Sequence Reconstruction