1443. Minimum Time to Collect All Apples in a Tree - Explanation

Problem Link

Description

You are given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend one second to walk over one edge of the tree. Return the minimum time in seconds you have to spend to collect all apples in the tree, starting at vertex 0 and coming back to this vertex.

The edges of the undirected tree are given in the array edges, where edges[i] = [ai, bi] means that exists an edge connecting the vertices a[i] and b[i]. Additionally, there is a boolean array hasApple, where hasApple[i] = true means that vertex i has an apple; otherwise, it does not have any apple.

Example 1:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,true,true,false]

Output: 8

Explanation: The path that takes minimum time to collect all apples is: 0 -> 1 -> 4 -> 1 -> 5 -> 1 -> 0 -> 2 -> 0.

Example 2:

Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,true,false,false,true,false]

Output: 6

Explanation: The path that takes minimum time to collect all apples is: 0 -> 2 -> 0 -> 1 -> 5 -> 1 -> 0.

Constraints:

• 1 <= n <= 100,000
• edges.length == n - 1
• edges[i].length == 2
• 0 <= a[i] < b[i] <= n - 1
• hasApple.length == n

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Depth First Search

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        adj = {i: [] for i in range(n)}
        for par, child in edges:
            adj[par].append(child)
            adj[child].append(par)

        def dfs(cur, par):
            time = 0
            for child in adj[cur]:
                if child == par:
                    continue
                childTime = dfs(child, cur)
                if childTime > 0 or hasApple[child]:
                    time += 2 + childTime
            return time

        return dfs(0, -1)

Time & Space Complexity

• Time complexity: $O(V + E)$
• Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges.

---

2. Topological Sort (Kahn's Algorithm)

class Solution:
    def minTime(self, n: int, edges: List[List[int]], hasApple: List[bool]) -> int:
        adj = defaultdict(list)
        indegree = [0] * n
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
            indegree[u] += 1
            indegree[v] += 1

        queue = deque()
        for i in range(1, n):
            if indegree[i] == 1:
                queue.append(i)
                indegree[i] = 0

        time = [0] * n
        while queue:
            node = queue.popleft()
            for nei in adj[node]:
                if indegree[nei] <= 0:
                    continue

                indegree[nei] -= 1
                if hasApple[node] or time[node] > 0:
                    time[nei] += time[node] + 2
                if indegree[nei] == 1 and nei != 0:
                    queue.append(nei)

        return time[0]

Time & Space Complexity

• Time complexity: $O(V + E)$
• Space complexity: $O(V + E)$

Where $V$ is the number of vertices and $E$ is the number of edges.