Count in-degrees of each node and build graph. Run Topological sort. Count the number of courses completed equals total number of courses.
public boolean canFinish(int numCourses, int[][] prerequisites) {
Map<Integer, Set<Integer>> map = new HashMap<>();
int[] indegree = new int[numCourses];
for (int[] pre : prerequisites) {
int from = pre[1], to = pre[0];
map.putIfAbsent(from, new HashSet<>());
map.get(from).add(to);
indegree[to]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < indegree.length; i++) {
if (indegree[i] == 0) {
q.offer(i);
}
}
while (!q.isEmpty()) {
int curt = q.poll();
numCourses--;
for (int next : map.getOrDefault(curt, new HashSet<>())) {
if (--indegree[next] == 0) {
q.offer(next);
}
}
}
return numCourses == 0;
}
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
graph = [[] for i in range(numCourses)]
indegree = [0] * numCourses
for v, u in prerequisites:
graph[u].append(v)
indegree[v] += 1
queue = []
for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)
visited = 0
while queue:
curt = queue.pop(0)
visited += 1
for next in graph[curt]:
indegree[next] -= 1
if indegree[next] == 0:
queue.append(next)
return visited == numCourses
Add visited courses to the list. Check if list size == numCourses before return.
public int[] findOrder(int numCourses, int[][] prerequisites) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
int[] indegree = new int[numCourses];
for (int[] p : prerequisites) {
graph.putIfAbsent(p[1], new HashSet<>());
graph.get(p[1]).add(p[0]);
indegree[p[0]]++;
}
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < indegree.length; i++) {
if (indegree[i] == 0) q.offer(i);
}
List<Integer> list = new ArrayList<>();
while (!q.isEmpty()) {
int curt = q.poll();
list.add(curt);
if (!graph.containsKey(curt)) continue;
for (int next : graph.get(curt)) {
indegree[next]--;
if (indegree[next] == 0) {
q.offer(next);
}
}
}
if (list.size() != numCourses) return new int[]{};
int[] res = new int[numCourses];
for (int i = 0; i < numCourses; i++) {
res[i] = list.get(i);
}
return res;
}
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
graph = [[] for i in range(numCourses)]
indegree = [0] * numCourses
for v, u in prerequisites:
graph[u].append(v)
indegree[v] += 1
queue = []
for i in range(numCourses):
if indegree[i] == 0:
queue.append(i)
res = []
while queue:
curt = queue.pop(0)
res.append(curt)
for next in graph[curt]:
indegree[next] -= 1
if indegree[next] == 0:
queue.append(next)
if len(res) == numCourses:
return res
return []
1. Given a dependency where for java packages p1,p2,p3
p1:{p2,p3}
p2:{p3}
p3:{}
This means p1 can be compiled when compilation of p2 and p3 done
p2 can compile when p3 is compiled
p3 can start as it does not have any dependence.
Write a function to calculate build order given a project with a list of dependencies that also need to be built.
Build the graph. Store indegrees in a different map. Check if all chars are in the array by using return sb.length() == indegree.size() ? sb.toString() : "";
public String alienOrder(String[] words) {
if(words == null || words.length == 0) return "";
Map<Character, Set<Character>> map = new HashMap<>();
Map<Character, Integer> indegree = new HashMap<>();
if (!buildGraph(map, indegree, words)) return "";
Queue<Character> queue = new LinkedList<>();
for (char key : indegree.keySet()) {
if (indegree.get(key) == 0) {
queue.offer(key);
}
}
if (queue.isEmpty()) return "";
StringBuilder sb = new StringBuilder();
while (!queue.isEmpty()) {
char curt = queue.poll();
sb.append(curt);
if (map.get(curt) == null) continue;
for (char next : map.get(curt)) {
indegree.put(next, indegree.get(next) - 1);
if (indegree.get(next) == 0) {
queue.offer(next);
}
}
}
return sb.length() == indegree.size() ? sb.toString() : "";
}
private boolean buildGraph(Map<Character, Set<Character>> map,
Map<Character, Integer> indegree,
String[] words) {
for (String word : words) {
for (char c : word.toCharArray()) indegree.put(c, 0);
}
for (int i = 0; i < words.length - 1; i++) {
String w1 = words[i], w2 = words[i + 1];
for (int k = 0; k < Math.min(w1.length(), w2.length()); k++) {
char u = w1.charAt(k), v = w2.charAt(k);
if (u != v) {
map.putIfAbsent(u, new HashSet<>());
if (!map.get(u).contains(v)) {
map.get(u).add(v);
indegree.put(v, indegree.getOrDefault(v, 0) + 1);
}
break;
}
if (k == Math.min(w1.length(), w2.length()) - 1 && w1.length() > w2.length()) {
return false;
}
}
}
return true;
}
Topological sort with lots of validations. Construct graph from provided sequences. Be care of when a sequence may exist multiple times, and there might be sequence with 1 size.
While traversing, check if the queue size > 1, this means there are multiple path. Also check if curt match with org[index++] and index is not out of bound.
As completed, check if traveled all nodes in org and graph.
public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
Map<Integer, Set<Integer>> graph = new HashMap<>();
Map<Integer, Integer> indegree = new HashMap<>();
for (List<Integer> s : seqs) {
if (s.size() == 1) {
int u = s.get(0);
graph.putIfAbsent(u, new HashSet<>());
indegree.put(u, indegree.getOrDefault(u, 0));
} else {
for (int i = 0; i < s.size() - 1; i++) {
int u = s.get(i), v = s.get(i + 1);
graph.putIfAbsent(u, new HashSet<>());
graph.putIfAbsent(v, new HashSet<>());
indegree.put(v, indegree.getOrDefault(v, 0));
indegree.put(u, indegree.getOrDefault(u, 0));
if (graph.get(u).add(v)) {
indegree.put(v, indegree.get(v) + 1);
}
}
}
}
Queue<Integer> q = new LinkedList<>();
for (int key : indegree.keySet()) {
if (indegree.get(key) == 0) {
q.offer(key);
}
}
int index = 0;
while (!q.isEmpty()) {
if (q.size() > 1) return false; // 精髓
int curt = q.poll();
if (index == org.length || curt != org[index++]) {
return false;
}
for (int next : graph.get(curt)) {
indegree.put(next, indegree.get(next) - 1);
if (indegree.get(next) == 0) {
q.offer(next);
}
}
}
return index == org.length && index == indegree.size();
}
Given a 2D array of distinct integers with n numbers, "compress" the array such that the resulting array's numbers are in the range [1, n] and their relative order is kept.
Relative order means that if a number at position (row1, col1) is smaller than a number at position (row2, col2) in the original array, it should still have that relationship in the resulting array.
Sort and reverse map the position and values.
public static int[][] compress2dArray(int[][] matrix) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
pq.offer(matrix[i][j]);
}
}
Map<Integer, Integer> map = new HashMap<>();
int k = 1;
while (!pq.isEmpty()) {
map.put(pq.poll(), k++);
}
int[][] res = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
res[i][j] = map.get(matrix[i][j]);
}
}
return res;
}
Follow-up:
Compress the array to make the numbers as small as possible as long as the relative order holds true for numbers in the same row and column.
Build DAG and count indegree. Use Topological sort with Level order traversal to assign values.
class Node {
int x,y,val;
Node(int x, int y, int val) {
this.x = x;
this.y = y;
this.val = val;
}
}
public int[][] compress2dArray2(int[][] matrix) {
Map<Node, Set<Node>> map = new HashMap<>();
Map<Node, Integer> indegree = new HashMap<>();
Node[][] nodes = new Node[matrix.length][matrix[0].length];
buildGraph(matrix, nodes, map, indegree);
Queue<Node> q = new LinkedList<>();
int[][] res = new int[matrix.length][matrix[0].length];
for (Node key : indegree.keySet()) {
if (indegree.get(key) == 0) {
q.offer(key);
}
}
int i = 1;
while (!q.isEmpty()) {
for (int k = q.size(); k > 0 ; k--) {
Node curt = q.poll();
res[curt.x][curt.y] = i;
if (map.get(curt) == null) continue;
for (Node next : map.get(curt)) {
indegree.put(next, indegree.get(next) - 1);
if (indegree.get(next) == 0) {
q.offer(next);
}
}
}
i++;
}
return res;
}
public void buildGraph(int[][] matrix,
Node[][] nodes,
Map<Node, Set<Node>> map,
Map<Node, Integer> indegree) {
int m = matrix.length, n = matrix[0].length;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
nodes[i][j] = new Node(i, j, matrix[i][j]);
}
}
for (int i = 0; i < m - 1; i++) {
for (int j = 0; j < n; j++) {
Node up = nodes[i][j], down = nodes[i + 1][j];
indegree.putIfAbsent(up, 0);
indegree.putIfAbsent(down, 0);
if (matrix[i][j] < matrix[i + 1][j]) {
map.putIfAbsent(up, new HashSet<>());
map.get(up).add(down);
indegree.put(down, indegree.get(down) + 1);
} else {
map.putIfAbsent(down, new HashSet<>());
map.get(down).add(up);
indegree.put(up, indegree.get(up) + 1);
}
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n - 1; j++) {
Node left = nodes[i][j], right = nodes[i][j + 1];
if (left.val < right.val) {
map.putIfAbsent(left, new HashSet<>());
map.get(left).add(right);
indegree.put(right, indegree.get(right) + 1);
} else {
map.putIfAbsent(right, new HashSet<>());
map.get(right).add(left);
indegree.put(left, indegree.get(left) + 1);
}
}
}
}