Skip to content

010 — Course Schedule

Source

  • Original source: Classic capstone interview problem (cycle detection / topological sort)
  • Platform: LeetCode — https://leetcode.com/problems/course-schedule/
  • Topic: graphs + hashing (adjacency)
  • Difficulty: Medium
  • Pattern: Cycle detection via topological sort (Kahn's BFS on indegree)
  • Basic idea inherited from: এটা একটা cross-topic capstone — এখানে মেশে 09 graphs (prerequisite-গুলোকে একটা directed graph ধরে, cycle আছে কি না / topological order সম্ভব কি না দেখা) আর 05 hashing (adjacency list-টা একটা dictionary/defaultdict দিয়ে O(1)-এ গড়া ও পড়া)। দুই tool জোড়া লাগলেই এই problem।

1. Problem in simple words

তোমাকে numCoursesটা কোর্স (0 থেকে numCourses-1) আর কিছু prerequisite জোড়া দেওয়া। প্রতিটা জোড়া [a, b]-র মানে: কোর্স a করার আগে কোর্স b করতেই হবে। প্রশ্ন: এমন কোনো ক্রম আছে কি, যাতে সব কোর্স শেষ করা যায়? (মানে কোনো চক্রাকার নির্ভরতা — "A-র আগে B, B-র আগে A" — নেই তো?) সম্ভব হলে True, নাহলে False।

numCourses = 2, prerequisites = [[1, 0]]
   মানে: 1-এর আগে 0 -> 0 তারপর 1 -> সম্ভব -> True

numCourses = 2, prerequisites = [[1, 0], [0, 1]]
   মানে: 1-এর আগে 0, আবার 0-এর আগে 1 -> চক্র! -> False

2. Which basic idea does this inherit from?

এই problem দুটো আগের chapter-এর tool জোড়া দেয়:

  • 09 graphs থেকে: prerequisite-গুলোকে একটা directed graph ধরা (edge b -> a মানে "b শেষ হলে তবে a-র দিকে যাওয়া যায়")। তখন "সব কোর্স করা সম্ভব?" = "graph-এ cycle নেই তো?" = "একটা topological order বের করা যায় কি?"
  • 05 hashing থেকে: graph-টা একটা adjacency list (defaultdict(list)) দিয়ে রাখা — কোন node থেকে কোথায় edge যায়, তা O(1)-এ পড়া।

একা graph-চিন্তা দেয় cycle/topo framing; একা hashing দেয় adjacency-র দ্রুত গঠন। দুটো মিললে O(V+E)।

3. What is the hidden math or logic?

লুকানো logic: সব কোর্স করা সম্ভব ঠিক তখনই যখন directed graph-টা acyclic (DAG)। একটা DAG-এ সবসময় অন্তত একটা node থাকে যার কোনো অসম্পূর্ণ prerequisite নেই (indegree 0); সেটা শেষ করে সরিয়ে দিলে আবার নতুন indegree-0 node বেরোয়। সব node এভাবে সরাতে পারলে cycle নেই; কোনো এক পর্যায়ে আর indegree-0 না পেলে বাকিগুলো একটা cycle-এ আটকা — অসম্ভব।

4. Which data structure is needed?

  • একটা adjacency list (defaultdict(list), 05 hashing) — graph-এর edge রাখতে।
  • একটা indegree array — প্রতিটা node-এর কতগুলো অসম্পূর্ণ prerequisite।
  • একটা queue (deque) — Kahn's BFS-এ indegree-0 node ধরে রাখতে।

5. Why this data structure fits

Topological sort-এ বারবার দুটো কাজ লাগে: (1) "এই node থেকে কোথায় কোথায় edge যায়" দ্রুত জানা, (2) "এই মুহূর্তে কোন কোন node-এর indegree 0" ধরে রাখা। adjacency list (hashmap) প্রথমটা O(1)-এ দেয়; indegree array + queue দ্বিতীয়টা সহজ করে। এই combination-ই Kahn-এর algorithm-কে O(V+E)-এ চালায়। তাই graph (09) + hashing (05) এখানে নিখুঁত।

6. Real-life analogy

ভাবো তুমি জামাকাপড় পরছ — মোজার আগে জুতো পরা যায় না, শার্টের আগে কোট না। তুমি প্রথমে সেই জিনিসগুলো পরো যেগুলোর কোনো "আগে-শর্ত" নেই (অন্তর্বাস, মোজা)। একটা পরে ফেললে যেসব জিনিসের শর্ত পূরণ হলো (এবার জুতো পরা যায়), সেগুলো "তৈরি" তালিকায় ঢোকে। সব পরা শেষ হলে ভালো; কিন্তু যদি "A-র আগে B, B-র আগে A" এমন গিঁট থাকে, তুমি কখনোই শুরু করতে পারবে না — সেটাই cycle।

7. Visual explanation

numCourses=4, prereqs [[1,0],[2,0],[3,1],[3,2]] — Kahn's BFS:

edge (b->a):  0->1, 0->2, 1->3, 2->3
indegree:     [0, 1, 1, 2]      # node 0-এর কোনো শর্ত নেই

queue=[0]              নাও 0; processed=1; 1,2-র indegree-- -> [0,0,0,2]; queue=[1,2]
queue=[1,2]            নাও 1; processed=2; 3-র indegree-- -> [_,_,0,1]; queue=[2]
queue=[2]             নাও 2; processed=3; 3-র indegree-- -> [_,_,_,0]; queue=[3]
queue=[3]             নাও 3; processed=4; queue খালি

processed (4) == numCourses (4) -> cycle নেই -> True

8. Example input and output

Input : numCourses=2, prerequisites=[[1,0]]        -> Output: True
Input : numCourses=2, prerequisites=[[1,0],[0,1]]  -> Output: False  (চক্র)

Edge case 1 (কোনো prereq নেই): numCourses=3, []    -> Output: True
Edge case 2 (একটা কোর্স): numCourses=1, []         -> Output: True
Edge case 3 (নিজের উপর নির্ভর): numCourses=1, [[0,0]] -> Output: False

9. Brute force thinking

প্রথম সরল চিন্তা: প্রতিটা কোর্স থেকে DFS করে দেখি কোনো পথ ঘুরে নিজের কাছে ফিরে আসে কি না (cycle খোঁজা)। প্রতিটা DFS-এ বর্তমান পথের node গুলো একটা "recursion stack"-এ রেখে, আবার সেই node-এ পৌঁছালে cycle।

for প্রতিটা course c:
    if dfs(c) cycle পায়:
        return False
return True
# dfs: c-কে "চলমান পথে" চিহ্নিত করো, প্রতিবেশীতে যাও;
#      চলমান node আবার পেলে cycle; শেষ হলে চিহ্ন তুলে নাও

10. Why brute force is slow

সাবধানে visited/finished চিহ্ন না রাখলে একই subtree বারবার ঘুরে DFS O(V·(V+E)) বা আরও খারাপ হয়ে যায়। ঠিকভাবে memo করলে DFS-ও O(V+E)-এ নামে — কিন্তু তিন রঙের state (unvisited / in-progress / done) সামলানো bug-প্রবণ। Kahn's BFS (indegree) একই O(V+E) আরও সরল ও কম-ভুলের পথে দেয়, আর বাড়তি হিসেবে একটা valid order-ও দেয়।

11. Key observation

মূল observation: প্রশ্নটা আসলে "graph-এ cycle আছে কি?" — আর একটা DAG-এ সবসময় indegree-0 node দিয়ে শুরু করে সব node সরানো যায়। যদি সব node সরাতে পারি (processed == numCourses), cycle নেই। কোনো পর্যায়ে আর indegree-0 না পেলে, বাকিগুলো cycle-এ আটকা। এই এক চিন্তাই সমাধান।

12. Optimized intuition

Adjacency list (b -> a) আর indegree array বানাও। indegree-0 সব node queue-তে দাও (এদের আগে কোনো শর্ত নেই)। queue থেকে এক এক node নাও, "processed" গুনো, আর তার প্রতিবেশীদের indegree কমাও; কারো indegree 0 হলে queue-তে দাও। শেষে যদি processed == numCourses, তাহলে সব করা সম্ভব (True), নাহলে cycle (False)।

13. Thinking tweak

মোচড়: "কোন ক্রমে কোর্স করব খুঁজব" ভাবার বদলে ভাবো "শুধু জিজ্ঞেস করি — সব node কি indegree-0 দিয়ে এক এক করে সরানো যায়?" topological-feasibility একটা সহজ indegree-counting-এ গলে যায়; পুরো order বের করারও দরকার নেই, শুধু গুনলেই হয়।

14. Step-by-step dry run

Input numCourses=3, prereqs [[1,0],[2,1]] (edge 0->1, 1->2):

  1. adjacency: {0:[1], 1:[2]}; indegree [0, 1, 1]; queue [0]; processed 0
  2. নাও 0: processed 1; 1-র indegree → 0; queue [1]
  3. নাও 1: processed 2; 2-র indegree → 0; queue [2]
  4. নাও 2: processed 3; queue খালি
  5. processed (3) == numCourses (3) → return True

15. Python solution

from collections import deque, defaultdict

def can_finish(num_courses, prerequisites):
    adj = defaultdict(list)               # b -> [a, ...]: b শেষ হলে a-রা এক ধাপ এগোয়
    indegree = [0] * num_courses
    for a, b in prerequisites:            # a-র আগে b
        adj[b].append(a)
        indegree[a] += 1

    queue = deque(c for c in range(num_courses) if indegree[c] == 0)
    processed = 0
    while queue:
        node = queue.popleft()
        processed += 1                    # এই কোর্স "করা গেল"
        for nxt in adj[node]:
            indegree[nxt] -= 1            # একটা শর্ত পূরণ হলো
            if indegree[nxt] == 0:
                queue.append(nxt)
    return processed == num_courses       # সব করা গেলে cycle নেই

# ---- tests ----
assert can_finish(2, [[1, 0]]) is True
assert can_finish(2, [[1, 0], [0, 1]]) is False        # সরাসরি চক্র
assert can_finish(3, []) is True                       # কোনো শর্ত নেই
assert can_finish(1, []) is True                       # একটা কোর্স
assert can_finish(1, [[0, 0]]) is False                # নিজের উপর নির্ভর = চক্র
assert can_finish(4, [[1,0],[2,0],[3,1],[3,2]]) is True
assert can_finish(3, [[0,1],[1,2],[2,0]]) is False     # ত্রিভুজ চক্র
print("সব test pass!")

16. Line-by-line code explanation

  • adj = defaultdict(list) — adjacency list, নতুন key আপনাআপনি খোলে (05 hashing)।
  • for a, b in prerequisites — a-র আগে b, তাই edge b -> a যোগ করি আর a-র indegree বাড়াই।
  • queue = deque(... indegree[c] == 0) — যেসব কোর্সের কোনো শর্ত নেই, তারা প্রথমে তৈরি।
  • processed += 1 — queue থেকে নেওয়া মানে এই কোর্স সফলভাবে করা গেল, গুনে রাখি।
  • for nxt in adj[node] — যাদের এই node শর্ত ছিল, তাদের indegree কমাও।
  • if indegree[nxt] == 0: queue.append(nxt) — সব শর্ত পূরণ হলে সেই কোর্স এবার তৈরি।
  • return processed == num_courses — সব কোর্স process হলে DAG (সম্ভব); কম হলে কিছু cycle-এ আটকা (অসম্ভব)।

17. Output walkthrough

numCourses=2, [[1,0]]-এ indegree [0,1], queue [0]; 0 নিয়ে processed 1, 1-র indegree 0 হয়ে queue-তে; 1 নিয়ে processed 2; 2 == 2 → True — assert pass। [[1,0],[0,1]]-এ দুটো node-ই indegree 1, queue শুরুতেই খালি, processed 0 ≠ 2 → False। ত্রিভুজ চক্র, self-loop, খালি-prereq case-ও সঠিক। শেষে print: সব test pass!।

18. Time complexity

O(V + E) — প্রতিটা node একবার queue-তে ঢোকে-বেরোয় (V), প্রতিটা edge একবার relax হয় (E)।

19. Space complexity

O(V + E) — adjacency list সব edge রাখে (E), indegree array আর queue O(V)।

20. Common mistakes

  • edge-এর দিক উল্টে দেওয়া (a -> b বনাম b -> a) — [a,b] মানে "a-র আগে b", তাই edge b -> a; উল্টালে cycle-যুক্তি ভেঙে যায়।
  • শেষে processed == num_courses চেক না করে শুধু queue খালি কি না দেখা — cycle-এ আটকা node গুলো কখনো queue-তে ঢোকেই না, তাই গোনাটাই আসল test।
  • self-loop ([0,0]) ভুলে যাওয়া — এটা একটা cycle, False হওয়া উচিত; indegree-পদ্ধতি এটা আপনাআপনি ধরে।
  • disconnected node (কোনো prereq নেই) ভুলে যাওয়া — এদের indegree 0, শুরুতেই queue-তে দিতে হয়।

21. Which basic problem this inherits from

ভিত্তি: directed graph-এ cycle detection / topological sort (09 graphs, ../../09-graphs/topological-sort.md) + adjacency list-এর জন্য hashmap (05 hashing, ../../05-hashing/)। সাধারণ graph traversal-ই এখানে indegree-গণনার মোড়কে।

22. Similar harder problems

23. Pattern learned

Topological sort / cycle detection (Kahn's BFS): prerequisite-কে directed graph ধরে, indegree-0 node দিয়ে শুরু করে সব node সরানো যায় কি না গুনে — "নির্ভরতা নিয়ে সব কাজ করা সম্ভব?"-ধরনের problem সমাধান। DFS-three-color দিয়েও একই কাজ হয়।

24. Final summary

ভবিষ্যতের আমাকে: "prerequisite / dependency / ordering সম্ভব কি না" শুনলেই topological sort (cycle detection) মনে করবে। মূল চাল — directed graph বানাও, indegree-0 থেকে BFS, শেষে processed == n হলে DAG। edge-এর দিক আর শেষের গোনা — এই দুটোতেই বেশি ভুল হয়, তাই সাবধান। order চাইলে Course Schedule II-তে শুধু processed-ক্রমটা জমিয়ে রাখলেই হয়।

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