Definition
- Feasibility check – the question is whether all tasks can be completed, not what order to complete them in.
- Cycle detection – a cycle in the prerequisite graph means some tasks mutually depend on each other and can never start.
- Kahn's algorithm – count in-degrees, enqueue tasks with in-degree 0, process the queue, and check if all tasks were placed.
- In-degree – the number of prerequisites a task has; a task can start only when its in-degree reaches 0.
- Linear time – O(V + E) because each task and each edge is processed exactly once.
The National Bank of India wants to know whether a set of compliance tasks with prerequisite dependencies can all be completed, or whether a circular dependency would cause a deadlock. Tasks Scheduling answers yes or no by checking whether a safe order covering every task exists.
Understanding the Concepts
What is the Tasks Scheduling problem?
Given a number of tasks (numbered 0 to n-1) and a list of prerequisite pairs where [a, b] means task a must be completed before task b, determine whether it is possible to finish all tasks. This is the feasibility variant of topological sort.
package com.bank.compliance;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
public class TaskScheduling {
public static boolean canFinishAll(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);
}
int placed = 0;
while (!queue.isEmpty()) {
int task = queue.poll();
placed++;
for (int next : adj.get(task)) {
if (--inDegree[next] == 0) {
queue.add(next);
}
}
}
return placed == taskCount;
}
}
Why does the placed count detect cycles?
If a cycle exists, the tasks inside the cycle never reach in-degree 0 because they are waiting on each other. They never enter the queue, so the placed count stays below the total task count. If no cycle exists, every task eventually reaches in-degree 0 and gets placed, so the count equals the total.
package com.bank.compliance;
public class CycleDetectionDemo {
public static void demonstrate() {
// No cycle: 0->1, 0->2, 1->3
// In-degrees: [0, 1, 1, 1]
// Queue starts: [0]
// Process 0: place 0, reduce 1 and 2 → queue: [1, 2]
// Process 1: place 1, reduce 3 → queue: [2, 3]
// Process 2: place 2 → queue: [3]
// Process 3: place 3 → queue: []
// placed=4 == taskCount=4 → true
System.out.println(TaskScheduling.canFinishAll(4,
new int[][]{{0,1},{0,2},{1,3}})); // true
// Cycle: 0->1, 1->0
// In-degrees: [1, 1]
// Queue starts: [] (no task has in-degree 0!)
// placed=0 != taskCount=2 → false
System.out.println(TaskScheduling.canFinishAll(2,
new int[][]{{0,1},{1,0}})); // false
}
}
true
false
How does Kahn's algorithm work step by step?
Build the adjacency list and in-degree array from the prerequisite pairs. Enqueue every task with in-degree 0 (no prerequisites). Process the queue: for each removed task, increment the placed count and decrement the in-degree of all its dependents. If a dependent's in-degree reaches 0, enqueue it. When the queue is empty, compare the placed count to the total.
package com.bank.compliance;
public class KahnTrace {
public static void trace() {
// Tasks: 0, 1, 2, 3
// Prerequisites: 0->1, 0->2, 1->3, 2->3
// In-degrees: [0, 1, 1, 2]
// Queue: [0] (only task with in-degree 0)
// Process 0: placed=1, reduce in-degree of 1 and 2
// In-degrees: [0, 0, 0, 2] → enqueue 1 and 2
// Process 1: placed=2, reduce in-degree of 3
// In-degrees: [0, 0, 0, 1]
// Process 2: placed=3, reduce in-degree of 3
// In-degrees: [0, 0, 0, 0] → enqueue 3
// Process 3: placed=4
// placed=4 == taskCount=4 → true
}
}
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 |
What are edge cases?
Edge cases include zero tasks (trivially true), tasks with no prerequisites (all can start immediately), a self-loop (task depends on itself, impossible), and disconnected components (each component is checked independently by Kahn's).
package com.bank.compliance;
public class EdgeCases {
public static void test() {
// Zero tasks
System.out.println(TaskScheduling.canFinishAll(0, new int[][]{})); // true
// No prerequisites: all tasks independent
System.out.println(TaskScheduling.canFinishAll(3, new int[][]{})); // true
// Self-loop: task 0 depends on itself
System.out.println(TaskScheduling.canFinishAll(1, new int[][]{{0,0}})); // false
}
}
true
true
false
How is this different from the DFS cycle detection approach?
Kahn's algorithm (BFS-based) counts placed tasks and checks if all were reached. An alternative DFS-based approach marks nodes as visiting/visited and detects a back edge as a cycle. Both are O(V + E), but Kahn's is more intuitive for topological sort problems and naturally extends to the order-producing variant.
// Kahn's (BFS): count placed tasks, check placed == total
// DFS: track visiting state, back edge = cycle
// Both: O(V + E) time, O(V + E) space
// Kahn's advantage: naturally produces the topological order
// DFS advantage: can also find strongly connected components
What are common mistakes?
The most common mistake is forgetting to handle disconnected components. Kahn's algorithm handles this naturally because every component contributes tasks with in-degree 0 to the initial queue. Another mistake is modelling the edge direction wrong: [a, b] means a is a prerequisite of b, so the edge goes from a to b.
package com.bank.compliance;
public class CommonMistakes {
// WRONG: edge direction reversed
// [a, b] means a before b, so edge a->b, not b->a
// Reversing causes wrong in-degree counts and wrong results
// WRONG: using adjacency matrix for sparse graphs
// O(V^2) space instead of O(V + E)
// Fix: use adjacency list
}
How is this used in banking?
At the National Bank of India, the compliance team checks whether all regulatory tasks can be completed given their dependencies. If two tasks mutually depend on each other, the whole compliance workflow deadlocks and needs redesigning. Kahn's algorithm detects such cycles by comparing the placed count to the total task count.
package com.bank.compliance;
public class ComplianceCheck {
public static void main(String[] args) {
int[][] prerequisites = {
{0, 1}, // KYC verification before account opening
{1, 2}, // Account opening before card issuance
{0, 3} // KYC verification before loan review
};
boolean canComplete = TaskScheduling.canFinishAll(4, prerequisites);
System.out.println("All compliance tasks completable: " + canComplete);
}
}
All compliance tasks completable: true
Visual Overview
Kahn's Algorithm Flow
======================
Tasks: 0, 1, 2, 3
Prerequisites: 0→1, 0→2, 1→3, 2→3
In-degree: [0, 1, 1, 2]
Initial queue: [0] (in-degree 0)
Process 0: placed=1
├── Reduce 1: in-degree 1→0 → enqueue
└── Reduce 2: in-degree 1→0 → enqueue
Queue: [1, 2]
Process 1: placed=2
└── Reduce 3: in-degree 2→1
Queue: [2]
Process 2: placed=3
└── Reduce 3: in-degree 1→0 → enqueue
Queue: [3]
Process 3: placed=4
Queue: []
placed (4) == taskCount (4) → All tasks can finish!
Cycle Example
==============
Tasks: 0, 1 Prerequisites: 0→1, 1→0
In-degree: [1, 1]
Initial queue: [] (no task has in-degree 0!)
placed=0 != taskCount=2 → CYCLE! Cannot finish.
┌───┐ ┌───┐
│ 0 │ ───► │ 1 │
│ │ ◄─── │ │
└───┘ └───┘
Mutual dependency = deadlock
Key Takeaway
Tasks Scheduling is the feasibility variant of the Topological Sort pattern. The question is whether all tasks can be completed given their prerequisites, and the answer is yes if and only if the prerequisite graph has no cycle. You run Kahn's algorithm: model each prerequisite as a directed edge, build the in-degree array, enqueue tasks with in-degree 0, and process the queue by placing each task and decrementing its dependents' in-degrees.
The entire decision comes down to the placed count. If you place every task, the graph is acyclic and all tasks can finish. If tasks remain with non-zero in-degree after the queue empties, those tasks are caught in a cycle and can never start. The algorithm is linear in the number of tasks plus prerequisites.
At the National Bank of India, the compliance team used this to check whether all regulatory tasks could be completed given their prerequisite dependencies. If two tasks mutually depended on each other, the workflow would deadlock, and the team needed to know before execution. Kahn's placed-count check gave the answer instantly.
The key distinction from the order-producing variant is that here you return a boolean, not the actual sequence. The order variant records the removal sequence as the valid completion order.
Remember one sentence: run Kahn's algorithm and check whether the placed count equals the total task count; if it does, all tasks can finish, otherwise a cycle blocks completion.
---