Category: graph
-
LeetCode 2115: Find All Possible Recipes from Given Supplies
link We build a directed graph with vertex set as the union of recipes and ingredients. An edge represents . A topological order of recipes from this graph will give us the recipes we can make. We use in-degree approach. Say we start with supplies as the sources, therefore vertices with in-degree = 0. Then…
-
LeetCode 2246: Longest Path With Different Adjacent Characters
link If we had a simpler tree where for edge , s[u] != s[v], then our problem would be finding the length of the longest path in the tree. We can reduce the original problem to the above simpler problem by building an undirected graph having an edge only between different char’s. This is equivalent…
-
LeetCode 2392: Build a Matrix With Conditions
link The row indices of the numbers must be a permutation of row indices . Say we only have rowConditions — no conditions on the columns. We can build a directed graph with vertex set and edge set . Then, from a topological ordering of , we can find a valid permuation of row indices…
-
LeetCode 210: Course Schedule II
We build a directed graph where vertex set is the courses and an edge represents . So, input [0, 1] would be added as the edge . If the graph does not have a cycle, it is a DAG and we emit the courses in topological order. DFS Presence of back edge signals cycle in…
-
LeetCode 207: Course Schedule
link Check if the directed graph has cycle. An edge represents . In the input, [0, 1] means 1 has to be done before 0. So, we add edge in our graph. DFS Check if graph has back edge. Time and space complexity is that of DFS: . In-degree Check if all courses can be…
-
LeetCode 953: Verifying an Alien Dictionary
link Lexicographic order between two words can be thought of as comparing two same-length numbers with the shorter one padded with ‘s on the right. Since for three numbers , if and , then ; lexicographic order is transitive. Validating pairs of consecutive words is thus sufficient. With words, alphabet size , and the biggest…
-
LeetCode 269: Alien Dictionary
link We want to build a directed graph where vertex set is the alien alphabet and an edge represents: . A cycle in the graph signals and — a contradiction; so input is invalid. Otherwise, we emit the vertices in topological order. Single word Say words = [“confide”]. With a single word we do not…
unreasonably effective 