Topological Sort is used to find a linear ordering of elements that have dependencies on each other. For example, if event B is dependent on event A, A comes before B in topological ordering.
This pattern defines an easy way to understand the technique for performing topological sorting of a set of elements and then solves a few problems using it.
Let’s see this pattern in action.
Topological Sort of a directed graph (a graph with unidirectional edges) is a linear ordering of its vertices such that for every directed edge
(U, V)from vertexUto vertexV,Ucomes beforeVin the ordering.Given a directed graph, find the topological ordering of its vertices.
Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1]
Output: Following are the two valid topological sorts for the given graph:
1) 3, 2, 0, 1
2) 3, 2, 1, 0
Input: Vertices=5, Edges=[4, 2], [4, 3], [2, 0], [2, 1], [3, 1]
Output: Following are all valid topological sorts for the given graph:
1) 4, 2, 3, 0, 1
2) 4, 3, 2, 0, 1
3) 4, 3, 2, 1, 0
4) 4, 2, 3, 1, 0
5) 4, 2, 0, 3, 1
Input: Vertices=7, Edges=[6, 4], [6, 2], [5, 3], [5, 4], [3, 0], [3, 1], [3, 2], [4, 1]
Output: Following are all valid topological sorts for the given graph:
1) 5, 6, 3, 4, 0, 1, 2
2) 6, 5, 3, 4, 0, 1, 2
3) 5, 6, 4, 3, 0, 2, 1
4) 6, 5, 4, 3, 0, 1, 2
5) 5, 6, 3, 4, 0, 2, 1
6) 5, 6, 3, 4, 1, 2, 0
There are other valid topological ordering of the graph too.
The basic idea behind the topological sort is to provide a partial ordering among the vertices of the graph such that if there is an edge from U to V then U≤V i.e., U comes before V in the ordering.
Here are a few fundamental concepts related to topological sort:
- Source: Any node that has no incoming edge and has only outgoing edges is called a source.
- Sink: Any node that has only incoming edges and no outgoing edge is called a sink.
- So, we can say that a topological ordering starts with one of the sources and ends at one of the sinks.
- A topological ordering is possible only when the graph has no directed cycles, i.e. if the graph is a Directed Acyclic Graph (DAG). If the graph has a cycle, some vertices will have cyclic dependencies which makes it impossible to find a linear ordering among vertices.
To find the topological sort of a graph we can traverse the graph in a Breadth First Search (BFS) way. We will start with all the sources, and in a stepwise fashion, save all sources to a sorted list. We will then remove all sources and their edges from the graph. After the removal of the edges, we will have new sources, so we will repeat the above process until all vertices are visited.
- We will store the graph in Adjacency Lists, which means each parent vertex will have a list containing all of its children.
- We will do this using a HashMap where the
keywill be the parent vertex number and the value will be a List containing children vertices. - To find the sources, we will keep a HashMap to count the in-degrees i.e., count of incoming edges of each vertex. Any vertex with
0in-degree will be a source.
- We will build the graph from the input and populate the in-degrees HashMap.
- All vertices with
0in-degrees will be our sources and we will store them in a Queue.
- For each source, do the following things:
- Add it to the sorted list.
- Get all of its children from the graph.
- Decrement the in-degree of each child by
1. - If a child’s in-degree becomes
0, add it to the sources Queue.
- Repeat for each source, until the source Queue is empty.
Here is the visual representation of this algorithm for Example 3:
This is how we can implement this algorithm:
function topologicalSort(vertices, edges) {
const sortedOrder = [];
if (vertices <= 0) {
return sortedOrder;
}
//1. Initialize the graph
//count incoming edges
const inDegree = Array(vertices).fill(0);
//adjacency list graph
const graph = Array(vertices)
.fill(0)
.map(() => Array());
//2. Build the graph
edges.forEach((edge) => {
let parent = edge[0];
let child = edge[1];
//put the child into it's parent's list
graph[parent].push(child);
//increment child's inDegree
inDegree[child]++;
});
//3. Find all sources/vertices with 0 inDegrees
const sources = [];
for (let i = 0; i < inDegree.length; i++) {
if (inDegree[i] === 0) sources.push(i);
}
//4. For each sorce, add it to sortedOrder and decrement it children inDegree
//if a child become 0, add to source queue
while (sources.length > 0) {
const vertex = sources.shift();
sortedOrder.push(vertex);
graph[vertex].forEach((child) => {
//get the nodes children to dcrement thier inDegree
inDegree[child]--;
if (inDegree[child] === 0) {
sources.push(child);
}
});
// console.log(vertex)
}
// topological sort is not possible as the graph has a cycle
if (sortedOrder.length !== vertices) {
return [];
}
// console.log(inDegree, graph, sources)
return sortedOrder;
}
console.log(`Topological sort: ${topologicalSort(4, [[3, 2], [3, 0], [2, 0], [2, 1]])}`)
//Following are the two valid topological sorts for the given graph:
//1) 3, 2, 0, 1
//2) 3, 2, 1, 0
console.log(`Topological sort: ${topologicalSort(5, [[4, 2], [4, 3], [2, 0], [2, 1], [3, 1]])}`)
//Following are all valid topological sorts for the given graph:
// 1) 4, 2, 3, 0, 1
// 2) 4, 3, 2, 0, 1
// 3) 4, 3, 2, 1, 0
// 4) 4, 2, 3, 1, 0
// 5) 4, 2, 0, 3, 1
console.log(`Topological sort: ${topologicalSort(7, [[6, 4],[6, 2],[5, 3],[5, 4],[3, 0],[3, 1],[3, 2],[4, 1],])}`);
// Following are all valid topological sorts for the given graph:
// 1) 5, 6, 3, 4, 0, 1, 2
// 2) 6, 5, 3, 4, 0, 1, 2
// 3) 5, 6, 4, 3, 0, 2, 1
// 4) 6, 5, 4, 3, 0, 1, 2
// 5) 5, 6, 3, 4, 0, 2, 1
// 6) 5, 6, 3, 4, 1, 2, 0
// There are other valid topological ordering of the graph too.- In step
4, each vertex will become a source only once and each edge will be accessed and removed once. Therefore, the time complexity of the above algorithm will beO(V+E), whereVis the total number of vertices and ‘E’ is the total number of edges in the graph. - The space complexity will be
O(V+E), since we are storing all of the edges for each vertex in an adjacency list.
Find if a given Directed Graph has a cycle in it or not.
Solution: If we can’t determine the topological ordering of all the vertices of a directed graph, the graph has a cycle in it. This was also referred to in the above code:
if (sortedOrder.size() != vertices) // topological sort is not possible as the graph has a cycle
return new ArrayList<>();https://leetcode.com/problems/course-schedule/
There are
Ntasks, labeled from0toN-1. Each task can have someprerequisitetasks which need to be completed before it can be scheduled. Given the number oftasksand a list ofprerequisitepairs, find out if it is possible to schedule all thetasks.
This problem is asking us to find out if it is possible to find a topological ordering of the given tasks. The tasks are equivalent to the vertices and the prerequisites are the edges.
We can use a similar algorithm as described in Topological Sort to find the topological ordering of the tasks. If the ordering does not include all the tasks, we will conclude that some tasks have cyclic dependencies.
function isSchedulingPossible(tasks, prerequisites) {
const schedule = []
if(tasks <= 0) {
return false
}
//1. initialize the graph
//count incoming edges
const steps = Array(tasks).fill(0)
//adjacency list graph
const graph = Array(tasks).fill(0).map(()=>Array())
//2. Build the graph
prerequisites.forEach((prereq) =>{
let parent = prereq[0]
let child = prereq[1]
//put the child into it's parents list
graph[parent].push(child)
//increment childs step
steps[child]++
})
//3. Find all sources with 0 steps
const sources = []
for(let i = 0; i < steps.length; i++){
if(steps[i] === 0) sources.push(i)
}
//4. For each source, add it to schecule and decrement it's children steps
//if a child becomes 0, add to source queue
while(sources.length > 0){
const vertex = sources.shift()
schedule.push(vertex)
graph[vertex].forEach((child) =>{
//get the nodes children to decrement thier steps
steps[child]--
if(steps[child] === 0) sources.push(child)
})
}
console.log(steps,"steps", graph, "graph", schedule, "schedule")
// if schedule doesn't contain all tasks,
// there is a cyclic dependency between tasks,
// therefore, we will not be able to schedule all tasks
return schedule.length === tasks
};
console.log(`Is scheduling possible: ${isSchedulingPossible(3, [[0, 1], [1, 2]])}`)
//true
//To execute task '1', task '0' needs to finish first.
//Similarly, task '1' needs to finish before '2' can be scheduled.
//One possible scheduling of tasks is: [0, 1, 2]
console.log(`Is scheduling possible: ${isSchedulingPossible(3, [[0, 1], [1, 2], [2, 0]])}`)
// false
//The tasks have a cyclic dependency, therefore they cannot be scheduled.
console.log(`Is scheduling possible: ${isSchedulingPossible(6, [[0, 4], [1, 4], [3, 2], [1, 3]])}`)
// true
//A possible scheduling of tasks is: [0 1 4 3 2 5] - In step
4, each task can become a source only once, and each edge (i.e.,prereq) will be accessed and removed once. Therefore, the time complexity of the above algorithm will beO(V+E), whereVis the total number of tasks andEis the total number ofprerequisites. - The space complexity will be
O(V+E), since we are storing all of the prerequisites for each task in an adjacency list.
Course Schedule: There are N courses, labeled from 0 to N-1. Each course can have some prerequisite courses which need to be completed before it can be taken. Given the number of courses and a list of prerequisite pairs, find if it is possible for a student to take all the courses.
Solution: This problem is exactly similar to our parent problem. In this problem, we have courses instead of tasks.
https://leetcode.com/problems/course-schedule-ii/
There are
Ntasks, labeled from0toN-1. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, write a method to find the ordering of tasks we should pick to finish all tasks.
This problem is similar to Tasks Scheduling, the only difference being that we need to find the best ordering of tasks so that it is possible to schedule them all.
function findOrder(tasks, prerequisites) {
const schedule = []
if(tasks <= 0) {
return false
}
//1. initialize the graph
//count incoming edges
const steps = Array(tasks).fill(0)
//adjacency list graph
const graph = Array(tasks).fill(0).map(()=>Array())
//2. Build the graph
prerequisites.forEach((prereq) =>{
let parent = prereq[0]
let child = prereq[1]
//put the child into it's parents list
graph[parent].push(child)
//increment childs step
steps[child]++
})
//3. Find all sources with 0 steps
const sources = []
for(let i = 0; i < steps.length; i++){
if(steps[i] === 0) sources.push(i)
}
//4. For each source, add it to schecule and decrement it's children steps
//if a child becomes 0, add to source queue
while(sources.length > 0){
const vertex = sources.shift()
schedule.push(vertex)
graph[vertex].forEach((child) =>{
//get the nodes children to decrement thier steps
steps[child]--
if(steps[child] === 0) sources.push(child)
})
}
// if schedule doesn't contain all tasks,
// there is a cyclic dependency between tasks,
// therefore, we will not be able to schedule all tasks
if(schedule.length !== tasks){
return []
}
return schedule
};
console.log(`Is scheduling possible: ${findOrder(3, [[0, 1], [1, 2]])}`)
//To execute task '1', task '0' needs to finish first.
//Similarly, task '1' needs to finish before '2' can be scheduled.
//One possible scheduling of tasks is: [0, 1, 2]
console.log(`Is scheduling possible: ${findOrder(3, [[0, 1], [1, 2], [2, 0]])}`)
// []
//The tasks have a cyclic dependency, therefore they cannot be scheduled.
console.log(`Is scheduling possible: ${findOrder(6, [[2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1,3]])}`)
// true
//A possible scheduling of tasks is: [0 1 4 3 2 5] - In step
4, each task can become a source only once, and each edge (i.e.,prereq) will be accessed and removed once. Therefore, the time complexity of the above algorithm will beO(V+E), whereVis the total number of tasks andEis the total number of prerequisites. - The space complexity will be
O(V+E), since we are storing all of the prerequisites for each task in an adjacency list.
Course Schedule:
There are
Ncourses, labeled from0toN-1. Each course has someprerequisitecourses which need to be completed before it can be taken. Given the number of courses and a list ofprerequisitepairs, write a method to find the best ordering of the courses that a student can take in order to finish all courses.
Solution: This problem is exactly similar to our parent problem. In this problem, we have courses instead of tasks.
There are
Ntasks, labeled from0toN-1. Each task can have some prerequisite tasks which need to be completed before it can be scheduled. Given the number of tasks and a list of prerequisite pairs, write a method to print all possible ordering of tasks meeting all prerequisites.
This problem is similar to Tasks Scheduling Order, the only difference is that we need to find all of the topological orderings of the tasks.
At any stage, if we have more than one source available and since we can choose any source, therefore, in this case, we will have multiple orderings of the tasks. We can use a recursive approach with Backtracking to consider all sources at any step.
function printOrders(tasks, prerequisites) {
let possibleSchedules = [];
if (tasks.length <= 0) return possibleSchedules;
//1. Initialize graph
//count incoming edges
let steps = Array(tasks).fill(0);
//adjaceny list graph
const graph = Array(tasks)
.fill(0)
.map(() => Array());
//2. Build Graph
prerequisites.forEach((prereq) => {
let parent = prereq[0];
let child = prereq[1];
//put the child into it's parent list
graph[parent].push(child);
//increment child's steps
steps[child]++;
});
//3. Find sources with 0 steps
const sources = [];
for (let i = 0; i < steps.length; i++) {
if (steps[i] === 0) sources.push(i);
}
printAllTopologicalSorts(graph, steps, sources, possibleSchedules);
}
function printAllTopologicalSorts(graph, steps, sources, schedule) {
//4. For each source, add to schedule and decrement child steps
//if child === 0, add to source queue
if (sources.length > 0) {
for (let i = 0; i < sources.length; i++) {
const vertex = sources[i];
schedule.push(vertex);
//clone current sources
const sourcesForNextCall = sources.slice(0);
//only remove the current source
//all other sources will remain in queue for next call
sourcesForNextCall.splice(sourcesForNextCall.indexOf(vertex), 1);
graph[vertex].forEach((child) => {
//get the nodes for the children to decrement thier steps
steps[child]--;
if (steps[child] === 0) sourcesForNextCall.push(child);
});
//recursive call to print other ordering from the
//remaining and new sources
printAllTopologicalSorts(graph, steps, sourcesForNextCall, schedule);
//backtrack, remove the vertex from the schedule and put
//all of it's children back to consider the next source
//instead of the current vertex
schedule.splice(schedule.indexOf(vertex), 1);
for (let p = 0; p < graph[vertex].length; p++) {
steps[graph[vertex][p]]++;
}
}
}
// if schedule doesn't contain all tasks,
// there is a cyclic dependency between tasks,
// OR we have not processed all tasks in this recursive call
if (schedule.length === steps.length) console.log(schedule) ;
}
printOrders(3, [[0, 1],[1, 2]])
// [0, 1, 2]
// There is only possible ordering of the tasks.
printOrders(4, [[3, 2], [3, 0], [2, 0], [2, 1]])
// 1) [3, 2, 0, 1]
// 2) [3, 2, 1, 0]
// There are two possible orderings of the tasks meeting all prerequisites.
printOrders(6, [[2, 5], [0, 5], [0, 4], [1, 4], [3, 2], [1, 3]])
// 1) [0, 1, 4, 3, 2, 5]
// 2) [0, 1, 3, 4, 2, 5]
// 3) [0, 1, 3, 2, 4, 5]
// 4) [0, 1, 3, 2, 5, 4]
// 5) [1, 0, 3, 4, 2, 5]
// 6) [1, 0, 3, 2, 4, 5]
// 7) [1, 0, 3, 2, 5, 4]
// 8) [1, 0, 4, 3, 2, 5]
// 9) [1, 3, 0, 2, 4, 5]
// 10) [1, 3, 0, 2, 5, 4]
// 11) [1, 3, 0, 4, 2, 5]
// 12) [1, 3, 2, 0, 5, 4]
// 13) [1, 3, 2, 0, 4, 5]- If we don’t have any
prerequisites, all combinations of the tasks can represent a topological ordering. As we know, that there can beNcombinations forNnumbers, therefore the time and space complexity of our algorithm will beO(V! * E)whereVis the total number oftasksandEis the totalprerequisites. We need theEpart because in each recursive call, at max, we remove (and add back) all the edges.
https://leetcode.com/problems/alien-dictionary/
There is a dictionary containing
wordsfrom an alien language for which we don’t know the ordering of the alphabets. Write a method to find the correct order of the alphabets in the alien language. It is given that the input is a valid dictionary and there exists an ordering among its alphabets.
Since the given words are sorted lexicographically by the rules of the alien language, we can always compare two adjacent words to determine the ordering of the characters. Take Example 1 below: [“ba”, “bc”, “ac”, “cab”]
Take the first two words “ba” and “bc”. Starting from the beginning of the words, find the first character that is different in both words: it would be a from “ba” and c from “bc”. Because of the sorted order of words (i.e. the dictionary!), we can conclude that a comes before c in the alien language.
Similarly, from “bc” and “ac”, we can conclude that b comes before a.
These two points tell us that we are actually asked to find the topological ordering of the characters, and that the ordering rules should be inferred from adjacent words from the alien dictionary.
This makes the current problem similar to Tasks Scheduling Order, the only difference being that we need to build the graph of the characters by comparing adjacent words first, and then perform the topological sort for the graph to determine the order of the characters.
function findOrder(words) {
if(words.length === 0) return ''
//1. Initilize the graph, with hashmaps
//count of incoming edges
const steps = {}
//adjency list graph
const graph = {}
words.forEach((word) => {
for(let i = 0; i < word.length; i++){
steps[word[i]] = 0
graph[word[i]] = []
}
})
// 2. Build the graph
for(let i = 0; i < words.length-1;i++){
//find ordering of characters from adjacent words
let w1 = words[i]
let w2 = words[i+1]
for(let j = 0; j < Math.min(w1.length, w2.length); j++){
let parent = w1[j]
let child = w2[j]
//if the parent and child are different
if(parent !== child){
//put the child into it's parents list
graph[parent].push(child)
//increment childs step
steps[child]++
//only the first differenent character between the two words
//will help us find the order
break;
}
}
}
console.log(graph)
// 3. Find all sources(vertices with 0 steps)
const sources = []
const chars = Object.keys(steps)
chars.forEach((key) => {
if(steps[key] === 0){
sources.push(key)
}
})
console.log(steps)
// 4. For each source, add it to sortedDictionary and subtract 1 from all of it's children's steps
//if a childs step becomes 0, add it to the source queue
const sortedDictionary = []
while(sources.length > 0) {
let vertex = sources.shift()
sortedDictionary.push(vertex)
graph[vertex].forEach((child) => {
//get the node's children to decrement thier steps
steps[child]--
if(steps[child] === 0){
sources.push(child)
}
})
}
//if sortedDictionary doesn't contain all chars
//then there is a cyclic dependency between chars,
//then we will not be able to find the correct ordering of the chars
if(sortedDictionary.length !== chars.length) return ''
return sortedDictionary.join("");
};
console.log(`Character order: ${findOrder(["ba", "bc", "ac", "cab"])}`)
//bac
//Given that the words are sorted lexicographically by the rules of the alien language, so
//from the given words we can conclude the following ordering among its characters:
//1. From "ba" and "bc", we can conclude that 'a' comes before 'c'.
//2. From "bc" and "ac", we can conclude that 'b' comes before 'a'
//From the above two points, we can conclude that the correct character order is: "bac"
console.log(`Character order: ${findOrder(["cab", "aaa", "aab"])}`)
//cab
//From the given words we can conclude the following ordering among its characters:
//1. From "cab" and "aaa", we can conclude that 'c' comes before 'a'.
//2. From "aaa" and "aab", we can conclude that 'a' comes before 'b'
//From the above two points, we can conclude that the correct character order is: "cab"
console.log(`Character order: ${findOrder(["ywx", "wz", "xww", "xz", "zyy", "zwz"])}`)
//ywxz
//From the given words we can conclude the following ordering among its characters:
// 1. From "ywx" and "wz", we can conclude that 'y' comes before 'w'.
// 2. From "wz" and "xww", we can conclude that 'w' comes before 'x'.
// 3. From "xww" and "xz", we can conclude that 'w' comes before 'z'
// 4. From "xz" and "zyy", we can conclude that 'x' comes before 'z'
// 5. From "zyy" and "zwz", we can conclude that 'y' comes before 'w'
// From the above five points, we can conclude that the correct character order is: "ywxz"- In step 4, each task can become a source only once and each edge (a rule) will be accessed and removed once. Therefore, the time complexity of the above algorithm will be
O(V+E), whereVis the total number of different characters andEis the total number of the rules in the alien language. Since, at most, each pair of words can give us one rule, therefore, we can conclude that the upper bound for the rules isO(N)whereNis the number of words in the input. So, we can say that the time complexity of our algorithm isO(V+N). - The space complexity will be
O(V+N), since we are storing all of the rules for each character in an adjacency list.
https://leetcode.com/problems/sequence-reconstruction/
Given a sequence
originalSeqand an array ofsequences, write a method to find iforiginalSeqcan be uniquely reconstructed from the array ofsequences.Unique reconstruction means that we need to find if
originalSeqis the only sequence such that allsequencesin the array are subsequences of it.
Since each sequence in the given array defines the ordering of some numbers, we need to combine all these ordering rules to find two things:
- Is it possible to construct the
originalSeqfrom all these rules? - Are these ordering rules not sufficient enough to define the unique ordering of all the numbers in the
originalSeq? In other words, can these rules result in more than one sequence? Take Example 1:
originalSeq: [1, 2, 3, 4], seqs:[[1, 2], [2, 3], [3, 4]]The first sequence tells us that 1 comes before 2; the second sequence tells us that 2 comes before 3; the third sequence tells us that 3 comes before 4. Combining all these sequences will result in a unique sequence: [1, 2, 3, 4].
The above explanation tells us that we are actually asked to find the topological ordering of all the numbers and also to verify that there is only one topological ordering of the numbers possible from the given array of the sequences.
This makes the current problem similar to Tasks Scheduling Order with two differences:
- We need to build the graph of the numbers by comparing each pair of numbers in the given array of sequences.
- We must perform the topological sort for the graph to determine two things:
- Can the topological ordering construct the
originalSeq? - That there is only one topological ordering of the numbers possible. This can be confirmed if we do not have more than one source at any time while finding the topological ordering of numbers.
function canConstruct(originalSeq, sequences) {
let reconstructed = [];
if (originalSeq.length <= 0) return false;
// 1. Initialize the graph
//count of incoming edges
let steps = {};
//create adjacency list graph
let graph = {};
sequences.forEach((seq) => {
for (let i = 0; i < seq.length; i++) {
steps[seq[i]] = 0;
graph[seq[i]] = [];
}
});
// 2. Build the graph
sequences.forEach((seq) => {
for (let i = 1; i < seq.length; i++) {
const parent = seq[i - 1];
const child = seq[i];
graph[parent].push(child);
steps[child]++;
}
});
//if we dont have ordering rules for all the numbers
//we will not be able to UNIQUELY construct the sequence
const vertices = Object.keys(steps);
if (vertices.length !== originalSeq.length) return false;
// 3. Find all sources(all vertices with O steps)
const sources = [];
vertices.forEach((key) => {
if (steps[key] == 0) sources.push(key);
});
// console.log(steps)
// console.log(graph)
// 4.For each source, add it to the reconstructed and
//subtract one for all it's childrens steps
//if a childs steps become 0, add it to the source queue
while (sources.length > 0) {
if (sources.length > 1) {
//more than one source === more than
//one way to reconstruct the sequence
return false;
}
if (originalSeq[reconstructed.length] !== +sources[0]) {
//the next source(or number) is different from the originalSeq
return false;
}
const vertex = sources.shift();
reconstructed.push(vertex);
graph[vertex].forEach((child) => {
//get the node's children to decrement thier steps
steps[child]--;
if (steps[child] === 0) sources.push(child);
});
}
// if reconstructed's size !== orginalSeq's size
//there is no way to construct
return reconstructed.length === originalSeq.length;
}
console.log(`Can construct: ${canConstruct([1, 2, 3, 4], [[1, 2], [2, 3], [3, 4]])}`)
//true
//The sequences [1, 2], [2, 3], and [3, 4] can uniquely reconstruct [1, 2, 3, 4],
//in other words, all the given sequences uniquely define the order of numbers in the 'originalSeq'.
console.log(`Can construct: ${canConstruct([1, 2, 3, 4], [[1, 2], [2, 3], [2, 4]])}`)
//false
//The sequences [1, 2], [2, 3], and [2, 4] cannot uniquely reconstruct [1, 2, 3, 4].
//There are two possible sequences we can construct from the given sequences:
//1) [1, 2, 3, 4]
//2) [1, 2, 4, 3]
console.log(`Can construct: ${canConstruct([3, 1, 4, 2, 5], [[3, 1, 5], [1, 4, 2, 5]])}`)
//true
//The sequences [3, 1, 5] and [1, 4, 2, 5] can uniquely reconstruct [3, 1, 4, 2, 5].- In step 4, each task can become a source only once and each edge (a rule) will be accessed and removed once. Therefore, the time complexity of the above algorithm will be
O(V+E), whereVis the total number of different characters andEis the total number of the rules in the alien language. Since, at most, each pair of words can give us one rule, therefore, we can conclude that the upper bound for the rules isO(N)whereNis the number of words in the input. So, we can say that the time complexity of our algorithm isO(V+N). - The space complexity will be
O(V+N), since we are storing all of the rules for each character in an adjacency list.
https://leetcode.com/problems/minimum-height-trees/
We are given an undirected graph that has characteristics of a k-ary tree. In such a graph, we can choose any node as the root to make a k-ary tree. The root (or the tree) with the minimum height will be called Minimum Height Tree (MHT). There can be multiple MHTs for a graph. In this problem, we need to find all those roots which give us MHTs. Write a method to find all MHTs of the given graph and return a list of their roots.
Input: vertices: 5, Edges: [[0, 1], [1, 2], [1, 3], [2, 4]]
Output:[1, 2]
Explanation: Choosing '1' or '2' as roots give us MHTs. In the below diagram, we can see that the
height of the trees with roots '1' or '2' is three which is minimum.
Input: vertices: 4, Edges: [[0, 1], [0, 2], [2, 3]]
Output:[0, 2]
Explanation: Choosing '0' or '2' as roots give us MHTs. In the below diagram, we can see that the
height of the trees with roots '0' or '2' is three which is minimum.
Input: vertices: 4, Edges: [[0, 1], [1, 2], [1, 3]]
Output:[1]From the above-mentioned examples, we can clearly see that any leaf node (i.e., node with only one edge) can never give us an MHT because its adjacent non-leaf nodes will always give an MHT with a smaller height. All the adjacent non-leaf nodes will consider the leaf node as a subtree.
Let’s understand this with another example. Suppose we have a tree with root M and height 5. Now, if we take another node, say P, and make the M tree as its subtree, then the height of the overall tree with root P will be 6 (=5+1). Now, this whole tree can be considered a graph, where P is a leaf as it has only one edge (connection with M). This clearly shows that the leaf node P gives us a tree of height 6 whereas its adjacent non-leaf node M gives us a tree with smaller height 5 - since P will be a child of M.
This gives us a strategy to find MHTs. Since leaves can’t give us MHT, we can remove them from the graph and remove their edges too. Once we remove the leaves, we will have new leaves. Since these new leaves can’t give us MHT, we will repeat the process and remove them from the graph too. We will prune the leaves until we are left with one or two nodes which will be our answer and the roots for MHTs.
We can implement the above process using the topological sort. Any node with only one edge (i.e., a leaf) can be our source and, in a stepwise fashion, we can remove all sources from the graph to find new sources. We will repeat this process until we are left with one or two nodes in the graph, which will be our answer.
function findTrees(nodes, edges) {
if (nodes <= 0) return [];
//with only one node, we need to handle it seperatly since it's steps will be 0
if (nodes === 1) return [0];
// 1.Initialize the graph
//Count of incoming edges
const steps = Array(nodes).fill(0);
//adjacency list graph
const graph = Array(nodes)
.fill(0)
.map(() => Array());
// 2. Build the graph
edges.forEach((edge) => {
let node1 = edge[0];
let node2 = edge[1];
//this is an undirected graph, so we will add a link for both nodes
graph[node1].push(node2);
graph[node2].push(node1);
//increment the steps of both nodes
steps[node1]++;
steps[node2]++;
});
// 3. Find all leaves(all nodes with 1 step left)
const leaves = [];
for (let i = 0; i < steps.length; i++) {
if (steps[i] === 1) leaves.push(i);
// console.log(leaves)
}
// 4. Remove leaves level by level and decrement each leaves childrens steps
// repeat this until we are left with 1 or 2 nodes(our answer)
//any node that has already been a leaf cannot be the root of a MHT
//bc it's adjacent non-leaf node will always be the better option
let totalNodes = nodes;
while (totalNodes > 2) {
let leavesSize = leaves.length;
totalNodes -= leavesSize;
for (let i = 0; i < leavesSize; i++) {
let vertex = leaves.shift();
//get the node's children to decrement thier steps
graph[vertex].forEach((child) => {
//get the nodes children to decrement thier steps
steps[child]--;
if (steps[child] === 1) leaves.push(child);
});
}
}
// console.log(steps);
// console.log(graph);
return leaves;
}
console.log(`Roots of MHTs: ${findTrees(5, [[0, 1], [1, 2], [1, 3], [2, 4]])}`)
//[1, 2]
//Choosing '1' or '2' as roots give us MHTs. In the below diagram, we can see that the height of the trees with roots '1' or '2' is three which is minimum.
console.log(`Roots of MHTs: ${findTrees(4, [[0, 1], [0, 2], [2, 3]])}`)
//[0, 2]
//Choosing '0' or '2' as roots give us MHTs. In the below diagram,
//we can see that the height of the trees with roots '0' or '2' is three which is minimum.
console.log(`Roots of MHTs: ${findTrees(4, [[1, 2], [1, 3]])}`)
//[1]- In step 4, each task can become a source only once and each edge (a rule) will be accessed and removed once. Therefore, the time complexity of the above algorithm will be
O(V+E), whereVis the total number of different characters andEis the total number of the rules in the alien language. Since, at most, each pair of words can give us one rule, therefore, we can conclude that the upper bound for the rules isO(N)whereNis the number of words in the input. So, we can say that the time complexity of our algorithm isO(V+N). - The space complexity will be
O(V+N), since we are storing all of the rules for each character in an adjacency list.