Definition
- Order recording – append each task to an order list as it is removed from the queue during Kahn's algorithm.
- Correctness guarantee – a task enters the queue only when all its prerequisites are placed, so the removal order respects every dependency.
- Cycle detection – if the order list is shorter than the total task count, a cycle exists and an empty list signals impossibility.
- Multiple valid orders – the algorithm returns one valid order; others may exist depending on queue ordering.
- Linear time – O(V + E) because each task and edge is processed exactly once.
The National Bank of India needs an actual step-by-step onboarding playbook where document verification precedes account opening and account opening precedes card issuance. Tasks Scheduling Order gives that playbook by listing tasks in a sequence that always respects prerequisites.
Understanding the Concepts
What is the Tasks Scheduling Order problem?
Given a number of tasks and prerequisite pairs, return one valid order in which all tasks can be completed. If no valid order exists (due to a cycle), return an empty list. This extends the feasibility variant by recording the actual sequence.
package com.bank.onboarding;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class TaskSchedulingOrder {
public static List<Integer> findOrder(int taskCount, int[][] prerequisites) {
List<List<Integer>> adj = new ArrayList<>();
int[] inDegree = new int[taskCount];
for (int i = 0; i < taskCount; i++) adj.add(new ArrayList<>());
for (int[] pre : prerequisites) {
adj.get(pre[0]).add(pre[1]);
inDegree[pre[1]]++;
}
Queue<Integer> queue = new LinkedList<>();
for (int i = 0; i < taskCount; i++) {
if (inDegree[i] == 0) queue.add(i);
}
List<Integer> order = new ArrayList<>();
while (!queue.isEmpty()) {
int task = queue.poll();
order.add(task); // record the order
for (int next : adj.get(task)) {
if (--inDegree[next] == 0) {
queue.add(next);
}
}
}
return order.size() == taskCount ? order : new ArrayList<>();
}
}
How does recording the order differ from the feasibility check?
The feasibility variant just counts placed tasks and returns a boolean. The order variant replaces the counter with a list that records each task as it leaves the queue. The rest of the algorithm is identical. This list is the topological order.
// Feasibility: placed++; ... return placed == taskCount;
// Order: order.add(task); ... return order.size() == taskCount ? order : empty;
Why is the removal order a valid completion order?
A task enters the queue only when its in-degree reaches 0, meaning all its prerequisites have already been removed and placed in the order. So every task in the order appears after all its prerequisites, which is exactly the definition of a valid topological order.
package com.bank.onboarding;
public class OrderCorrectnessDemo {
public static void demonstrate() {
// Prerequisites: 0->1, 0->2, 1->3, 2->3
// Task 0 has no prerequisites → enters queue first
// Tasks 1,2 wait for 0 → enter after 0 is placed
// Task 3 waits for 1 and 2 → enters after both are placed
// Order: [0, 1, 2, 3] or [0, 2, 1, 3] (both valid)
System.out.println(TaskSchedulingOrder.findOrder(4,
new int[][]{{0,1},{0,2},{1,3},{2,3}}));
}
}
[0, 1, 2, 3]
What happens when a cycle exists?
When a cycle exists, tasks in the cycle never reach in-degree 0, so they never enter the queue and never get placed. The order list ends up shorter than the total task count, and we return an empty list.
package com.bank.onboarding;
public class CycleDemo {
public static void demonstrate() {
// Cycle: 0->1, 1->2, 2->0
// In-degrees: [1, 1, 1] → no task has in-degree 0!
// Queue is empty from the start
// Order: [] (empty), order.size()=0 != 3 → return empty
System.out.println(TaskSchedulingOrder.findOrder(3,
new int[][]{{0,1},{1,2},{2,0}})); // []
}
}
[]
Why can multiple valid orders exist?
When multiple tasks have in-degree 0 at the same time, any of them can be processed next. The queue ordering (FIFO) picks one, but a different ordering would also be valid. For example, with prerequisites 0->2 and 1->2, both orders [0, 1, 2] and [1, 0, 2] are valid.
package com.bank.onboarding;
public class MultipleOrders {
public static void demonstrate() {
// Prerequisites: 0->2, 1->2
// Both 0 and 1 have in-degree 0
// FIFO queue: processes 0 first, then 1, then 2
// But [1, 0, 2] is equally valid
System.out.println(TaskSchedulingOrder.findOrder(3,
new int[][]{{0,2},{1,2}})); // [0, 1, 2]
}
}
[0, 1, 2]
What is the time and space complexity?
| Aspect | Complexity | Notes |
|---|---|---|
| Time | O(V + E) | Each task and edge processed once |
| Space | O(V + E) | Adjacency list + in-degree array + queue + order list |
What are edge cases?
Edge cases include zero tasks (return empty list), tasks with no prerequisites (return any permutation), and a single task (return [0]).
package com.bank.onboarding;
public class EdgeCases {
public static void test() {
System.out.println(TaskSchedulingOrder.findOrder(0, new int[][]{})); // []
System.out.println(TaskSchedulingOrder.findOrder(3, new int[][]{})); // [0, 1, 2]
System.out.println(TaskSchedulingOrder.findOrder(1, new int[][]{})); // [0]
}
}
[]
[0, 1, 2]
[0]
What are common mistakes?
The most common mistake is returning the incomplete order instead of empty when a cycle is detected. Another mistake is not handling the case where the task count is zero.
package com.bank.onboarding;
public class CommonMistakes {
// WRONG: returning incomplete order when cycle exists
// If order.size() < taskCount, returning order gives a partial result
// Fix: check order.size() == taskCount before returning
// WRONG: not handling zero tasks
// taskCount=0 should return [] (empty, but valid)
}
How is this used in banking?
At the National Bank of India, the onboarding team generates a corporate onboarding playbook where document verification precedes account opening, account opening precedes card issuance, and KYC precedes loan review. The operations team needs the ordered steps, not just a yes/no feasibility answer.
package com.bank.onboarding;
import java.util.List;
public class OnboardingPlaybook {
public static void main(String[] args) {
// 0: KYC Verification
// 1: Account Opening
// 2: Card Issuance
// 3: Loan Review
int[][] prerequisites = {{0,1}, {1,2}, {0,3}};
List<Integer> order = TaskSchedulingOrder.findOrder(4, prerequisites);
String[] taskNames = {"KYC Verification", "Account Opening",
"Card Issuance", "Loan Review"};
System.out.println("Onboarding playbook:");
for (int i = 0; i < order.size(); i++) {
System.out.println((i + 1) + ". " + taskNames[order.get(i)]);
}
}
}
Onboarding playbook:
1. KYC Verification
2. Account Opening
3. Loan Review
4. Card Issuance
Visual Overview
Kahn's Algorithm with Order Recording
=======================================
Tasks: 0(KYC), 1(Account), 2(Card), 3(Loan)
Prereqs: 0→1, 1→2, 0→3
In-degree: [0, 1, 1, 1]
Queue: [0]
Process 0: order=[0]
├── Reduce 1: 1→0 → enqueue
└── Reduce 3: 1→0 → enqueue
Queue: [1, 3]
Process 1: order=[0, 1]
└── Reduce 2: 1→0 → enqueue
Queue: [3, 2]
Process 3: order=[0, 1, 3]
Queue: [2]
Process 2: order=[0, 1, 3, 2]
Queue: []
order.size()=4 == taskCount=4 → Return [0, 1, 3, 2]
Playbook:
┌─────┐ ┌─────┐ ┌─────┐ ┌─────┐
│ KYC │──►│Acct │──►│Card │ │Loan │
└──┬──┘ └─────┘ └─────┘ └─────┘
│ ▲
└──────────────────────────────┘
Feasibility vs Order
=====================
┌─────────────────────┬───────────────────────┐
│ Feasibility │ Order │
├─────────────────────┼───────────────────────┤
│ placed++ counter │ order.add(task) list │
│ Return boolean │ Return list or empty │
│ Same algorithm │ Same algorithm │
└─────────────────────┴───────────────────────┘
Key Takeaway
Tasks Scheduling Order is the order-producing variant of the Topological Sort pattern. You run Kahn's algorithm exactly as for the feasibility check, but instead of counting placed tasks you record each removed task in an order list. A task only enters the queue when all its prerequisites have been placed, so the removal order is guaranteed to respect every dependency.
If the order list ends up shorter than the total task count, a cycle existed and you return an empty list. Otherwise the list is a valid completion order. Multiple valid orders may exist because when several tasks have in-degree 0 simultaneously, any can be chosen next.
At the National Bank of India, the onboarding team used this to generate a step-by-step playbook for corporate clients, where document verification had to precede account opening and account opening had to precede card issuance. The operations team needed the actual ordered steps, not just a feasibility answer.
The algorithm is linear in the number of tasks plus prerequisites. The key difference from the feasibility variant is one line: replacing a counter with an order list that captures the removal sequence.
Remember one sentence: the order in which Kahn's algorithm removes tasks is a valid completion order; return it if complete, empty if a cycle blocks it.
---