Crack the Backend

Problem Statement

There are numCourses courses labeled 0 to numCourses-1. You are given prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses (i.e. complete a valid ordering); otherwise return false. The dependency graph is directed; we need to detect if there is a cycle (which would make it impossible to finish).

Cycle detection with DFS: Use three states per node: unvisited, visiting (in current DFS stack), visited (finished). If we follow an edge to a node that is "visiting", we have found a back edge → cycle. Alternatively, Kahn's algorithm (BFS with in-degree): repeatedly remove nodes with in-degree 0; if we cannot process all nodes, there is a cycle.

Key Observations

DFS approach: Build adjacency list (from prerequisite: b -> a means b must be before a, so edge b→a). For each node, if unvisited, run dfs(node). In dfs: mark node as "visiting". For each neighbor: if neighbor is "visiting" return false (cycle); if unvisited and !dfs(neighbor) return false. Mark node as "visited"; return true.
Kahn (BFS): Compute in-degrees. Queue all with in-degree 0. For each dequeued node, reduce in-degree of neighbors; if a neighbor's in-degree becomes 0, enqueue. If the number of processed nodes < numCourses, there is a cycle.

Approach

High-level: Build graph: edge b→a for each [a,b]. DFS with state: unvisited/visiting/visited. If we ever go to a "visiting" node, return false. Return true if all nodes become visited.

Steps: adj list; state array. For each node i: if unvisited, if !dfs(i) return false. dfs(u): set state[u]=visiting; for v in adj[u]: if state[v]==visiting return false; if state[v]==unvisited && !dfs(v) return false; state[u]=visited; return true.

Implementation

Java

public boolean canFinish(int numCourses, int[][] prerequisites) {
    List<List<Integer>> adj = new ArrayList<>();

    for (int i = 0; i < numCourses; i++) {
        adj.add(new ArrayList<>());
    }

    for (int[] p : prerequisites) {
        adj.get(p[1]).add(p[0]);
    }

    int[] state = new int[numCourses];

    for (int i = 0; i < numCourses; i++)
    if (state[i] == 0 && !dfs(adj, i, state)) {
        return false;
    }

    return true;
}

boolean dfs(List<List<Integer>> adj, int u, int[] state) {
    state[u] = 1;

    for (int v : adj.get(u)) {
        if (state[v] == 1) {
            return false;
        }

        if (state[v] == 0 && !dfs(adj, v, state)) {
            return false;
        }
    }

    state[u] = 2;
    return true;
}

Test Cases

Example 1

Input

numCourses = 2, prerequisites = [[1,0]]

Expected

true

Explanation

0 then 1.

Complexity Analysis

Time: O(V+E).
Space: O(V).

Follow-ups

Course Schedule II: return one valid order (topological order).