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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Time Taken to Mark All Nodes

Difficulty: Hard

Problem Description

There exists an undirected tree with n nodes numbered 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [u_i, v_i] indicates that there is an edge between nodes u_i and v_i in the tree. Initially, all nodes are unmarked. For each node i:

  • If i is odd, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 1.
  • If i is even, the node will get marked at time x if there is at least one node adjacent to it which was marked at time x - 2.

Return an array times where times[i] is the time when all nodes get marked in the tree, if you mark node i at time t = 0.

Key Insights

  • Nodes are marked based on their parity (odd or even) and their adjacency to already marked nodes.
  • Odd-indexed nodes depend on the previous time step for marking, while even-indexed nodes depend on two time steps back.
  • This creates a layered marking process that can be modeled using BFS or DFS strategies to simulate the marking over time.

Space and Time Complexity

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

Solution

To solve the problem, we will use Depth-First Search (DFS) to traverse the tree. We will maintain a queue to simulate the marking process based on the parity of the node being processed. Each node will be marked at the appropriate time based on the marking of its neighbors. The results will be stored in an array which we will return at the end.

Code Solutions

from collections import defaultdict, deque

def time_to_mark_all_nodes(edges):
    n = len(edges) + 1
    graph = defaultdict(list)

    # Build the adjacency list for the tree
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)

    # Result array to store mark times for each node
    result = [0] * n

    # Function to perform BFS and calculate time to mark all nodes
    def bfs(start):
        queue = deque([start])
        visited = [False] * n
        visited[start] = True
        time = 0
        while queue:
            # Process all nodes at the current time step
            for _ in range(len(queue)):
                node = queue.popleft()
                result[node] = time
                for neighbor in graph[node]:
                    if not visited[neighbor]:
                        visited[neighbor] = True
                        queue.append(neighbor)
            time += 1

    # Run BFS for all nodes to compute the marking time
    for i in range(n):
        bfs(i)

    return result
← Back to All Questions