1443. Minimum Time to Collect All Apples in a Tree LeetCode Solution

In this guide, you will get 1443. Minimum Time to Collect All Apples in a Tree LeetCode Solution with the best time and space complexity. The solution to Minimum Time to Collect All Apples in a Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Time to Collect All Apples in a Tree solution in C++
Minimum Time to Collect All Apples in a Tree solution in Java
Minimum Time to Collect All Apples in a Tree solution in Python
Additional Resources

1443. Minimum Time to Collect All Apples in a Tree LeetCode Solution image

Problem Statement of Minimum Time to Collect All Apples in a Tree

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
hasApple.length == n

Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(n)

1443. Minimum Time to Collect All Apples in a Tree LeetCode Solution in C++

class Solution {
 public:
  int minTime(int n, vector<vector<int>>& edges, vector<bool>& hasApple) {
    vector<vector<int>> graph(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      graph[u].push_back(v);
      graph[v].push_back(u);
    }

    return dfs(graph, 0, vector<bool>(n), hasApple);
  }

 private:
  int dfs(const vector<vector<int>>& graph, int u, vector<bool>&& seen,
          const vector<bool>& hasApple) {
    seen[u] = true;
    int totalCost = 0;

    for (const int v : graph[u]) {
      if (seen[v])
        continue;
      const int cost = dfs(graph, v, std::move(seen), hasApple);
      if (cost > 0 || hasApple[v])
        totalCost += cost + 2;
    }

    return totalCost;
  }
};
/* code provided by PROGIEZ */

1443. Minimum Time to Collect All Apples in a Tree LeetCode Solution in Java

class Solution {
  public int minTime(int n, int[][] edges, List<Boolean> hasApple) {
    List<Integer>[] graph = new List[n];

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      graph[u].add(v);
      graph[v].add(u);
    }

    return dfs(graph, 0, new boolean[n], hasApple);
  }

  private int dfs(List<Integer>[] graph, int u, boolean[] seen, List<Boolean> hasApple) {
    seen[u] = true;
    int totalCost = 0;

    for (final int v : graph[u]) {
      if (seen[v])
        continue;
      final int cost = dfs(graph, v, seen, hasApple);
      if (cost > 0 || hasApple.get(v))
        totalCost += cost + 2;
    }

    return totalCost;
  }
}
// code provided by PROGIEZ