Problem 2 - Course Schedule

Question

There are a total of numCourses courses you have to take, labeled from 0 to numCourses - 1. You are given an array prerequisites where prerequisites[i] = [ai, bi] indicates that you must take course bi first if you want to take course ai.

• For example, the pair [0, 1], indicates that to take course 0 you have to first take course 1.

Return true if you can finish all courses. Otherwise, return false.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= numCourses <= 2000

• 0 <= prerequisites.length <= 5000

• prerequisites[i].length == 2

• 0 <= ai, bi < numCourses

• All the pairs prerequisites[i] are unique.

Approach

This solution utilizes a depth-first search (DFS) algorithm to check if there is a cycle in the course prerequisites. It builds an adjacency list representation of the courses, where each course is associated with its prerequisites. Then, it performs a DFS for each course, checking for any cycles. If a cycle is found, it returns false, indicating that it is not possible to schedule the courses. If no cycle is found, it returns true, indicating that the course schedule is possible.

Here's a summary of the DFS algorithm for this solution:

1. Build an adjacency list representation of the courses using the given prerequisites.

2. Initialize a visited array to keep track of the visited status of each course.

3. Perform a DFS for each course.

4. During the DFS, mark the current course as visited.

5. Explore the prerequisites of the current course.

6. If a prerequisite is already visited during the DFS traversal, it indicates a cycle, and the course schedule is not possible. Return false.

7. If a prerequisite is not visited, perform a DFS on that prerequisite recursively.

8. After exploring all prerequisites, mark the current course as completed (visited).

9. If no cycle is detected in any DFS traversal, return true, indicating that the course schedule is possible.

This DFS approach helps determine if there is a cycle in the course prerequisites, as a cycle would indicate an impossible course schedule.

Solution

Solve it here

import java.util.*;

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // Create adjacency list representation of the courses
        List<List<Integer>> adjacencyList = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) {
            adjacencyList.add(new ArrayList<>());
        }

        // Build the adjacency list
        for (int[] prerequisite : prerequisites) {
            int course = prerequisite[0];
            int prerequisiteCourse = prerequisite[1];
            adjacencyList.get(course).add(prerequisiteCourse);
        }

        // Create an array to track the visited status of each course
        int[] visited = new int[numCourses];

        // Perform DFS for each course
        for (int i = 0; i < numCourses; i++) {
            if (hasCycle(i, adjacencyList, visited)) {
                return false; // Cycle detected, course schedule is not possible
            }
        }

        return true; // No cycle detected, course schedule is possible
    }

    private boolean hasCycle(int course, List<List<Integer>> adjacencyList, int[] visited) {
        if (visited[course] == 1) {
            return true; // Cycle detected
        }
        if (visited[course] == -1) {
            return false; // Already visited, no cycle
        }

        visited[course] = 1; // Mark course as visited

        // Explore prerequisites of the course
        for (int prerequisiteCourse : adjacencyList.get(course)) {
            if (hasCycle(prerequisiteCourse, adjacencyList, visited)) {
                return true; // Cycle detected
            }
        }

        visited[course] = -1; // Mark course as completed

        return false; // No cycle detected
    }
}

Time and space complexity

Time Complexity: The time complexity of this solution is O(V + E), where V represents the number of courses (vertices) and E represents the number of prerequisites (edges). It involves traversing each course once and exploring its prerequisites. The time complexity may also include the complexity of building the adjacency list, which is O(E) in this case.

Space Complexity: The space complexity of this solution is O(V + E). It includes the space required for the adjacency list representation of the courses, which is O(V + E). Additionally, the space used by the visited array is O(V). In the worst case, when there are no prerequisites and each course depends on all other courses, the space complexity can be considered O(V^2).