Problem Statement:
Given an undirected tree consisting of n vertices numbered from 0 to n-1, which has some apples in their vertices. You spend 1 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 ai and bi. 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 figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
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 figure above represents the given tree where red vertices have an apple. One optimal path to collect all apples is shown by the green arrows.
Example 3:
Input: n = 7, edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]], hasApple = [false,false,false,false,false,false,false]
Output: 0
Constraints:
- 1 <= n <= 105
- edges.length == n - 1
- edges[i].length == 2
- 0 <= ai < bi <= n - 1
- fromi < toi
- hasApple.length == n
Solution:
Algorithm:
- Create an array parent of size n and initialize it with -1.
- Traverse the edges array and update the parent array.
- Create a variable res and initialize it with 0.
- Traverse the array from n-1 to 1.
- If the ith index of hasApple is true, then update the res by 2 and update the parent[i]th index of hasApple to true.
Code:
public class Solution {
public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
int[] parent = new int[n];
Arrays.fill(parent, -1);
for (int[] edge : edges) {
parent[edge[1]] = edge[0];
}
int res = 0;
for (int i = n - 1; i > 0; i--) {
if (hasApple.get(i)) {
res += 2;
hasApple.set(parent[i], true);
}
}
return res;
}
}
Time Complexity:
O(n)
Space Complexity:
O(n)
Top comments (0)