Leetcode 210. Course Schedule II

Question

Problem statement

There are a total of \$n\$ courses you have to take, labeled from \0ドル\$ to \$n - 1\$.

Some courses may have prerequisites, for example to take course \0ドル\$ you have to first take course \1ドル\,ドル which is expressed as a pair: \$[0,1]\$

Given the total number of courses and a list of prerequisite pairs, return the ordering of courses you should take to finish all courses.

There may be multiple correct orders, you just need to return one of them. If it is impossible to finish all courses, return an empty array.

For example:

\2,ドル [[1,0]]\$

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]\$

\4,ドル [[1,0],[2,0],[3,1],[3,2]]\$

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]\$.

My introduction of algorithm:

The algorithm is one of topological sorting algorithms. I spent over 5 hours to practice in 2016, and then based on the last practice, I reviewed the practice today less than 2 hour. I put together the C# solution for code review.

Highlights of changes:

1. Add two test cases, work on the second test case with 4 possible solutions.

2. For each course, there are dependent courses, assuming that course Id is from 0 to numCourses - 1. I declare a local variable dependents this practice.

   var dependents = new Stack<int>[numCourses];
   

My last practice in 2016, I used List<List<int>> dpList. Two obvious issues: the name is not meaningful one, and List<List<int>> is hard to tell what two lists are stored.

The C# code passes all test cases on leetcode online judge.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace _210CourseProject
{
 public class Solution
 {
 /*
 * Leetcode 210: course schedule II
 * https://leetcode.com/submissions/detail/91139534/
 */
 static void Main(string[] args)
 {
 //RunSampleTestcase();
 //RunSampleTestcase1();
 RunSampleTestcase2(); 
 }
 /* [[1,0]]
 *
 * 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]
 */
 public static void RunSampleTestcase1()
 {
 int[,] prerequisites = new int[,] { { 1, 0 } };
 var coursesInOrder = FindOrder(2, prerequisites);
 string concatenatedCourses = string.Join(",", coursesInOrder);
 Debug.Assert(concatenatedCourses.CompareTo("0,1") == 0 
 );
 }
 /*
 * int[,] prerequisite
 * 
 * 
 * 4, [[1,0],[2,0],[3,1],[3,2]]
 * 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 
 * there are 4 possible orderings. 
 * [4,0,1,2,3]
 * [4,0,2,1,3]
 * [0,4,2,1,3]
 * [0,4,1,2,3]
 */
 public static void RunSampleTestcase2()
 {
 int[,] prerequisites = new int[,]{{1,0},{2,0},{3,1},{3,2}}; 
 var coursesInOrder = FindOrder(5, prerequisites);
 string concatenatedCourses = string.Join(",", coursesInOrder);
 Debug.Assert(concatenatedCourses.CompareTo("4,0,1,2,3") == 0 ||
 concatenatedCourses.CompareTo("4,0,2,1,3") == 0 ||
 concatenatedCourses.CompareTo("0,4,2,1,3") == 0 ||
 concatenatedCourses.CompareTo("0,4,1,2,3") == 0
 ); 
 }
 /*
 * 1. Take prerequisites first
 * 2. There may be multiple correct orders, you just need to return one of them.
 * 3. If it is impossible to finish all courses, return an empty array
 * Using topological sort, find all courses without prerequisites, 
 * put into the queue, 
 * and then dequeue one by one. 
 */
 public static int[] FindOrder(int numCourses, int[,] prerequisites)
 {
 var dependents = new Stack<int>[numCourses];
 for (int i = 0; i < numCourses; ++i)
 {
 dependents[i] = new Stack<int>(); 
 }
 // build dependency list for each prerequisite course, 
 // and set up indegree variable for each courses matching 
 // with prerequisite courses' number.
 int[] indegree = new int[numCourses];
 for (int i = 0; i < prerequisites.GetLength(0); ++i)
 {
 int takeFirst = prerequisites[i, 1];
 int takeAfter = prerequisites[i, 0];
 dependents[takeFirst].Push(takeAfter); 
 ++indegree[takeAfter]; 
 }
 // add those courses with 0 indegree to the queue
 Queue<int> queue = new Queue<int>();
 for (int courseId = 0; courseId < numCourses; ++courseId)
 {
 if (indegree[courseId] == 0)
 {
 queue.Enqueue(courseId);
 }
 }
 // take courses with indgree zero only
 var coursesByTakingOrder = new int[numCourses];
 int count = 0;
 while (queue.Count > 0)
 { 
 int readyToTake = queue.Dequeue();
 coursesByTakingOrder[count++] = readyToTake; 
 foreach (int courseId in dependents[readyToTake])
 {
 // decrement value of indegree by 1 
 indegree[courseId]--;
 // add to the queue if there is no prerequisite left
 if (indegree[courseId] == 0) 
 {
 queue.Enqueue(courseId);
 }
 }
 }
 if (count != numCourses)
 { 
 return new int[]{}; 
 }
 return coursesByTakingOrder;
 }
 }
}

• Jianmin Chen: My last practice in April 30 2016 took a lot of time, but I did not know the code review at that time, and then I encouraged myself using the twitter of sports player Kristina Mladenovic "train insane or remain the same", twitter.com/KikiMladenovic/status/744887194016452609. Just use this short memo to remind myself to be more open to advice.
• David Isla: You have a mistake in your testcase 2 FindOrder(5, prerequisites);, 5->4?
• Jianmin Chen: @DavidIsla, thank you for the comment. I did make a mistake in the comment. There are 5 courses, ID from 0 to 4, course 4 has no dependent. But in my comment, I did say by mistake "There are a total of 4 courses to take", should say "There are a total of 5 courses to take". Good catch if I understand you correctly.
• sam: How can we ensure that if there are multiple answers, we give a solution where the courses are in ascending order?

Answer 1

In a real life scenario I personally would take an object oriented approach instead of this algorithmic one to be able to verify invalid inputs (what about if there are indirect circular dependencies in the database?), have self-speaking code and debug hints etc.

Here my suggestion:

Solution.cs

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
namespace _210CourseProject {
 public class Solution {
 /*
 * Leetcode 210: course schedule II
 * https://leetcode.com/submissions/detail/91139534/
 */
 static void Main(string[] args) {
 //Common variables
 Int32[,] myTestData;
 Course[] myCourses;
 String[] myCourseIDs;
 //Test case 1
 myTestData = new Int32[,] { { 1, 0 } };
 myCourses = GetCourses(null, myTestData);
 myCourseIDs = (from e in myCourses select e.CourseID.ToString()).ToArray();
 Console.WriteLine(String.Join(", ", myCourseIDs));
 //Test case 2
 myTestData = new Int32[,] { { 1, 0 }, { 2, 0 }, { 3, 1 }, { 3, 2 }, { 2, 4 } };
 myCourses = GetCourses(null, myTestData);
 myCourseIDs = (from e in myCourses select e.CourseID.ToString()).ToArray();
 Console.WriteLine(String.Join(", ", myCourseIDs));
 //Test case 3 (invalid indirect circular-dependency)
 myTestData = new Int32[,] { { 1, 0 }, { 0, 2 }, { 2, 1 }, { 3, 2 }, { 2, 4 } };
 try {
 myCourses = GetCourses(null, myTestData);
 Debug.Assert(false, "An ArgumentException should have been thrown!");
 } catch (ArgumentException ex) {
 Console.WriteLine(ex.Message);
 } catch (Exception ex) {
 Debug.Assert(false, $"An exception of type {typeof(ArgumentException).Name } expected, not of type {ex.GetType().Name }!");
 }
 }
 private static Course[] GetCourses(Int32[] courseList, Int32[,] courseDependencies) {
 Dictionary<Int32, Course> myDict = new Dictionary<Int32, Course>();
 //Needed for courses without any dependencies (usually they won't appear in a m:n table)
 if (courseList != null) {
 Array.ForEach(courseList, (Int32 x) => {
 if (myDict.ContainsKey(x)) return;
 myDict.Add(x, new Course(x));
 });
 }
 //Create courses and add dependency
 if (courseDependencies != null) {
 IEnumerable<CourseDependency> myDependencies = ConvertDependencies(courseDependencies);
 foreach (var myDependency in myDependencies) {
 //Check arg
 Debug.Assert(myDependency != null, "The dependency is never null.");
 //Create courses if needed
 Int32 myCourseID = myDependency.CourseID;
 Int32 myDependsOnCourseID = myDependency.DependsOn;
 Course myCourse = null;
 Course myDependsOnCourse = null;
 if (!myDict.TryGetValue(myCourseID, out myCourse)) {
 //Add course
 myCourse = new Course(myCourseID);
 myDict.Add(myCourseID, myCourse);
 }
 if (!myDict.TryGetValue(myDependsOnCourseID, out myDependsOnCourse)) {
 //Add course this one is depending on
 myDependsOnCourse = new Course(myDependsOnCourseID);
 myDict.Add(myDependsOnCourseID, myDependsOnCourse);
 }
 //Add dependency to course
 myCourse.AddDependency(myDependsOnCourse);
 }
 }
 //Convert the result to an array and sort it
 Course[] myResult = myDict.Values.ToArray();
 Array.Sort(myResult);
 //Return the result
 return myResult;
 }
 private static IEnumerable<CourseDependency> ConvertDependencies(Int32[,] courseDependencies) {
 //Check args
 Debug.Assert(courseDependencies != null, "The course dependency is never null!");
 //Convert array elements
 CourseDependency myDependency;
 for (var i = 0; i < courseDependencies.Length / 2; i++) {
 //Try to get values
 try {
 Int32 myCourseID = courseDependencies[i, 0];
 Int32 myDependsOn = courseDependencies[i, 1];
 myDependency = new CourseDependency(myCourseID, myDependsOn);
 } catch (Exception ex) {
 Debug.Assert(false, $"An exception of type {ex.GetType().Name} was thrown!\r\n{ex}");
 continue;
 }
 //Yield dependency
 yield return myDependency;
 }
 }
 //***********************************************************************************************
 // INNER CLASS: CourseDependency
 //***********************************************************************************************
 private class CourseDependency {
 //Constructors
 public CourseDependency(Int32 courseID, Int32 dependsOn) {
 //Check args
 if (courseID == dependsOn) throw new ArgumentException($"The course cannot depend on itself! (courseID = {courseID})");
 //Assign values
 CourseID = courseID;
 DependsOn = dependsOn;
 }
 //Public Properties
 public Int32 CourseID { get; }
 public Int32 DependsOn { get; }
 //Public Methods
 public override String ToString() {
 return $"{CourseID} needs {DependsOn}";
 }
 }
 }
}

Course.cs:

using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace _210CourseProject {
 public class Course : IComparable<Course> {
 //Private Fields
 private Dictionary<Int32, Course> _DependencyDict;
 private Dictionary<Int32, Course> _DependencyDictRecursive;
 //Constructors
 public Course(Int32 id) {
 CourseID = id;
 }
 //Public Properties
 public Int32 CourseID { get; }
 //Public Methods
 public void AddDependency(Course course) {
 //Check arg
 if (course == null) {
 Debug.Assert(false, "The course is never null.");
 return; //Ignore in production
 }
 //Check whether the dependency is already assigned
 var myDict = _DependencyDict;
 if (myDict != null) {
 Course myCourse = null;
 if (myDict.TryGetValue(course.CourseID, out myCourse)) {
 //If it's the same reference, ignore it
 if (Object.ReferenceEquals(myCourse, course)) {
 Debug.Assert(false, "Dependency was added multiple times!");
 return; //Ignore in production
 }
 //Otherwise throw an exception
 throw new ArgumentException($"An other instance of course {course.CourseID} was already added as dependency!", nameof(course));
 }
 }
 //Check self-dependency
 if (course.CourseID == this.CourseID) {
 Debug.Assert(false, $"The course (ID={course.CourseID}) cannot depend on itself!");
 return; //Ignore in production
 }
 //Check whether given course depends on us
 if (course.DependsOn(this, true)) {
 if (course.DependsOn(this, false)) {
 throw new ArgumentException($"Course {course.CourseID} depends on course {this.CourseID} and therefore cannot be assigned as dependency.", nameof(course));
 }
 throw new ArgumentException($"Course {course.CourseID} indirectly depends on course {this.CourseID} and therefore cannot be assigned as dependency.", nameof(course));
 }
 //Add dependency
 DependencyDict.Add(course.CourseID, course);
 _DependencyDictRecursive = null;
 }
 public Boolean DependsOn(Course otherCourse, Boolean recursive) {
 //Check arg
 if (otherCourse == null) {
 Debug.Assert(false, "The given course is never null.");
 return false; //Ignore in production
 }
 //Get direct/indirect dependencies
 var dict = recursive ? DependencyDictRecursively : _DependencyDict;
 if (dict == null) return false;
 //Return result
 var result = dict.ContainsKey(otherCourse.CourseID);
 return result;
 }
 public override String ToString() {
 return $"Course {CourseID}";
 }
 //Private Properties
 private Dictionary<Int32, Course> DependencyDict {
 get {
 var result = _DependencyDict;
 if (result == null) {
 result = new Dictionary<Int32, Course>(3);
 _DependencyDict = result;
 }
 return result;
 }
 }
 /// <summary>Gets the dependency dictionary containing direct and indirect dependencies. Watch out: The dictionary is null
 /// if there are no direct dependencies.</summary>
 private Dictionary<Int32, Course> DependencyDictRecursively {
 get {
 var result = _DependencyDictRecursive;
 if (result == null) {
 var myDirectDict = _DependencyDict;
 if (myDirectDict == null) return null;
 result = GetRecursiveDependency(myDirectDict);
 _DependencyDictRecursive = result;
 }
 return result;
 }
 }
 //Private Methods
 private static Dictionary<Int32, Course> GetRecursiveDependency(Dictionary<Int32, Course> directDependencies) {
 //Return null if null
 if (directDependencies == null) return null;
 //Get dependencies recursively
 var myResult = new Dictionary<Int32, Course>();
 foreach (Course myCourse in directDependencies.Values) {
 AddRecursiveDependency(myResult, myCourse);
 }
 //Return the result
 return myResult;
 }
 private static void AddRecursiveDependency(Dictionary<Int32, Course> resultDict, Course dependency) {
 //If already added, return
 if (resultDict.ContainsKey(dependency.CourseID)) return;
 //Add this dependencies
 resultDict.Add(dependency.CourseID, dependency);
 //Add child dependencies
 Dictionary<Int32, Course> myChildDict = dependency._DependencyDict;
 if (myChildDict == null) return;
 foreach (Course myChild in myChildDict.Values) {
 AddRecursiveDependency(resultDict, myChild);
 }
 }
 //Interface Implementation
 Int32 IComparable<Course>.CompareTo(Course other) {
 //Check arg
 if (other == null) {
 Debug.Assert(false, "The other is never null.");
 return 1; //Ignore in production
 }
 //Check dependencies
 if (this.CourseID == other.CourseID) return 0;
 if (this.DependsOn(other, true)) return 1;
 if (other.DependsOn(this, true)) return -1;
 if (this.CourseID > other.CourseID) return 1;
 if (this.CourseID < other.CourseID) return -1;
 return 0;
 }
 }
}

• Jianmin Chen: I like the solution you wrote. Beautiful and working C# code.