Short one based on CourseSchedule I (Java)


  • 0
    8

    The idea is same as topological sort in BFS.

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] ret = new int[numCourses], pre = new int[numCourses];
        HashMap<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>();
        for(int[] p : prerequisites) {
            pre[p[0]]++;
            if(!map.containsKey(p[1])) map.put(p[1], new ArrayList<Integer>());
            map.get(p[1]).add(p[0]);
        }
        int finishedCourses = 0;
        while(true) {
            int i = 0;
            for(; i < numCourses && pre[i] != 0; i++);
            if(i == numCourses) return new int[0];
            else {
                ret[finishedCourses] = i;
                pre[i]--;
                if(map.containsKey(i)) for(int c : map.get(i)) pre[c]--;
                if(++finishedCourses == numCourses) return ret;
            }
        }
    }

Log in to reply
 

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