Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
What would be a N^2 solution?
What is a minimum height tree?
What is the degree of the node?
HAPPY CASE
Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]
EDGE CASE
Input: n = 7, edges = [[0,1],[1,2],[1,3],[2,4],[3,5],[4,6]]
Output: [1,2]
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For graph problems, some things we want to consider are:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Filter out the roots that have the minimal height among all the trees
The idea is keep removing all of the leaves until there is the last layer of leaves, then those are the roots of the minimum height trees. Using an arrayList, add the first layer of leaves. Because when we break the longest branch in half, there can be at most 2 things at the top. If there are three, then we can break again. Remove all the other occurrences of this leaf from other rows that the leaf is associated with. Remove the row of the current leaf from the adjacency list.
⚠️ Common Mistakes
Implement the code to solve the algorithm.
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
// edge cases
if (n < 2) {
ArrayList<Integer> centroids = new ArrayList<>();
for (int i = 0; i < n; i++)
centroids.add(i);
return centroids;
}
// Build the graph with the adjacency list
ArrayList<Set<Integer>> neighbors = new ArrayList<>();
for (int i = 0; i < n; i++)
neighbors.add(new HashSet<Integer>());
for (int[] edge : edges) {
Integer start = edge[0], end = edge[1];
neighbors.get(start).add(end);
neighbors.get(end).add(start);
}
// Initialize the first layer of leaves
ArrayList<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; i++)
if (neighbors.get(i).size() == 1)
leaves.add(i);
// Trim the leaves until reaching the centroids
int remainingNodes = n;
while (remainingNodes > 2) {
remainingNodes -= leaves.size();
ArrayList<Integer> newLeaves = new ArrayList<>();
// remove the current leaves along with the edges
for (Integer leaf : leaves) {
// the only neighbor left for the leaf node
Integer neighbor = neighbors.get(leaf).iterator().next();
// remove the edge along with the leaf node
neighbors.get(neighbor).remove(leaf);
if (neighbors.get(neighbor).size() == 1)
newLeaves.add(neighbor);
}
// prepare for the next round
leaves = newLeaves;
}
// The remaining nodes are the centroids of the graph
return leaves;
}
}
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
# edge cases
if n <= 2:
return [i for i in range(n)]
# Build the graph with the adjacency list
neighbors = [set() for i in range(n)]
for start, end in edges:
neighbors[start].add(end)
neighbors[end].add(start)
# Initialize the first layer of leaves
leaves = []
for i in range(n):
if len(neighbors[i]) == 1:
leaves.append(i)
# Trim the leaves until reaching the centroids
remaining_nodes = n
while remaining_nodes > 2:
remaining_nodes -= len(leaves)
new_leaves = []
# remove the current leaves along with the edges
while leaves:
leaf = leaves.pop()
# the only neighbor left for the leaf node
neighbor = neighbors[leaf].pop()
# remove the only edge left
neighbors[neighbor].remove(leaf)
if len(neighbors[neighbor]) == 1:
new_leaves.append(neighbor)
# prepare for the next round
leaves = new_leaves
# The remaining nodes are the centroids of the graph
return leaves
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Time Complexity: O(V)
, where V
represents the number of nodes in the graph
Space Complexity: O(V)
, where V
represents the number of nodes in the graph