[JAVA] Beats 95% Java Submisioms | With Proper Explanation & TC/SC | Modularised Code
Note:- Do give it a upvote,if my explanation helps as it will be a source of motivation for me!!\n# Intuition\n Describe your first thoughts on how to solve thi
### Note:- Do give it a upvote,if my explanation helps as it will be a source of motivation for me!!\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nKey observations here are:-\n1. Time taken to collect a apple is 2 (1 for coming, 2 for going back)\n2. Since we need to collect all apples, so its obvious we would traverse the graph/tree.\n3. Let\'s say A has 2 childs b & c. So it doesnt matter even if any one of nodes has an apple, it will still consume time.\n4. We dont involve the staring node (0 in this case) for calculating the time.\n# Approach\n<!-- Describe your approach to solving the problem. -->\nHere we are given adjacent matrix, first we need to build a adjacent list for us to perform DFS traversal.\n\nWe adopt a DFS startegy, where we visit every node in depth wise direction. When a node has an apple and isnt a root node, we increment the count by 2, else we just return the count.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(N) - Where N is the node of Nodes\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nRecursive Stack space O(N) + O(N) [Where N is the node of Nodes]\n# Code\n```\nclass Solution {\n    public int minTime(int n, int[][] edges, List<Boolean> hasApple) {\n        int l=0;\n        for(int i=0;i<hasApple.size();i++){\n            if(hasApple.get(i)==false)l++;\n            else break;\n        }\n        if(l==hasApple.size())return 0;\n        ArrayList<ArrayList<Integer>> adjList = buildAjList(edges);\n        boolean[] vis = new boolean[n];\n        return dfs(0,adjList,hasApple,vis);\n    }\n\n    public int dfs(int node,ArrayList<ArrayList<Integer>> adjList,List<Boolean> hasApple,boolean[] vis){\n        int c=0;\n        vis[node]=true;\n        for(Integer it:adjList.get(node)){\n            if(vis[it]==false){\n            c+=dfs(it,adjList,hasApple,vis);\n            }\n        }\n        if((c>0||hasApple.get(node))&&node!=0) c+=2;\n        return c;\n    }\n\n    public ArrayList<ArrayList<Integer>> buildAjList(int[][] edges){\n        ArrayList<ArrayList<Integer>> adjList = new ArrayList<ArrayList<Integer>>();\n        for(int i=0;i<=edges.length;i++)\n            adjList.add(new ArrayList<Integer>());\n\n        for(int i=0;i<edges.length;i++){\n            adjList.get(edges[i][0]).add(edges[i][1]);\n            adjList.get(edges[i][1]).add(edges[i][0]);\n        }\n        return adjList;\n    }\n}\n```
['Array', 'Tree', 'Depth-First Search', 'Graph', 'Java']