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

Find the Last Marked Nodes in Tree

Number: 3497

Difficulty: Hard

Paid? Yes

Companies: Salesforce

Problem Description

Given an undirected tree with n nodes (numbered 0 to n - 1) and an edge list, we simulate a marking process. Initially, all nodes are unmarked. For a given starting node that is marked at time t = 0, every second the process marks all unmarked nodes with at least one marked neighbor. For each possible starting node, return the node that is marked last (if there are several candidates, any one is accepted).

Key Insights

  • The marking process proceeds in “waves”, similar to a breadth-first search (BFS) level traversal.
  • In a tree, the last marked node when starting from a source is simply one of the nodes at maximum distance from the source.
  • A core observation is that, in a tree, for every vertex, the farthest node from it must be one of the endpoints of the tree's diameter.
  • Thus, by computing the two farthest nodes (endpoints of the tree's diameter), we can determine for each starting node which endpoint is farther and therefore will be the last marked.

Space and Time Complexity

Time Complexity: O(n), since we perform a constant number of BFS traversals. Space Complexity: O(n), for storing the tree as an adjacency list and the distance arrays.

Solution

We first compute one endpoint of the diameter by running a BFS from an arbitrary node. Then, from that node, we perform a BFS to find the farthest node, which gives us the other endpoint of the diameter. Next, we run two BFS traversals starting from each endpoint (u and v) to compute the distances of every node from u and v respectively. Finally, for each starting node s, we choose the endpoint (u or v) which is farther from s; this endpoint is the last node to be marked during the marking process. This approach leverages the property that the furthest node from any source in a tree lies on its diameter, making the solution efficient even for large trees.

Code Solutions

# Python solution with detailed comments
from collections import deque
from typing import List

def lastMarkedNodes(n: int, edges: List[List[int]]) -> List[int]:
    # Build adjacency list for the tree
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
        
    # Helper function to perform BFS and return distances from the starting node
    def bfs(start: int) -> List[int]:
        dist = [-1] * n
        q = deque([start])
        dist[start] = 0
        while q:
            node = q.popleft()
            for neighbor in adj[node]:
                if dist[neighbor] == -1:
                    dist[neighbor] = dist[node] + 1
                    q.append(neighbor)
        return dist

    # First, find one endpoint of the tree diameter
    initial_dist = bfs(0)
    u = initial_dist.index(max(initial_dist))
    
    # Next, perform BFS from u to get distances and find the other endpoint v
    dist_from_u = bfs(u)
    v = dist_from_u.index(max(dist_from_u))
    
    # Perform BFS from v to get distances from v
    dist_from_v = bfs(v)
    
    # For each node as a starting point, choose the endpoint that is further away 
    result = [u if dist_from_u[s] >= dist_from_v[s] else v for s in range(n)]
    return result

# Example Usage:
# edges = [[0,1],[0,2]]
# print(lastMarkedNodes(3, edges))  # Possible output: [2,2,1]
← Back to All Questions