Leetcode 1443. Minimum Time to Collect All Apples in a Tree
Problem Explanation
We are provided with n
number of vertices (represented as 0 to n-1), forming an undirected tree. Some vertices can contain apples. Our task is to find the minimum time required to collect all apples in the tree given that:
- We start and end at vertex 0.
- Every move we make from one vertex to another represents 1 second.
We are provided with an array of edges
indicating the connections between vertices and an array hasApple
with boolean values indicating the presence of an apple in a certain vertex.
Our aim is to calculate the minimum time in seconds we would need to make a round trip from vertex 0, collect all the apples, and return back to vertex 0.
Detailed Problem Approach
The problem can be solved using Depth First Search (DFS) algorithm.
Step 1:
Create an adjacency list/data structure to map each node to all its neighboring nodes. This data structure represents a graph.
Step 2:
Start from the root node (0 in this case), and traverse all the neighboring nodes using DFS.
For each vertex, consider the cost to collect apples in its subtree. If a vertex has an apple or it has a child that has an apple, we need to spend 2 seconds reaching it (going to it and coming back). The total time spent for this vertex is the sum of the time spent on its children + 2 (if it has an apple or a child having an apple).
Step 3:
Keep on traversing the tree using DFS. Continue the DFS until you visit all vertices.
Step 4:
The final time cost calculated in the end represents the minimum time needed to collect all apples and return to vertex 0.
Example:
Let's walk through an example:
1 2 3n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]
In this case, we have vertices from 0 to 6. From the edges
array, we can infer the connections between them. The hasApple
array indicates the presence of an apple in vertices 2, 4 and 5.
Starting from vertex 0, we traverse through the tree. From 0, we move to vertex 1 (1 second) and from there, we proceed to 4 (1 second) to collect an apple. We go back to 1 (1 second) and move to 5 (1 second) to collect another apple. We again go back to 1 and then to 0 (2 seconds), making the total time 6 seconds.
From 0, we now traverse to vertex 2 (1 second), collect an apple and come back to 0 (1 second). This makes the total time 6 (collected from the 0-1-4-5 path) + 2 (collected from the 0-2 path) = 8
seconds.
This gives us the minimum time needed to collect all apples and return to vertex 0.
C++ Solution:
1
2cpp
3class Solution {
4 public:
5 int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
6 // Create adjacency list for graph representation
7 vector<vector<int>> graph(n);
8 // Fill graph with edges
9 for (const vector<int>& edge : edges) {
10 const int u = edge[0];
11 const int v = edge[1];
12 graph[u].push_back(v);
13 graph[v].push_back(u);
14 }
15 return dfs(graph, 0, vector<bool>(n), hasApple);
16 }
17
18 private:
19 int dfs(const vector<vector<int>>& graph, int u, vector<bool>&& seen,
20 const vector<bool>& hasApple) {
21 seen[u] = true;
22 int totalCost = 0;
23 // Traverse through connected vertices
24 for (const int v : graph[u]) {
25 if (seen[v])
26 continue;
27 const int cost = dfs(graph, v, move(seen), hasApple);
28 // Update cost if it has apple or it's subtree has apple
29 if (cost > 0 || hasApple[v])
30 totalCost += cost + 2;
31 }
32 // return total time cost
33 return totalCost;
34 }
35 };
Python Solution:
1 2python 3from typing import List 4from collections import defaultdict 5 6class Solution: 7 def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int: 8 # Create adjacency list for graph representation 9 graph = defaultdict(list) 10 # Fill graph with edges 11 for u, v in edges: 12 graph[u].append(v) 13 graph[v].append(u) 14 return self.dfs(graph, hasApple, 0, -1) 15 16 def dfs(self, graph: dict, hasApple: List[bool], node: int, parent: int) -> int: 17 total_time = 0 18 # Traverse through connected vertices 19 for child in graph[node]: 20 if child != parent: 21 total_time += self.dfs(graph, hasApple, child, node) 22 # Add 2 in total_time if visiting current node is beneficial 23 if (node != 0 and (hasApple[node] or total_time > 0)): 24 total_time += 2 25 26 return total_time
Java Solution:
1
2java
3class Solution {
4 public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
5 // Create adjacency list for graph representation
6 List<Integer>[] graph = new ArrayList[n];
7 for (int i = 0; i < n; i++)
8 graph[i] = new ArrayList<>();
9 // Fill graph with edges
10 for (int[] edge : edges){
11 int u = edge[0], v = edge[1];
12 graph[u].add(v);
13 graph[v].add(u);
14 }
15 return dfs(graph, 0, new boolean[n], hasApple);
16 }
17
18 private int dfs(List<Integer>[] graph, int u, boolean[] seen, List<Boolean> hasApple) {
19 seen[u] = true;
20 int totalTime = 0;
21 for (int v : graph[u]) {
22 if (seen[v])
23 continue;
24 int tempTime = dfs(graph, v, seen, hasApple);
25 // Update tempTime if visiting the node v is needed (itself or subtree has an apple)
26 if (tempTime > 0 || hasApple.get(v))
27 totalTime += tempTime + 2;
28 }
29 return totalTime;
30 }
31}
Note: In JavaScript, there is no direct way to create an adjacency list using associated array like Python. We can use a Map or a 2D array for this.
JavaScript Solution:
1
2javascript
3var minTime = function(n, edges, hasApple) {
4 let graph = new Map(); // Create a Map for graph representation
5 for(let edge of edges){ // Fill graph with edges
6 if(!graph.has(edge[0])) graph.set(edge[0],[]);
7 if(!graph.has(edge[1])) graph.set(edge[1],[]);
8 graph.get(edge[0]).push(edge[1]);
9 graph.get(edge[1]).push(edge[0]);
10 }
11 return dfs(graph, hasApple, 0, 0, 0);
12};
13
14function dfs(graph, hasApple, current, parent){
15 let total = 0;
16 for(let child of graph.get(current)){
17 if(child == parent) continue;
18 total += dfs(graph, hasApple, child, current);
19 }
20 // Cascade all the way up
21 if((hasApple[current] || total > 0) && current!=0) total += 2;
22 return total;
23}
C# Solution:
1
2csharp
3using System;
4using System.Collections.Generic;
5
6public class Solution {
7 public int MinTime(int n, int[][] edges, IList<bool> hasApple) {
8 List<int>[] graph = new List<int>[n];
9 // create a new List for each vertices in graph
10 for (int i=0; i<n; i++){
11 graph[i] = new List<int>();
12 }
13 // Fill graph with edges
14 foreach(int[] edge in edges){
15 int u = edge[0], v = edge[1];
16 graph[u].Add(v);
17 graph[v].Add(u);
18 }
19
20 return DFS(graph, 0, hasApple, new bool[n]);
21 }
22
23 private int DFS(List<int>[] graph, int u, IList<bool> hasApple, bool[] seen) {
24 seen[u] = true;
25 int total = 0;
26
27 foreach (int v in graph[u]){
28 if (seen[v]) continue;
29 int time = DFS(graph, v, hasApple, seen);
30 // update the time if node v itself or it's subtree has an apple
31 if (time > 0 || hasApple[v]) total += time + 2;
32 }
33
34 return total;
35 }
36}
In conclusion, we have solved the common problem of traversing trees to collect a certain element, in this case, apples. Irrespective of the language used, we have seen that the Depth First Search algorithm was crucial in identifying nodes that contain an apple and providing a way to navigate the tree. Further, by representing the tree as a graph, we are able to easily traverse it and keep count of the time spent. Additionally, we avoid visiting already visited nodes through the use of a 'seen' list or array alongside the 'hasApple' list to keep track of which vertices contain an apple. Implementing problems like these provides good practice for bigger, more complex problems where navigation of a tree and tracking of specific elements is required.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.