FastPrep
Problem · Tree

Chain of Command

Learn this problem
● MediumIMCOA

Problem statement

An organization contains n people. Its structure is a tree in which each person is a node. Every node except the root has one parent, representing its upstream reporting line, and a node may have any number of children, representing the people who report to it.

Person 1 is the root. The array parent represents the tree: parent[i] is the parent of person i + 1, and parent[0] = -1 indicates that the root has no parent.

Directive propagation

A person may issue a directive to their reporting subtree. The issuing person receives it first, and the directive then propagates as follows:

  • A person sends the directive to their direct children in ascending order of person index.
  • Before sending it to the next child, the person waits until propagation through the current child's entire subtree is complete.
  • Every child propagates the directive through its subtree using the same process.
  • Propagation stops when every node in the issuing person's subtree has received the directive.

Queries

Each query is [startNode, k]. Determine the kth person to receive the directive when startNode issues it.

If k is greater than the number of people in that reporting subtree, return -1. Evaluate every query independently.

Function

chainOfCommand(parent: int[], queries: int[][]) → int[]

Examples

Example 1

parent = [-1, 1, 1, 1, 3, 5, 3, 5, 7]queries = [[1, 5], [7, 2], [9, 2], [3, 6]]return = [6, 9, -1, 9]

The array parent represents these direct reporting relationships:

  • Person 1 manages people 2, 3, and 4.
  • Person 3 manages people 5 and 7.
  • Person 5 manages people 6 and 8.
  • Person 7 manages person 9.

The receive order is [1, 2, 3, 5, 6, 8, 7, 9, 4] from person 1, [3, 5, 6, 8, 7, 9] from person 3, [7, 9] from person 7, and [9] from person 9.

Processing the queries:

  1. queries[0] = [1, 5]: the 5th person is 6.
  2. queries[1] = [7, 2]: the 2nd person is 9.
  3. queries[2] = [9, 2]: no 2nd person exists, so the answer is -1.
  4. queries[3] = [3, 6]: the 6th person is 9.

Therefore, the returned array is [6, 9, -1, 9].

Example 2

parent = [-1, 1, 1, 2, 2]queries = [[1, 3], [2, 3]]return = [4, 5]

The array parent represents these direct reporting relationships:

  • Person 1 manages people 2 and 3.
  • Person 2 manages people 4 and 5.

The receive order is [1, 2, 4, 5, 3] from person 1 and [2, 4, 5] from person 2.

For queries[0] = [1, 3], the 3rd person is 4. For queries[1] = [2, 3], the 3rd person is 5.

Therefore, the returned array is [4, 5].

Constraints

  • 2 <= n <= 10^5
  • 1 <= parent[i] <= n for all nodes except the root node, where parent[0] = -1.
  • 1 <= q <= 2 * 10^5
  • 1 <= queries[i][0] <= n
  • 1 <= queries[i][1] <= n

More IMC problems

drafts saved locally
public int[] chainOfCommand(int[] parent, int[][] queries) {
  // write your code here
}
parent[-1, 1, 1, 1, 3, 5, 3, 5, 7]
queries[[1, 5], [7, 2], [9, 2], [3, 6]]
expected[6, 9, -1, 9]
checking account