210. Course Schedule II LeetCode Solution

In this guide, you will get 210. Course Schedule II LeetCode Solution with the best time and space complexity. The solution to Course Schedule II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Course Schedule II solution in C++
Course Schedule II solution in Java
Course Schedule II solution in Python
Additional Resources

210. Course Schedule II LeetCode Solution image

Problem Statement of Course Schedule II

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 the ordering of courses you should take to finish all courses. If there are many valid answers, return any of them. If it is impossible to finish all courses, return an empty array.

Example 1:

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

Example 2:

Input: numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
Output: [0,2,1,3]
Explanation: There are a total of 4 courses to take. To take course 3 you should have finished both courses 1 and 2. Both courses 1 and 2 should be taken after you finished course 0.
So one correct course order is [0,1,2,3]. Another correct ordering is [0,2,1,3].

Example 3:

Input: numCourses = 1, prerequisites = []
Output: [0]

Constraints:

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses – 1)
prerequisites[i].length == 2
0 <= ai, bi < numCourses
ai != bi
All the pairs [ai, bi] are distinct.

Complexity Analysis

Time Complexity: O(|V| + |E|), where |V| = \texttt{numCourses} and |E| = |\texttt{prerequisites}|
Space Complexity: O(|V| + |E|), where |V| = \texttt{numCourses} and |E| = |\texttt{prerequisites}|

210. Course Schedule II LeetCode Solution in C++

enum class State { kInit, kVisiting, kVisited };

class Solution {
 public:
  vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
    vector<int> ans;
    vector<vector<int>> graph(numCourses);
    vector<State> states(numCourses);

    for (const vector<int>& prerequisite : prerequisites) {
      const int u = prerequisite[1];
      const int v = prerequisite[0];
      graph[u].push_back(v);
    }

    for (int i = 0; i < numCourses; ++i)
      if (hasCycle(graph, i, states, ans))
        return {};

    ranges::reverse(ans);
    return ans;
  }

 private:
  bool hasCycle(const vector<vector<int>>& graph, int u, vector<State>& states,
                vector<int>& ans) {
    if (states[u] == State::kVisiting)
      return true;
    if (states[u] == State::kVisited)
      return false;
    states[u] = State::kVisiting;
    for (const int v : graph[u])
      if (hasCycle(graph, v, states, ans))
        return true;
    states[u] = State::kVisited;
    ans.push_back(u);
    return false;
  }
};
/* code provided by PROGIEZ */

210. Course Schedule II LeetCode Solution in Java

enum State { kInit, kVisiting, kVisited }

class Solution {
  public int[] findOrder(int numCourses, int[][] prerequisites) {
    Deque<Integer> ans = new ArrayDeque<>();
    List<Integer>[] graph = new List[numCourses];
    State[] states = new State[numCourses];

    for (int i = 0; i < numCourses; ++i)
      graph[i] = new ArrayList<>();

    for (int[] prerequisite : prerequisites) {
      final int u = prerequisite[1];
      final int v = prerequisite[0];
      graph[u].add(v);
    }

    for (int i = 0; i < numCourses; ++i)
      if (hasCycle(graph, i, states, ans))
        return new int[] {};

    return ans.stream().mapToInt(Integer::intValue).toArray();
  }

  private boolean hasCycle(List<Integer>[] graph, int u, State[] states, Deque<Integer> ans) {
    if (states[u] == State.kVisiting)
      return true;
    if (states[u] == State.kVisited)
      return false;
    states[u] = State.kVisiting;
    for (final int v : graph[u])
      if (hasCycle(graph, v, states, ans))
        return true;
    states[u] = State.kVisited;
    ans.addFirst(u);
    return false;
  }
}
// code provided by PROGIEZ

210. Course Schedule II LeetCode Solution in Python

from enum import Enum


class State(Enum):
  kInit = 0
  kVisiting = 1
  kVisited = 2


class Solution:
  def findOrder(
      self,
      numCourses: int,
      prerequisites: list[list[int]],
  ) -> list[int]:
    ans = []
    graph = [[] for _ in range(numCourses)]
    states = [State.kInit] * numCourses

    for v, u in prerequisites:
      graph[u].append(v)

    def hasCycle(u: int) -> bool:
      if states[u] == State.kVisiting:
        return True
      if states[u] == State.kVisited:
        return False
      states[u] = State.kVisiting
      if any(hasCycle(v) for v in graph[u]):
        return True
      states[u] = State.kVisited
      ans.append(u)
      return False

    if any(hasCycle(i) for i in range(numCourses)):
      return []

    return ans[::-1]
 # code by PROGIEZ