FastPrepSpecial Diameter Endpoints

Special Diameter Endpoints

Agoda logoAgoda● HardFULLTIMEOA
Learn

Problem statement

Given a tree with tree_nodes nodes numbered from 1 to tree_nodes, call a node special if it is an endpoint of at least one diameter of the tree.

The diameter of a tree is the number of edges in a longest path. Return a binary array with one value per node: 1 if the node is special, otherwise 0.

  2
 / \
1   3

Example tree: the diameter is the path 1 – 2 – 3.

Function

isSpecial(tree_nodes: int, tree_from: int[], tree_to: int[]) → int[]

Examples

Example 1

tree_nodes = 3tree_from = [2,2]tree_to = [1,3]return = [1,0,1]

The tree contains edges 2-1 and 2-3. Its unique diameter is the path from node 1 through node 2 to node 3, so nodes 1 and 3 are special and node 2 is not.

Example 2

tree_nodes = 7tree_from = [1,2,3,3,1,1]tree_to = [2,3,4,5,6,7]return = [0,0,0,1,1,1,1]

The four diameter paths connect one of nodes 6 and 7 to one of nodes 4 and 5. Exactly nodes 4, 5, 6, and 7 are diameter endpoints.

Constraints

  • 1 ≤ tree_nodes ≤ 10^5
  • 1 ≤ tree_from[i], tree_to[i] ≤ tree_nodes

More Agoda problems

See Agoda hiring insights
public int[] isSpecial(int tree_nodes, int[] tree_from, int[] tree_to) {
  // Write your code here.
}
tree_nodes3
tree_from[2,2]
tree_to[1,3]
expected[1,0,1]
Checking account…