Where am I wasting time here


  • 0
    V

    Hi,

    I came with this solution based on BFS. I believe it works for small cases but run out of time for large trees. Obviously I'm doing superfluous work but I'm not sure where. Any help would be appreciated.

    public class Solution {
        public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            List<Integer> winners = new ArrayList<>();
            int minDepth = Integer.MAX_VALUE;
            
            HashSet<Integer> links[] = new HashSet[n];
            
            for(int i = 0; i < links.length; i++) links[i] = new HashSet<>();
            
            for(int[] edge : edges) {
                links[edge[0]].add(edge[1]);
                links[edge[1]].add(edge[0]);
            }
            
            for(int i = 0; i < n; ++i) {
                int mhtHeight = findMinHeightTree(i, n, links);
                
                if(mhtHeight == minDepth) {
                    winners.add(i);
                } else if(mhtHeight < minDepth) {
                    winners.clear();
                    winners.add(i);
                    minDepth = mhtHeight;
                }
                
            }
            
            return winners;
        }
        
        public Integer findMinHeightTree(int root, int n, HashSet<Integer>[] edges) {
            int minDepth = Integer.MAX_VALUE;
            
            Set<Integer> markedNode = new HashSet<>();
            Queue<Integer> q = new ArrayDeque<>();
            Map<Integer,Integer> depths = new TreeMap<>();
            
            q.add(root);
            markedNode.add(root);
            depths.put(root, 0);
            
            while(!q.isEmpty()) {
                int node = q.remove();
                
                boolean isLeaf = true;
                for(int i = 0; i < n; i ++) {
                    if(edges[node].contains(i) && !markedNode.contains(i)) {
                        isLeaf = false;
                        markedNode.add(i);
                        int depth = depths.get(node) + 1;
                        depths.put(i, depth);
                        
                        if(depth < minDepth)
                            q.add(i);
                    }    
                }
            
                if(isLeaf) {
                    int depth = depths.get(node);
                    if(depth < minDepth) minDepth = depth;
                }
            }
            
            return minDepth;
        }

  • 0
    K

    bhai help mile to hume bhi batana


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.