016 — Course Schedule II

Source

• Original source: Classic topological-ordering (Kahn) exercise
• Platform: LeetCode — https://leetcode.com/problems/course-schedule-ii/
• Topic: graphs
• Difficulty: Medium
• Pattern: topological sort (Kahn's algorithm)
• Basic idea inherited from: Course Schedule (015-course-schedule.md, এই tracker-এর #15); topological sort (../topological-sort.md)

1. Problem in simple words

আগের মতোই numCourses টা কোর্স আর prerequisites জোড়া [a, b] ("a-এর আগে b করতেই হবে")। কিন্তু এবার শুধু "সম্ভব কিনা" নয় — সম্ভব হলে কোর্সগুলো করার একটা valid ক্রম ফেরত দাও (এমন একটা তালিকা যেখানে প্রতিটা কোর্সের আগে তার সব prerequisite আছে)। অসম্ভব হলে (চক্র থাকলে) খালি list []। এটাই topological sort — DAG-এর nodes-কে এমন এক লাইনে সাজানো যাতে প্রতিটা edge সামনের দিকে যায়।

prereq [1,0],[2,0],[3,1],[3,2]:
  0 আগে, তারপর 1 ও 2, তারপর 3
valid order: [0,1,2,3] (বা [0,2,1,3]) -> প্রতিটা কোর্সের আগে তার prereq

2. Which basic idea does this inherit from?

মূল ভিত হলো #15 Course Schedule (015-course-schedule.md) — সেই একই directed prerequisite graph, সেই একই চক্র-detection — কিন্তু এবার আমরা Kahn's algorithm ব্যবহার করি, যা চক্র ধরার পাশাপাশি আসল order produce করে। ../topological-sort.md-এ এটাই মূল কৌশল: indegree (unmet prerequisites) গোনো, যার indegree 0 তাকে এখনই নাও, তার outgoing edges সরাও, repeat। #15-এ যা ছিল হ্যাঁ/না, এখানে তা একটা সাজানো তালিকা।

3. What is the hidden math or logic?

লুকানো logic: কোনো node-এর indegree = তার দিকে আসা arrow-এর সংখ্যা = বাকি থাকা prerequisite-এর সংখ্যা। যার indegree 0, তাকে আটকানোর কিছু নেই — এখনই করা নিরাপদ। সেটা করলে তার outgoing arrows সরে যায়, যা নতুন কোর্স "মুক্ত" করতে পারে (তাদের indegree 0-তে নামে)। এভাবে layer-by-layer ছাড়াতে থাকো। যদি শেষে সব node বের হয়ে যায় — valid order পেলে; যদি কিছু আটকে থাকে (কেউ কখনো indegree 0-তে পৌঁছায় না) — সেগুলো একটা চক্রে, তাই কোনো order নেই।

4. Which data structure is needed?

• adjacency list — edge b -> a ("b শেষ হলে a unlock"); সাবধান, দিকটা।
• indegree array — প্রতিটা node-এর বাকি prerequisite সংখ্যা।
• collections.deque — যেসব node এখন করা যায় (indegree 0), তাদের queue।
• order list — চূড়ান্ত topological ক্রম।

5. Why this data structure fits

indegree array fit করে কারণ Kahn-এর পুরো logic একটাই গণনার উপর — "এই node-এর কয়টা prerequisite বাকি"; 0-তে নামা মানেই ready। deque (queue) fit করে কারণ ready-হওয়া node-গুলো FIFO-তে process করলেই হয় (order-এর uniqueness দরকার নেই, যেকোনো valid order চলবে), আর popleft/append দুটোই O(1)। adjacency list fit করে কারণ প্রতিটা node process করার সময় তার dependents-এর indegree কমাতে হয় — O(V + E)।

6. Real-life analogy

একটা বড় প্রকল্পের কাজগুলো সাজানো ভাবো, যেখানে কিছু কাজ অন্য কাজ শেষ না হলে শুরুই করা যায় না। প্রতিটা কাজের গায়ে লিখে রাখো "এর আগে আর কয়টা কাজ বাকি" (indegree)। যাদের গায়ে 0 — সেগুলো এখনই করতে পারো, করে ফেলো। প্রতিটা শেষ করা কাজ যেসব কাজকে আনলক করে, তাদের গায়ের সংখ্যা এক কমাও; নতুন কারো গায়ে 0 হলে সেও এখন করা যায়। সব কাজ এভাবে শেষ হলে তোমার হাতে একটা বৈধ কাজের ক্রম; কিছু কাজ চিরকাল 1-এ আটকে থাকলে বুঝবে বৃত্তাকার নির্ভরতা আছে।

7. Visual explanation

numCourses=4, prereq [[1,0],[2,0],[3,1],[3,2]] (edge b->a):

   0 ──> 1 ──┐
   │         v
   └──> 2 ──> 3        indegree: 0:0  1:1  2:1  3:2

queue=[0]            order=[]
pop 0 -> order=[0];  1:1->0 (enq), 2:1->0 (enq)   queue=[1,2]
pop 1 -> order=[0,1]; 3:2->1                        queue=[2]
pop 2 -> order=[0,1,2]; 3:1->0 (enq)               queue=[3]
pop 3 -> order=[0,1,2,3]   queue খালি, 4==4 -> valid

8. Example input and output

Input : numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]
Output: [0,1,2,3]      (বা [0,2,1,3] — দুটোই valid)

Input : numCourses=2, prerequisites=[[1,0]]
Output: [0,1]          (0-এর পরে 1)

Edge case (চক্র): numCourses=2, prerequisites=[[1,0],[0,1]] -> []  (অসম্ভব)

9. Brute force thinking

প্রথম সরল চিন্তা: সব n! permutation ঘুরে দেখা, প্রতিটার জন্য যাচাই করা সেটা সব prerequisite নিয়ম মানে কিনা (প্রতিটা কোর্সের আগে তার সব prereq আছে কিনা)।

1) কোর্সগুলোর প্রতিটা সম্ভাব্য সাজানো (permutation) নাও
2) সেই সাজানোয় প্রতিটা prereq [a,b] চেক করো — b কি a-এর আগে?
3) সব prereq মানা প্রথম permutation-ই উত্তর; কোনোটাই না মানলে []

10. Why brute force is slow

n! permutation ঘুরে দেখা factorial — সামান্য বেশি কোর্সেই অসম্ভব (n=15-এই 10^12 পেরোয়)। অথচ order বানাতে এত search লাগে না: যেকোনো মুহূর্তে কোন কোর্স "এখন করা যায়" তা indegree-ই বলে দেয়, কোনো guessing নেই। Kahn প্রতিটা node একবার, প্রতিটা edge একবার ছোঁয় — O(V + E)। permutation-search পুরো অপচয়, কারণ সিদ্ধান্তটা স্থানীয় (indegree 0?), global trial-and-error নয়।

11. Key observation

মূল observation: indegree 0 মানে "এই কোর্স এখনই করা যায়" — কোনো guess বা backtrack লাগে না। একটা কোর্স করলে তার dependents-এর indegree কমে, যা ক্রমে আরও কোর্স মুক্ত করে। আর শেষে output-এর দৈর্ঘ্য < numCourses হলেই চক্র — এটাই universal চক্র-alarm, আলাদা detection লাগে না।

12. Optimized intuition

সব indegree গোনো। যাদের indegree 0, তাদের queue-তে দাও। বারবার: queue থেকে একটা node নাও, order-এ যোগ করো; তার প্রতিটা dependent-এর indegree 1 কমাও, কেউ 0-তে নামলে queue-তে দাও। queue খালি হলে থামো। len(order) == numCourses হলে order-ই উত্তর; নাহলে চক্র, ফেরত []। O(V + E)।

13. Thinking tweak

মোচড়: "কোন ক্রমে সাজাব?" ভেবে সব সাজানো try না করে ভাবো "এই মুহূর্তে কে নির্ভরতা-মুক্ত (indegree 0)? তাকেই নিই, তারপর দেখি কে মুক্ত হলো।" Global ordering-এর প্রশ্নটাকে বারবার একটা স্থানীয় "এখন কে ready" প্রশ্নে ভেঙে দাও — সেটাই Kahn।

14. Step-by-step dry run

numCourses=3, prereq [[1,0],[2,1]] (0→1→2):

1. edge 0->1, 1->2। indegree: 0:0, 1:1, 2:1। queue = [0] (শুধু 0-এর indegree 0)। order = []।
2. pop 0 → order [0]। 0-এর dependent 1: indegree 1->0 → enqueue। queue = [1]।
3. pop 1 → order [0,1]। 1-এর dependent 2: indegree 1->0 → enqueue। queue = [2]।
4. pop 2 → order [0,1,2]। 2-এর dependent নেই। queue খালি। len(order)=3 == numCourses → ফেরত [0,1,2]।

15. Python solution

from collections import deque


def find_order(num_courses, prerequisites):
    adj = [[] for _ in range(num_courses)]
    indeg = [0] * num_courses
    for a, b in prerequisites:           # a করার আগে b -> edge b -> a (b unlock করে a)
        adj[b].append(a)
        indeg[a] += 1

    q = deque(c for c in range(num_courses) if indeg[c] == 0)   # এখন করা যায়
    order = []
    while q:
        c = q.popleft()
        order.append(c)
        for nxt in adj[c]:               # c শেষ -> dependents-এর এক prereq কমল
            indeg[nxt] -= 1
            if indeg[nxt] == 0:          # পুরো মুক্ত
                q.append(nxt)

    return order if len(order) == num_courses else []   # ছোট হলে চক্র


def is_valid_order(num_courses, prerequisites, order):
    # যাচাই: প্রতিটা prereq [a,b]-তে b কি a-এর আগে?
    if len(order) != num_courses:
        return False
    pos = {c: i for i, c in enumerate(order)}
    return all(pos[b] < pos[a] for a, b in prerequisites)


# ---- tests ----
o1 = find_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]])
assert is_valid_order(4, [[1, 0], [2, 0], [3, 1], [3, 2]], o1)

o2 = find_order(2, [[1, 0]])
assert o2 == [0, 1]

assert find_order(2, [[1, 0], [0, 1]]) == []          # চক্র -> খালি

o3 = find_order(3, [])                                 # prereq নেই
assert sorted(o3) == [0, 1, 2] and len(o3) == 3

o4 = find_order(3, [[1, 0], [2, 1]])                   # সরল chain
assert o4 == [0, 1, 2]

assert find_order(3, [[0, 1], [1, 2], [2, 0]]) == []  # ত্রিভুজ চক্র
print("সব test pass!")

16. Line-by-line code explanation

• adj[b].append(a) + indeg[a] += 1 — prereq [a, b] ("a-এর আগে b") মানে edge b -> a; b শেষ হলে a-এর একটা prereq মেটে।
• q = deque(... if indeg[c] == 0) — যেসব কোর্স শুরুতেই prerequisite-মুক্ত।
• order.append(c) — ready node-কে ক্রমে বসাই।
• indeg[nxt] -= 1 — c শেষ হওয়ায় তার প্রতিটা dependent-এর একটা prereq কমল।
• if indeg[nxt] == 0: q.append(nxt) — পুরো মুক্ত হলে সেও এখন করা যায়।
• return order if len(order) == num_courses else [] — সব বের না হলে চক্র, খালি list।

17. Output walkthrough

find_order(4, [[1,0],[2,0],[3,1],[3,2]]): indegree গোনে (0:0,1:1,2:1,3:2); 0 দিয়ে শুরু, তারপর 1 ও 2 মুক্ত হয়, শেষে 3 — একটা valid order (যেমন [0,1,2,3])। is_valid_order যাচাই করে প্রতিটা prereq মানা হয়েছে। chain 0->1->2 → [0,1,2]। পরস্পর-নির্ভর [[1,0],[0,1]]-এ কেউ indegree 0-তে পৌঁছায় না → []। ত্রিভুজ চক্র → []। prereq নেই → তিন node যেকোনো order, length 3। সব assert pass, শেষে print: সব test pass!।

18. Time complexity

O(V + E) — প্রতিটা node একবার enqueue/dequeue হয়, প্রতিটা edge একবার করে indegree-decrement-এ দেখা হয়। V = numCourses, E = len(prerequisites)।

19. Space complexity

O(V + E) — adjacency list O(V + E), indegree array O(V), queue ও order list worst case O(V)।

20. Common mistakes

• শেষের len(order) == num_courses check ভুলে যাওয়া — চক্র থাকলে নীরবে একটা অসম্পূর্ণ "order" ফেরত যায়।
• edge দিক উল্টো বসানো — prereq [a, b] মানে b -> a (b unlock করে a)। উল্টো করলে একটা নিখুঁত reverse order বেরোয় — classic নীরব bug।
• indegree বাড়ানোর সময় ভুল node-এ বাড়ানো (a-এর বদলে b) — শুরুর ready-set ভুল হয়।
• push করার সময়েই node-কে order-এ যোগ করা — শুধু popleft-এর সময় order-এ দিতে হয়, নাহলে একাধিকবার বা ভুল ক্রমে ঢোকে।

21. Which basic problem this inherits from

ভিত্তি: #15 Course Schedule (015-course-schedule.md) আর topological sort theory (../topological-sort.md)। #15-এ শুধু "সম্ভব?" (হ্যাঁ/না) ছিল; এখানে একই directed graph থেকে আসল ক্রম produce করি Kahn দিয়ে — আর Kahn-এর len(order) < numCourses নিজেই চক্র ধরে, তাই detection আর ordering এক algorithm-এই মেলে। মূল নতুন শিক্ষা: "indegree 0 = এখন ready" দিয়ে layer-by-layer ক্রম বানানো, যা পরে DP-on-DAG-এও processing order দেয়। পরের ধাপ: এই Kahn-ই CP scale-এ — #17।

22. Similar harder problems

• Course Schedule CSES (একই Kahn, competitive-programming scale) — https://cses.fi/problemset/task/1679 (এই tracker-এর #17)
• Alien Dictionary (sorted words থেকে constraint graph বানিয়ে topo sort) — https://leetcode.com/problems/alien-dictionary/ (#24)
• Parallel Courses (topo sort + layer/level গোনা) — https://leetcode.com/problems/parallel-courses/

23. Pattern learned

Topological sort (Kahn): DAG-এর nodes-কে এমন ক্রমে সাজাতে হলে যাতে প্রতিটা edge সামনে যায় — indegree গোনো, indegree-0 node-গুলো queue-তে দাও, একটা করে নিয়ে order-এ বসাও আর dependents-এর indegree কমাও; নতুন 0 হলে enqueue। len(order) < V হলে চক্র (order নেই)। detection + ordering এক pass-এ, O(V + E)।

24. Final summary

ভবিষ্যতের আমাকে: "Course Schedule II = Kahn topological sort; indegree 0 মানে এখন ready, একটা করে ছাড়ো আর dependents-এর indegree কমাও; order ছোট হলে চক্র, ফেরত []।" যখনই 'dependency মেনে একটা valid ক্রম বের করো' দেখবে — Kahn চালাও, edge দিক সাবধানে বসাও (prereq উল্টো), আর length-check দিয়ে চক্র ধরো।

25. JavaScript solution (with test cases)

Kahn JS-এ: indegree গোনো, 0-গুলো queue-তে, একে একে order-এ; valid order একাধিক, তাই helper দিয়ে যাচাই।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// prereq [a,b] মানে "a-এর আগে b" -> edge b -> a (b unlock করে a)
function findOrder(numCourses, prerequisites) {
  const adj = Array.from({ length: numCourses }, () => []);
  const indeg = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const queue = [];
  for (let c = 0; c < numCourses; c++) if (indeg[c] === 0) queue.push(c);
  let head = 0;
  const order = [];
  while (head < queue.length) {
    const c = queue[head++];
    order.push(c);
    for (const nxt of adj[c]) if (--indeg[nxt] === 0) queue.push(nxt);
  }
  return order.length === numCourses ? order : [];   // ছোট হলে চক্র
}
// helper: প্রতিটা prereq [a,b]-তে b কি a-এর আগে?
function isValidOrder(numCourses, prerequisites, order) {
  if (order.length !== numCourses) return false;
  const pos = new Map();
  order.forEach((c, i) => pos.set(c, i));
  return prerequisites.every(([a, b]) => pos.get(b) < pos.get(a));
}
// ---- test cases (example + edge) ----
const p1 = [[1, 0], [2, 0], [3, 1], [3, 2]];
assert(isValidOrder(4, p1, findOrder(4, p1)), "diamond-order");
assert(JSON.stringify(findOrder(2, [[1, 0]])) === JSON.stringify([0, 1]), "two");
assert(findOrder(2, [[1, 0], [0, 1]]).length === 0, "cycle -> empty");   // edge
const o3 = findOrder(3, []);
assert(o3.length === 3 && [...o3].sort().join() === "0,1,2", "no-prereq");
assert(JSON.stringify(findOrder(3, [[1, 0], [2, 1]])) === JSON.stringify([0, 1, 2]), "chain");
assert(findOrder(3, [[0, 1], [1, 2], [2, 0]]).length === 0, "triangle-cycle");
console.log("সব JS test pass!");

JS টীকা: Array.from({length: n}, () => []) দিয়ে adjacency বানাও — new Array(n).fill([]) সব index-এ একই array share করিয়ে দেয় (push একটায় = সবার গায়ে)। array সমান কিনা মেলাতে === চলে না (reference তুলনা), তাই JSON.stringify(a) === JSON.stringify(b); valid order একাধিক বলে isValidOrder helper দিয়ে যাচাই, hard-coded একটা order-এর সাথে নয়।

26. TypeScript solution (with test cases)

function findOrder(numCourses: number, prerequisites: number[][]): number[] {
  const adj: number[][] = Array.from({ length: numCourses }, () => []);
  const indeg: number[] = new Array(numCourses).fill(0);
  for (const [a, b] of prerequisites) { adj[b].push(a); indeg[a]++; }
  const queue: number[] = [];
  for (let c = 0; c < numCourses; c++) if (indeg[c] === 0) queue.push(c);
  let head = 0;
  const order: number[] = [];
  while (head < queue.length) {
    const c: number = queue[head++];
    order.push(c);
    for (const nxt of adj[c]) if (--indeg[nxt] === 0) queue.push(nxt);
  }
  return order.length === numCourses ? order : [];
}
function isValidOrder(numCourses: number, prerequisites: number[][], order: number[]): boolean {
  if (order.length !== numCourses) return false;
  const pos = new Map<number, number>();
  order.forEach((c, i) => pos.set(c, i));
  return prerequisites.every(([a, b]) => (pos.get(b) as number) < (pos.get(a) as number));
}
const p1: number[][] = [[1, 0], [2, 0], [3, 1], [3, 2]];
if (!isValidOrder(4, p1, findOrder(4, p1))) throw new Error("FAIL diamond");
if (findOrder(2, [[1, 0], [0, 1]]).length !== 0) throw new Error("FAIL cycle");
console.log("সব TS test pass!");

TS টীকা: return type number[] স্পষ্ট করে দেয় ফাংশন একটা order (বা খালি list) দেয়; Map<number, number> typing position-lookup-কে type-safe রাখে। pos.get number | undefined দেয় বলে compare-এ as number দিয়ে narrow করতে হয় — strict mode-এ এই null-safety-ই TS-এর সুবিধা।

27. কোথায় কাজে লাগে (real-world use)

• Build / compile order: Makefile, Bazel, webpack — কোন module আগে compile/link হবে তার valid order Kahn দিয়ে বের হয়।
• Task scheduler / CI pipeline: dependent job-গুলো এমন ক্রমে চালানো যাতে প্রতিটা job-এর আগে তার সব নির্ভরতা শেষ।
• Package installation: apt/npm/pip dependency resolve করে install order ঠিক করা; চক্র থাকলে error।
• Course/curriculum sequencing: prerequisite মেনে সেমিস্টার-ক্রম সাজানো (এই problem নিজেই)।
• DP on DAG / data pipeline: node-গুলো topological order-এ process করলে প্রতিটা গণনার আগে তার input তৈরি থাকে (ETL stage ordering)।

মূল pattern: "dependency মেনে একটা valid ক্রম বের করো" = topological sort; len(order) < V হলে চক্র।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।