algoadvance

Leetcode 207. Course Schedule

Problem Statement

You are given a list of courses you need to take, labeled from 0 to n-1. Some courses may have prerequisites, where taking course i requires taking course j first. Given the total number of courses and a list of prerequisite pairs, determine if it is possible for you to finish all courses.

Example:

Input: numCourses = 2, prerequisites = [[1,0]]
Output: true
Explanation: There are a total of 2 courses. To take course 1 you should have finished course 0. So it is possible.

Constraints:

• The input prerequisites are represented as a list of pairs [a, b], where a requires b to be taken first.
• You may assume that prerequisites are valid and form a directed acyclic graph (DAG).

Clarifying Questions

1. What should be the output if there are no courses (i.e., numCourses = 0)?
   • It should return true since there are no courses to take.
2. Can there be duplicate pairs in the prerequisites list?
   • For simplicity, you can assume there are no duplicate pairs.

Strategy

To determine if all courses can be completed, we must detect if there is a cycle in the directed graph formed by the course prerequisites. If there is a cycle, it is impossible to finish all courses.

We can use Depth First Search (DFS) to detect cycles in the graph. Here are the steps:

1. Create an adjacency list representation of the graph from prerequisites.
2. Use a recursive DFS approach to check for cycles.
3. Mark each node with three states:
   • 0 for unvisited,
   • 1 for being visited (part of the current DFS path),
   • 2 for fully visited (no cycle detected for this node).

Code

import java.util.ArrayList;
import java.util.List;

public class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjList.add(new ArrayList<>());
        }

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

        int[] visited = new int[numCourses]; // 0 = unvisited, 1 = visiting, 2 = visited

        for (int i = 0; i < numCourses; i++) {
            if (dfs(i, adjList, visited)) {
                return false;
            }
        }

        return true;
    }

    private boolean dfs(int node, List<List<Integer>> adjList, int[] visited) {
        if (visited[node] == 1) {
            return true; // Cycle detected
        }
        if (visited[node] == 2) {
            return false; // Already fully processed node
        
        visited[node] = 1; // Mark the node as being visited

        for (int neighbor : adjList.get(node)) {
            if (dfs(neighbor, adjList, visited)) {
                return true; // Cycle detected
            }
        }

        visited[node] = 2; // Mark the node as fully processed
        return false;
    }
}

Time Complexity

• Constructing the adjacency list takes O(E) time where E is the number of prerequisite pairs.
• The DFS traversal of the graph will take O(V + E) where V is the number of courses.

Hence, the overall time complexity is O(V + E).

Space Complexity

• Adjacency list uses O(V + E) space.
• The visited array uses O(V) space.
• The recursion stack in the worst case can go up to O(V) depth.

Thus, the space complexity is O(V + E).

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?