Unable to Find Time Complexity

Viewed 9

Below I am attaching my code(complete) , pls help me get an idea of how to find time_complexity and space_complexity of my code , especially for adding , updating and copying the set. Thanks in Advance !!!

class Solution {
   public List<List<Integer>> getAncestors(int n, int[][] edges) {

        Set<Integer> [] ancestors = new Set[n] ;
        int [] in_degree = new int[n] ;
        List<Integer>[] li = new List[n] ;

        for (int i = 0; i < n; i++) {           // T.C. = O(n)
            ancestors[i] = new HashSet<> ();
            li[i] = new ArrayList<>() ;
        }
        // creating adj_list
        for(int []edge : edges){            // T.C. =  O(E)
            li[edge[0]].add(edge[1]) ;
            in_degree[edge[1]] ++ ;
        }

        helper(n , li , in_degree  , ancestors) ;

        // filling from (set) to List<Integer> in (lineage)
        List<List<Integer>> lineage = new ArrayList<>() ;
        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>() ;
            for(int j : ancestors[i]){
                list.add(j) ;       // copying set to list
            }
            Collections.sort(list);
            lineage.add(list) ;
        }
        return lineage ;
    }
//_____________________________________________________________________________________________________
    private void helper(int n, List<Integer>[]li, int [] in_degree , Set<Integer> [] ancestors) {
        Queue<Integer> q = new LinkedList<>() ;

        for (int i = 0; i < n; i++)  if(in_degree[i] == 0) q.add(i) ;       // T.C. = O(n)

        while(!q.isEmpty()){
            int node = q.remove() ;
            Set<Integer> grand_ancestors = ancestors[node] ;
            for(int u : li[node]){
                ancestors[u].add(node) ;
                ancestors[u].addAll(grand_ancestors) ;
                if(--in_degree[u] == 0) q.add(u) ;
            }
        }
    }
}
0 Answers
Related