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.