Explain detecting a valid ordering.
01
01
Understand the problem
graphstopological-sort
02
02
Attempt it yourself
Sketch your approach before reading the solution — that's what interviews test.
Stuck? AI Nudge Available
Get a conceptual hint to guide your logic without spoiling the final implementation.
03
03
Study the solution
The solution is waiting
Give it an honest attempt first — then compare your thinking with the full walkthrough.
04
04
Read the code
Kahn's algorithm (BFS topo-sort)
Run Playgroundfrom collections import deque
def can_finish(num_courses, prerequisites):
graph = [[] for _ in range(num_courses)]
indegree = [0] * num_courses
for course, pre in prerequisites:
graph[pre].append(course)
indegree[course] += 1
q = deque(c for c in range(num_courses) if indegree[c] == 0)
taken = 0
while q:
c = q.popleft()
taken += 1
for nxt in graph[c]:
indegree[nxt] -= 1
if indegree[nxt] == 0:
q.append(nxt)
return taken == num_courses
# --- demo ---
print(can_finish(2, [[1, 0]])) # True (take 0, then 1)
print(can_finish(2, [[1, 0], [0, 1]])) # False (0 and 1 depend on each other)05
05
Join the discussion
Discussion (0)
Sign in to join the discussion.
No responses yet. Be the first to share what you think.