I liked the note about the length and how other languages would calculate the length. With so much python sugar, we forget how a similar code would break in Java or C.
Perhaps slightly simpler (more familiar BFS) impl where we can get rid of the layer traversal technique. At the end of the while loop, all root will have the highest layer value (since they're the last layer) 😃 // Initialize layers with -1, except leaves layers are 0. int max_layer = 0; while (!q.empty()) { int u = q.front(); q.pop(); link[u]--; for (int v : adj[u]) { link[v]--; // Here, one of u's neighbors v just turned into a leaf node after u is removed. if (link[v] == 1 && layers[v] == -1) { layers[v] = layers[u] + 1; max_layer = max(max_layer, layers[v]); q.push(v); } } } vector res; for (int i = 0; i < n; i++) { if (layers[i] == max_layer) { res.push_back(i); } }
code: class Solution: def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]: if n==1: return [0] adj = defaultdict(list) for n1,n2 in edges: adj[n1].append(n2) adj[n2].append(n1) edgecount = {} leaves = deque() for s, nei in adj.items(): if len(nei)==1: leaves.append(s) edgecount[s]=len(nei) while leaves: if n
For the edge case, you could check if length of neighbours is 0 or 1, then it will pass the edge case, without having to create an seperate check for the edge case
You’re not supposed to come up with requirements and approach on the spot. You must know every possible problem or pattern by heart, because many do, so you’re looking bad compared to them. Sorry, that’s the game.
@@pixusru true, the people who post this arent solving this live and for the first time either. So solve as many as you can and spot patterns, recognize general strategies, things to think about when blocked etc
@@pixusru Tell that to interviewers at FAANG companies :(. I have spent a long time preparing for the code portion of an interview w/ one tomorrow (even though I already have another role essentially secured as a backup). There's always going to be the chance that you just don't spot the optimal solution at that time, no matter how prepped you are. For example, most FAANG would not accept the solution coded up here and would require the second approach he described (since it is O(n) time, O(1) memory- while the first is O(n)/O(n))
@@pixusru I agree on the pattern by heart part, but problem by heart? lol. That is not the meaning of DSA and the interview process and if that's your approach to interviews, you are hoping and praying for dumb luck to run into a problem you know during interviews.
Okay. At first I thought it was just BFS from the leaves until you have 2 or 1 left. Lots of tests failed. The whole subtracting edges thing went over my head. Second explanation was easy to get though I haven't tried it yet.
Brute : class Solution { public List findMinHeightTrees(int n, int[][] edges) { // Step 1: Initialize the adjacency matrix with large values int[][] matrix = new int[n][n]; for (int[] i : matrix) Arrays.fill(i, 100000); // Large number to indicate no direct path
// Step 2: Set the diagonal to 0 and fill in the edges (distance 1 for connected nodes) for (int i = 0; i < n; i++) matrix[i][i] = 0; for (int[] e : edges) { matrix[e[0]][e[1]] = 1; matrix[e[1]][e[0]] = 1; // Undirected graph, so both directions are set } // Step 3: Floyd-Warshall algorithm to calculate shortest paths between all pairs for (int k = 0; k < n; k++) { for (int row = 0; row < n; row++) { for (int col = 0; col < n; col++) { matrix[row][col] = Math.min(matrix[row][col], matrix[row][k] + matrix[k][col]); } } } // Print the resulting distance matrix (for debugging purposes) System.out.print(Arrays.deepToString(matrix)); // Step 4: Find the minimum height trees // For each node, calculate the maximum distance to any other node (its "height") int[] maxDist = new int[n]; int minHeight = Integer.MAX_VALUE; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { maxDist[i] = Math.max(maxDist[i], matrix[i][j]); } minHeight = Math.min(minHeight, maxDist[i]); } // Step 5: Collect all nodes whose maximum distance is equal to the minimum height List result = new ArrayList(); for (int i = 0; i < n; i++) { if (maxDist[i] == minHeight) { result.add(i); } } return result; } }
Proof why leaf nodes can't be a root of min path. Suppose exist a min path, where leaf node is a root A(leaf) - B(end) , the node A has one neighbor N and this neighbor has to be included into the path A-B , from this we can find a root with smaller path N-B
This problem should be renamed from "Minimum Height Trees" to "Find the root". We can imagine like cutting leaf from all sides equally at same level. What is left is root ( can be two node or one ).
One would argue that the goal is to find the median(s) node(s) of the longest path of the graph, and this median(s) would be the root of the MHT. why? because the median will partition the longest path in such a way that the max(left_partition,right_partition) will result in the minimum partition possible, which allows us to minimize the longest path and therefore to achieve the MHT. any thoughts? @NeetCodeIO #neetcode
I was only able to implement a brute force solution, but only 67 out of 71 test cases passed (got time limit exception). 😁Thanks for the video.
Thanks for this. Please do daily LCs and Contest please.
I liked the note about the length and how other languages would calculate the length. With so much python sugar, we forget how a similar code would break in Java or C.
Decreasing the number of edges is similar to Kahn's algorithm (topological sort) where indegree of a node is decreased as we traverse the tree.
But doesn't that only work with Directed graphs?
@@harshitdandelia4663 it should work only with acyclic graphs
Whenever I struggle with daily Leetcode problems, I turn to Neetcode
Ok
Great video as always! One thing that's worth mentioning is that if n
was thinking same
Yes, if the n
Perhaps slightly simpler (more familiar BFS) impl where we can get rid of the layer traversal technique. At the end of the while loop, all root will have the highest layer value (since they're the last layer) 😃
// Initialize layers with -1, except leaves layers are 0.
int max_layer = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
link[u]--;
for (int v : adj[u]) {
link[v]--;
// Here, one of u's neighbors v just turned into a leaf node after u is removed.
if (link[v] == 1 && layers[v] == -1) {
layers[v] = layers[u] + 1;
max_layer = max(max_layer, layers[v]);
q.push(v);
}
}
}
vector res;
for (int i = 0; i < n; i++) {
if (layers[i] == max_layer) {
res.push_back(i);
}
}
code:
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n==1:
return [0]
adj = defaultdict(list)
for n1,n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
edgecount = {}
leaves = deque()
for s, nei in adj.items():
if len(nei)==1:
leaves.append(s)
edgecount[s]=len(nei)
while leaves:
if n
Thank you so much for the daily. Really helps a lot.
I solved it using re-rooting. But this "Removing leaf nodes" solution is very amazing. I didn't thought of that.
Thank you so much!💖
This question was super hard, first I tried solving it with DP with memoization, it gave me TLE on test 70 I think
great explanation. thank you so much
For the edge case, you could check if length of neighbours is 0 or 1, then it will pass the edge case, without having to create an seperate check for the edge case
Hey Navdeep how are you? I love your leetcode explanations and your solutions! Gives me motivation to do more leetcode
it takes me over 15 minutes to be clear the requirement,and until i finished the solution, it takes more than 1 hour.
You’re not supposed to come up with requirements and approach on the spot. You must know every possible problem or pattern by heart, because many do, so you’re looking bad compared to them.
Sorry, that’s the game.
@@pixusru true, the people who post this arent solving this live and for the first time either.
So solve as many as you can and spot patterns, recognize general strategies, things to think about when blocked etc
@@pixusru Tell that to interviewers at FAANG companies :(. I have spent a long time preparing for the code portion of an interview w/ one tomorrow (even though I already have another role essentially secured as a backup). There's always going to be the chance that you just don't spot the optimal solution at that time, no matter how prepped you are.
For example, most FAANG would not accept the solution coded up here and would require the second approach he described (since it is O(n) time, O(1) memory- while the first is O(n)/O(n))
@@pixusru I agree on the pattern by heart part, but problem by heart? lol. That is not the meaning of DSA and the interview process and if that's your approach to interviews, you are hoping and praying for dumb luck to run into a problem you know during interviews.
No need to check if n==1: return[0], we can return [0] after the while loop and it will work fine.
Thank you, I needed this
really cool stuff man, thanks for the content
Missed you buddy 😭
Thanks for putting this up!
Thanks 😊
Okay. At first I thought it was just BFS from the leaves until you have 2 or 1 left. Lots of tests failed. The whole subtracting edges thing went over my head. Second explanation was easy to get though I haven't tried it yet.
Good one
Thanks for this
The brute force solution is still hard to do
Please tell me one thing, why for loop is required here? why only popleft() does not work here
Brute :
class Solution {
public List findMinHeightTrees(int n, int[][] edges) {
// Step 1: Initialize the adjacency matrix with large values
int[][] matrix = new int[n][n];
for (int[] i : matrix) Arrays.fill(i, 100000); // Large number to indicate no direct path
// Step 2: Set the diagonal to 0 and fill in the edges (distance 1 for connected nodes)
for (int i = 0; i < n; i++) matrix[i][i] = 0;
for (int[] e : edges) {
matrix[e[0]][e[1]] = 1;
matrix[e[1]][e[0]] = 1; // Undirected graph, so both directions are set
}
// Step 3: Floyd-Warshall algorithm to calculate shortest paths between all pairs
for (int k = 0; k < n; k++) {
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
matrix[row][col] = Math.min(matrix[row][col], matrix[row][k] + matrix[k][col]);
}
}
}
// Print the resulting distance matrix (for debugging purposes)
System.out.print(Arrays.deepToString(matrix));
// Step 4: Find the minimum height trees
// For each node, calculate the maximum distance to any other node (its "height")
int[] maxDist = new int[n];
int minHeight = Integer.MAX_VALUE;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
maxDist[i] = Math.max(maxDist[i], matrix[i][j]);
}
minHeight = Math.min(minHeight, maxDist[i]);
}
// Step 5: Collect all nodes whose maximum distance is equal to the minimum height
List result = new ArrayList();
for (int i = 0; i < n; i++) {
if (maxDist[i] == minHeight) {
result.add(i);
}
}
return result;
}
}
Proof why leaf nodes can't be a root of min path. Suppose exist a min path, where leaf node is a root A(leaf) - B(end) , the node A has one neighbor N and this neighbor has to be included into the path A-B , from this we can find a root with smaller path N-B
This problem should be renamed from "Minimum Height Trees" to "Find the root". We can imagine like cutting leaf from all sides equally at same level. What is left is root ( can be two node or one ).
Kahn's algorithm as intuition for this question. topsort(remove) where indegree ==1
edging to this rn
why do we return list(leaves) when n
Is it ok if after watching an entire video, didn't get the solution considering I only have a basic knowledge of graphs and DFS
Can you do a video using Morris traversal?
Was trying Union join
The second approach feels more intuitive for me...
Crazy hard
I think if you could have given the working of the two solutions , rather than going ahead and start writing the code , that would be much better.
can we say it's the middle of the diameter?
Is the time complexity of the code O(n) ?
i think yeah should be O(n). but just want someone to confirm
The algorithm here is called khan's algorithm and its TC will be O(V+E) where V is the number of vertices/nodes and E for the count of edges.
omg i hate graph problems, I hope one day they become less intimidating
neetcoede
One would argue that the goal is to find the median(s) node(s) of the longest path of the graph, and this median(s) would be the root of the MHT. why? because the median will partition the longest path in such a way that the max(left_partition,right_partition) will result in the minimum partition possible, which allows us to minimize the longest path and therefore to achieve the MHT. any thoughts? @NeetCodeIO #neetcode