SHARE
TWEET

Untitled

ogv Sep 23rd, 2019 75 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // Runtime: 3 ms, faster than 96.33% of Java online submissions for Course Schedule II.
  2. // Memory Usage: 45.4 MB, less than 92.68% of Java online submissions for Course Schedule II.
  3. class Solution {
  4.     public int[] findOrder(int numCourses, int[][] prerequisites) {
  5.         int[] dc = new int[numCourses];
  6.        
  7.         LinkedList<Integer>[] deps = new LinkedList[numCourses];        
  8.         for (int i = 0; i < numCourses; i++) deps[i] = new LinkedList<Integer>();
  9.        
  10.         for (int[] req: prerequisites) {
  11.             deps[req[1]].add(req[0]);
  12.             dc[req[0]]++;
  13.         }
  14.        
  15.         Queue<Integer> q = new LinkedList<>();
  16.         for (int node = 0; node < numCourses; node++)
  17.             if (dc[node] == 0) q.add(node);
  18.        
  19.         int[] res = new int[numCourses];
  20.         int rPos = 0;
  21.        
  22.         while (q.size() > 0) {
  23.             int node = q.remove();
  24.             for (int d: deps[node]) if (--dc[d] == 0) q.add(d);
  25.             res[rPos++] = node;
  26.         }
  27.        
  28.         if (rPos < numCourses) return new int[0];
  29.        
  30.         return res;
  31.     }      
  32. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top