Clean and easy to understand java solution. Nearly identical to Course Schedule I


  • 1
    D

    this solution has only 2 lines different from Course Schedule I solution. (check code in line)
    This one uses adjacency matrix to maitain graph status.
    Then use BFS to iterate all edges. Utilizes queue to store 0 indgree nodes. Then bfs tl last.
    Very easy to understand and perfect solution for interview.

    public class Solution {

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] ret = new int[numCourses];
        int[][] matrix = new int[numCourses][numCourses]; // i -> j
        int[] indegree = new int[numCourses];
    
        for (int i=0; i<prerequisites.length; i++) {
            int ready = prerequisites[i][0];
            int pre = prerequisites[i][1];
            if (matrix[pre][ready] == 0)
                indegree[ready]++; //duplicate case
            matrix[pre][ready] = 1;
        }
    
        int count = 0;
        Queue<Integer> queue = new LinkedList();
        for (int i=0; i<indegree.length; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }
        while (!queue.isEmpty()) {
            int course = queue.poll();
            count++;
            ret[count-1]= course;   ////THISLINE
            for (int i=0; i<numCourses; i++) {
                if (matrix[course][i] != 0){ 
                    if (--indegree[i] == 0)
                        queue.offer(i);
                }
            }
        }
        return count == numCourses ? ret : new int[0];  ////THISLINE
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.