We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Time to Collect All Apples in a Tree

Number: 1554

Difficulty: Medium

Paid? No

Companies: Meta, Microsoft, Myntra, Amazon

Problem Description

We are given an undirected tree with n vertices numbered from 0 to n-1. Some vertices contain apples, as indicated by the boolean array hasApple. Starting at vertex 0, the goal is to collect all the apples in the tree and return to vertex 0 while minimizing the total time. Moving across an edge takes 1 second.

Key Insights

  • Use Depth-First Search (DFS) to traverse the tree from the root.
  • Only traverse branches (subtrees) which either contain an apple or lead to an apple.
  • Each necessary edge is counted twice (once forward and once backward), except when it is not needed.
  • Construct an adjacency list from the edges to efficiently represent the tree.

Space and Time Complexity

Time Complexity: O(n) — Each vertex is processed once. Space Complexity: O(n) — For storing the tree and the recursion stack in DFS.

Solution

We use a DFS approach starting from node 0. First, we build the tree using an adjacency list. During the DFS traversal, for each child node, we recursively determine the time required to collect apples in its subtree. If the subtree rooted at a child node contains an apple (or the child itself has an apple), we add the cost to travel to that child and come back (2 seconds). The DFS function returns the total time required from that node. This approach ensures that only necessary paths are explored and included in the final time calculation.

Code Solutions

def minTime(n, edges, hasApple):
    from collections import defaultdict
    # Build the tree as an adjacency list
    tree = defaultdict(list)
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    
    def dfs(node, parent):
        total_time = 0
        # Explore children excluding the parent to avoid cycles
        for child in tree[node]:
            if child == parent:
                continue
            child_time = dfs(child, node)
            # Add cost if the child's subtree contains an apple or the child itself has an apple
            if child_time > 0 or hasApple[child]:
                total_time += child_time + 2  # 2 seconds for the round-trip edge
        return total_time
    
    return dfs(0, -1)

# Example usage:
n = 7
edges = [[0,1],[0,2],[1,4],[1,5],[2,3],[2,6]]
hasApple = [False, False, True, False, True, True, False]
print(minTime(n, edges, hasApple))  # Expected output: 8
← Back to All Questions