Course Schedule II
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Same prerequisites. Return one valid order to take all courses, or an empty list if impossible.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What do you collect each time a course is taken from the ready queue?
- Hint 2How do you detect an impossible schedule?
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
The same timetable, but now you must hand in the actual plan: the list of courses in the order you took them. Every time a course becomes ready and you take it, write its name at the end of the plan. If every course got written, the plan is valid; otherwise there is a circular dependency and no plan exists.
- The obvious way
DFS with post-order reversed also works; Kahn gives the order directly.
- The key insight
Run the same ready-queue process and append each course to an order list when it is taken. If the order's length equals the number of courses, return it; else return an empty list.
- The algorithm
- Count waiting prerequisites; list who each unlocks.
- Queue the ready courses.
- Take a course: append to order, update dependants.
- Return order if complete, else [].
Watch it run
ExamplenumCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Only course 0 is ready. Take it: order = [0]. Courses 1 and 2 are now ready.
order: 0
Where people slip
- Return an empty list/array (not None) when a cycle exists.
- Any valid order is accepted; yours may differ from an example.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
from collections import deque
def find_order(num_courses, prerequisites):
waiting_on = [0] * num_courses
unlocks = [[] for _ in range(num_courses)]
for course, needed in prerequisites:
unlocks[needed].append(course)
waiting_on[course] += 1
ready = deque(course for course in range(num_courses) if waiting_on[course] == 0)
plan = [] # courses in the order we take them
while ready:
course = ready.popleft()
plan.append(course)
for next_course in unlocks[course]:
waiting_on[next_course] -= 1
if waiting_on[next_course] == 0:
ready.append(next_course)
return plan if len(plan) == num_courses else [] # fewer means a circular dependencyNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.