207 Course Schedule¶

207. Course Schedule

here 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.

:::Hint Finding cycles \(O(n^2) => O(n)\) Topological sort :::

Solution 1 : Topological Sort \(O(N)\)¶

alt

:::tip

0 : Not in Dictionary
1 : VISITING/PARTIAL
2 : COMPLETE :::

C# Solution¶

using System;
using System.Collections;
using System.Collections.Generic;

namespace Algorithms.Medium
{
  public class CourseScheduleTOWithDFS
  {
    public static bool CanFinish(int numCourses, int[,] prerequisites)
    {

      Dictionary<int, List<int>> graph = new Dictionary<int, List<int>>();
      Dictionary<int, int> visited = new Dictionary<int, int>();

      for (var i = 0; i < prerequisites.GetLength(0); i++)
      {
        var course = prerequisites[i, 0];
        var prerequisite = prerequisites[i, 1];
        if (!graph.ContainsKey(course))
        {
          graph.Add(course, new List<int>());
        }
        graph[course].Add(prerequisite);
      }

      for (var i = 0; i < prerequisites.GetLength(0); i++)
      {
        var course = prerequisites[i, 0];
        if (DFS(course, graph, visited)) return false;
      }

      return true;
    }

    private static bool DFS(int i, Dictionary<int, List<int>> graph, Dictionary<int, int> visited)
    {
      // 0 UNKNOWN/Not in Dictionary
      // 1 VISITING/PARTIAL
      // 2 COMPLETE
      if (visited.ContainsKey(i) && visited[i] == 1) return true;
      if (visited.ContainsKey(i) && visited[i] == 2) return false;

      visited[i] = 1;

      foreach (var dep in graph[i])
      {
        if (graph.ContainsKey(dep) && DFS(dep, graph, visited)) return true;
      }

      visited[i] = 2;

      return false;
    }
  }
}

C# Tests¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class CourseScheduleTOWithDFSTests
  {
    [Fact]
    public void LeetCodeTests()
    {
      Assert.True(CourseScheduleTOWithDFS.CanFinish(2, new int[,] { { 1, 0 } }));
      Assert.False(CourseScheduleTOWithDFS.CanFinish(2, new int[,] { { 1, 0 }, { 0, 1 } }));
    }

    [Fact]
    public void InvalidTest()
    {
      Assert.False(CourseScheduleTOWithDFS.CanFinish(7, new int[,] { { 1, 0 }, { 2, 6 }, { 1, 7 }, { 5, 1 }, { 6, 4 }, { 7, 0 }, { 0, 5 } }));
    }

    [Fact]
    public void ValidTest()
    {
      Assert.True(CourseScheduleTOWithDFS.CanFinish(7, new int[,] { { 1, 0 }, { 2, 6 }, { 1, 7 }, { 6, 4 }, { 7, 0 }, { 0, 5 } }));
    }
  }
}

Solution 2 : DFS Finding Cycles¶

alt

Time complexity: \(O(n^2)\) Space complexity: \(O(n)\)

// Time complexity: O(n^2)
// Runtime: 179 ms
class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {

        graph_.clear();

        for(const auto& p : prerequisites)
            graph_[p.first].insert(p.second);

        for (int i = 0; i < numCourses; ++i) {
            vector<int> visited(numCourses, 0);
            if (cycle(i, i, visited)) return false;
        }

        return true;
    }

private:
    unordered_map<int, unordered_set<int>> graph_;

    bool cycle(int start, int curr, vector<int>& visited) {
        if (curr == start && visited[start]) return true;
        if (!graph_.count(curr)) return false;

        for (const int next : graph_.at(curr)) {
            if (visited[next]) continue;
            visited[next] = true;
            if (cycle(start, next, visited)) return true;
        }
        return false;
    }
};