Coding

Course Schedule II

Asked at

Atlassian

Flipkart

Paytm

Salesforce

Uber

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

There are a total of N tasks, labeled from 0 to N-1. Given an array arr where arr[i] = [a, b] indicates that you must take course b first if you want to take course** a. **Find the order of tasks you should pick to finish all tasks. If no such ordering exists, return an empty array. Since multiple valid answers are possible, you can return any answer.

Note : The output visible will be 1 if your solution is correct, otherwise -1.

Input: N = 4, arr = [[1,0],[2,1],[3,2]] Output: [0, 1, 2, 3] Explanation: First,finish task 0, as it has no prerequisites. Then,finish task 1, since it depends only on task 0. After that,finish task 2, since it depends only on task 1. Finally,finish task 3, since it depends only on task 2

Input: N = 4, arr = [[0,1],[3,2],[1,3],[3,0]] Output: [] Explanation: It is impossible to finish all the tasks. Let’s analyze the pairs: For pair {0, 1} → we need to finish task 1 first and then task 0 (order: 1 → 0). For pair {3, 2} → we need to finish task 2 first and then task 3 (order: 2 → 3). For pair {1, 3} → we need to finish task 3 first and then task 1 (order: 2 → 3 → 1 → 0). But for pair {3, 0} → we need to finish task 0 first and then task 3, which contradicts the previous order. So, it is not possible to finish all the tasks.

Input: N = 2, arr = [[1,0]]

1 <= N <= 2000
0 <= arr.length <= 5000
arr[i].length == 2
0 <= arr[i][0], arr[i][1] < N
All the pairs arr[i] are unique.

cpp

class Solution {
  public: vector < int > findOrder(int N, vector < vector < int >> arr) {
   
  }
};

java

class Solution {
    public int[] findOrder(int N, int[][] arr) {
       
    }
}

python

class Solution:
    def findOrder(self, N, arr):

javascript

class Solution {
    findOrder(N, arr) {
        
    }
}

csharp

class Solution {
    public int[] FindOrder(int N, int[][] arr) {

    }
}

func findOrder(N int, arr [][]int) []int {

}

Stuck? Show a way to structure it+

01Translate each prerequisite [course, prerequisite] into an edge prerequisite -> course.
02Compute every node's indegree and enqueue all zero-indegree courses.
03Repeatedly remove a course, append it to the order, and release its dependent courses.
04Return the order only if it contains all N courses; otherwise a cycle exists and the answer is empty.

Reference answer

Model the tasks as a directed graph. For each pair [a, b], add an edge b -> a because task b must be completed before task a, and increment indegree[a]. Put every task with indegree zero into a queue. These tasks currently have no unmet prerequisite.

While the queue is not empty, remove one task, append it to the result, and visit each dependent task. Decrement that dependent's indegree; when it reaches zero, enqueue it. This is Kahn's topological-sort algorithm.

At the end, if the result contains exactly N tasks, it is a valid completion order. If fewer than N tasks were processed, the remaining nodes belong to or depend on a directed cycle, so no valid ordering exists and we return an empty array. Multiple answers are valid because zero-indegree tasks may be chosen in any order.

Building and processing the graph takes O(N + E) time and O(N + E) space, where E is the number of prerequisite pairs.

Then expect these follow-ups

How would you implement the same cycle check with DFS colors?
Tests: graph fundamentals
How would you return the lexicographically smallest valid order?
Tests: data-structure choice

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question