Java solution - explanation with example


  • 0
    V
    public class Solution {
        public int[] findOrder(int numCourses, int[][] prerequisites) {
            int[] emptyCourses = new int[]{};
            if(numCourses < 1) return emptyCourses;
    
            /* 
             define an array to maintain the count of prereqs a course has,
             so that later we can start visiting from the courses which doesn't 
             have  any prereq's
            */
            int[] prereqCount = new int[numCourses];
    
            // this list will maintain the relation of [ prereq ->  List<course>]
            /* this is needd so that we know what to visit next whle visiting 
               courses in order */
            /* 
              For eg. is course '1' is a prereq for 2 and 3, then if we have 
              visited 1, we can next go to 2 and 3
              if 2 & 3 doesn't have any other prereq other than '1'
            */
            List<List<Integer>> prereqs = new ArrayList<List<Integer>>(numCourses);
            int n = numCourses;
            while(n-- != 0) prereqs.add(new ArrayList<>());
            
            for(int[] arr : prerequisites) {
                /* increment the counter for number of prereqs for a 
                   particular course
                */
                prereqCount[arr[0]]++;
                // For eg. in [1 2] (2 is prereq for 1), add 1 to list of '2'
                prereqs.get(arr[1]).add(arr[0]);
            }
            
            Queue<Integer> visited = new LinkedList<>();
            int[] coursesTaken = new int[numCourses];
            int currentCourse = 0;
            
            for(int i = 0; i<numCourses; i++) {
                if(prereqCount[i] == 0) visited.add(i);
            }
            
            while(!visited.isEmpty()) {
                int visit = visited.poll();
                coursesTaken[currentCourse++] = visit;
                /* 
                - whenever we visit a course, we can next check which all
                courses have this visited course as a prereq.
                -For eg. if 3 was a prereq for 2,4,5 then it means one prereq is 
                  done for all these courses.
                - So now traverse that list and decrement the counter of 
                prereqCount of each course in that list 2,4 & 5
               
               - Now after decrementing, if prereqCount[course in list == 0], 
                 then it means we can visit that course too as there are no more 
                 prereqs, so add it to the visit Queue.
               */
                List<Integer> nextInOrder = prereqs.get(visit);
                for(int c: nextInOrder) {
                    if(--prereqCount[c] == 0) visited.add(c);
                }
            }
            
            // now if we have visited expected nnumber of courses then return the order of courses we took.
            // Note that there can be more than 1 order because there could be >1 course which has no prereq, so we could have started with any of it in our visited Queue, hence multiple correct answer
            if(currentCourse == numCourses) return coursesTaken;
            else return emptyCourses;
        }
    }
    

Log in to reply
 

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