This question is frequently asked at Amazon, Microsoft, DoorDash, and Google, and it is another Graphs problem:
There are a total of numCourses courses you have to take labelled from 0 to numCourses - 1 and you are given an array prerequisites where prerequisites[i] = [ai, bi] and it indicates that you must take course bi before you take course ai.
Return any possibilities, but if it is impossible to finish all the courses, return an empty array.
Here are some examples:
Input: numCourses = 4, prerequisites = [[1, 0], [2, 0], [3,1], [3,2]] can yield [0, 2, 1, 3]. So what I propose is that we take course 0 between 1 and to and course 1 and 2 before 3 so correct orderings are [0, 1, 2, 3] and [0, 2, 1, 3]. Here's my proposal:
Figure out if the graph is cyclic. If the graph isn't cyclic, I believe there is a possible solution then once we can mark all of the nodes, or keep a variable that keeps track of whether a particular node is active or not. We store all of the prerequisites and make sure none of the nodes interfere with the prerequisites. Here is an example of the cycles:
See there is a cycle between the purple node and the red node, even if it's not direct. This is why we need to keep check of the prerequisites.
There's 2 ways we can do this, and I'll go over both here.
The first way we can figure out is depth-first search which means we will consider all the possible paths.
We will initialize a stack that contain the sorted order of the courses of the graph, and we construct an adjacency list using the edge pairs given in the input.
For each node run dfs in case a node wasn't already visited. We finally add the node to the stack, and all the nodes that require the node as prerequisites will be in the stack. We return the nodes as they are present from the stack from the top to the bottom. So basically all we gotta do is topological sort here. :).
We mark white, gray, and black to indicated unvisited, visiting, and marked, respectively.
class Solution {
static int WHITE = 1; //unvisited
static int GRAY = 2; //visiting
static int BLACK = 3; //marked
boolean isPossible;
Map<Integer, Integer> color;
Map<Integer, List<Integer>> adjList;
List<Integer> topologicalOrder;
public void init(int numCourses) {
this.isPossible = true;
this.color = new HashMap<Integer, Integer>();
this.adjList = new HashMap<Integer, List<Integer>>();
this.topologicalOrder = new ArrayList<Integer>();
for(int i = 0; i < numCourses; i++) {
//every node starts at white.
this.color.put(i, WHITE);
}
}
public void dfs(int node) {
if(!this.isPossible) return;
this.color.put(node, GRAY);
for(Integer neighbor: this.adjList.getOrDefault(node, new ArrayList<Integer>()){
//run dfs if node is valid
if(this.color.get(neighbor) == WHITE) {this.dfs(neighbor);}
//otherwise if we get a neighbor that we found a cycle in we can't point another node to it since we now have a cycle.
else if (this.color.get(neighbor) == GRAY) {
this.isPossible = false;
}
}
}
public int[] findOrder(int numCourses, int[][] prerequisites) {
this.init(numCourses);
for(int i = 0; i < prerequisites.length; i++) {
int dest = prerequisites[i][0];
int src = prerequisites[i][1];
//put all the prerequisites and add the element to the adjacency list.
List<Integer> lst = adjList.getOrDefault(src, new ArrayList<Integer>());
lst.add(dest);
adjList.put(src, lst);
}
//perform DFS on the nodes that aren't empty.
for(int i = 0; i < numCourses; i++) {
if(this.color.get(i) == WHITE) this.dfs(i);
}
int[] order;
if(this.isPossible) {
//put the topological order in the list
order = new int[numCourses];
for(int i = 0; i < numCourses; i++) {
order[i] = this.topologicalOrder.get(numCourses - i - 1);
}
} else {
order = new int[0];
}
return order;
}
}
Now let's go over the alternate method: the indegree methods.
We first initialize a queue to keep track of nodes with 0 in degree and we will subsequently iterate over all the edges in the node and create an adjacency list, add the nodes with 0 indegree to the queue. Then we pop the node from queue and for all the neighbors reduce indegree by 1 and this is how we figure these nodes done in topologically sorted order.
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
boolean isPossible = true;
Map<Integer, List<Integer>> adjList = new HashMap<Integer, List<Integer>>();
int[] indegree = new int[numCourses];
//topological order
int[] topologicalOrder = new int[numCourses];
for(int i = 0; i < prerequisites.length; i++) {
int dest = prerequisites[i][0];
int src = prerequisites[i][1];
List<Integer> lst = adjList.getOrDefault(src, new ArrayList<Integer>());
//put in the adjacency list
list.add(dest);
adjList.put(src, lst);
indegree[dest] += 1;
}
Queue<Integer> q = new LinkedList<Integer>();
for(int i = 0; i < numCourses; i++) {
if(indegree[i] == 0) q.add(i);
}
}
int i = 0;
while(!q.isEmpty()) {
//remove the node from the queue
int node = q.remove();
topologicalOrder[i] = node;
i++;
if(adjList.containsKey(node)) {
for(Integer neighbor: adjList.get(node)){
//decrement the indegree
indegree[neighbor]--;
//add nodes with indegree to 0.
if(indegree[neighbor] == 0) {
q.add(neighbor);
}
}
}
}
if(i == numCourses) return topologicalOrder;
return new int[0];
}
}
Comments
Post a Comment