Is Find the Last Marked Nodes in Tree easy or hard?

Find the Last Marked Nodes in Tree is classified as a Hard problem because it requires recognizing a non-obvious tree property. A naive approach is easy to implement but inefficient. The optimized solution requires understanding tree diameter and distance propagation using DFS.

Find the Last Marked Nodes in Tree Python/Java solution

Implement the solution by building the tree with adjacency lists, running DFS to find the diameter endpoints among marked nodes, and computing distances from both endpoints. The same logic works across Python, Java, C++, Go, TypeScript, and JavaScript because the algorithm only relies on DFS and array distance tracking.

How to solve Find the Last Marked Nodes in Tree in O(n)?

First build the adjacency list for the tree. Run DFS from any marked node to find the farthest marked node A. Run another DFS from A to find the opposite marked endpoint B of the diameter. Compute distances from both A and B, and for each node choose whichever endpoint is farther. This completes in linear time.

What is the best approach for Find the Last Marked Nodes in Tree?

The most efficient approach is computing the diameter formed by the marked nodes and then running DFS from the two diameter endpoints. For each node, compare distances to both endpoints and select the farther marked node. This works because the farthest node in a tree must lie on the diameter. The method runs in O(n) time and O(n) space.

Is Find the Last Marked Nodes in Tree asked at Google/Amazon/Meta?

Problems involving tree diameter, farthest node queries, and DFS distance propagation frequently appear in interviews at companies like Google, Amazon, and Meta. Variations of this problem test understanding of tree properties and efficient graph traversal techniques.

What data structure is used in Find the Last Marked Nodes in Tree?

The problem uses an adjacency list to represent the tree along with Depth-First Search for traversal. Arrays or vectors store distances from candidate nodes. The algorithm relies on tree properties and graph traversal rather than complex data structures.

What is the time complexity of Find the Last Marked Nodes in Tree?

The optimal solution runs in O(n) time where n is the number of nodes in the tree. It performs a few DFS traversals to find the marked-node diameter and compute distances. Space complexity is O(n) due to the adjacency list and recursion or stack used in DFS.

Description Hints 4 Solution Video 5:42

3313. Find the Last Marked Nodes in Tree

Hard57.1% acceptance1 companyPremium elsewhere, free here

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. After every second, you mark all unmarked nodes which have at least one marked node adjacent to them.

Return an array nodes where nodes[i] is the last node to get marked in the tree, if you mark node i at time t = 0. If nodes[i] has multiple answers for any node i, you can choose any one answer.

Example 1:

Input: edges = [[0,1],[0,2]]

Output: [2,2,1]

Explanation:

For i = 0, the nodes are marked in the sequence: [0] -> [0,1,2]. Either 1 or 2 can be the answer.
For i = 1, the nodes are marked in the sequence: [1] -> [0,1] -> [0,1,2]. Node 2 is marked last.
For i = 2, the nodes are marked in the sequence: [2] -> [0,2] -> [0,1,2]. Node 1 is marked last.

Example 2:

Input: edges = [[0,1]]

Output: [1,0]

Explanation:

For i = 0, the nodes are marked in the sequence: [0] -> [0,1].
For i = 1, the nodes are marked in the sequence: [1] -> [0,1].

Example 3:

Input: edges = [[0,1],[0,2],[2,3],[2,4]]

Output: [3,3,1,1,1]

Explanation:

For i = 0, the nodes are marked in the sequence: [0] -> [0,1,2] -> [0,1,2,3,4].
For i = 1, the nodes are marked in the sequence: [1] -> [0,1] -> [0,1,2] -> [0,1,2,3,4].
For i = 2, the nodes are marked in the sequence: [2] -> [0,2,3,4] -> [0,1,2,3,4].
For i = 3, the nodes are marked in the sequence: [3] -> [2,3] -> [0,2,3,4] -> [0,1,2,3,4].
For i = 4, the nodes are marked in the sequence: [4] -> [2,4] -> [0,2,3,4] -> [0,1,2,3,4].

Constraints:

2 <= n <= 10⁵
edges.length == n - 1
edges[i].length == 2
0 <= edges[i][0], edges[i][1] <= n - 1
The input is generated such that edges represents a valid tree.

Asked at 1 company

Salesforce

Topics

Depth-First Search Tree

Hints open one at a time

Hint 1

We need to calculate the height of tree when rooted at each node.

Hint 2

Find a diameter using two DFS.

Hint 3

The farthest node from each node must be one of the endpoints of the diameter.

Hint 4

The last marked node will be one of the end of the diameter, whichever is more distant.

5:42

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

3313. Find the Last Marked Nodes in Tree

Asked at 1 company

Topics

Hints open one at a time

Similar problems