FastPrepMaximum Sum of a k-Node Downward Path

Maximum Sum of a k-Node Downward Path

Hudson River Trading logoHudson River Trading● MediumFULLTIMEOA

Problem statement

You are given a rooted tree with n nodes, numbered from 0 to n - 1. A node can have any number of children.

The tree is described by two arrays of length n:

  • parents[i] is the parent of node i. The root is the only node with parents[i] == -1. The root does not have to be node 0.
  • values[i] is the value of node i.

A downward path with k nodes is a list of exactly k nodes where each node after the first is a child of the node before it. The path can start at any node and stop at any node. It does not have to start at the root or end at a leaf. A single node is a downward path with 1 node.

Return the largest sum of values over all downward paths with exactly k nodes. If the tree has no downward path with k nodes, return -1.

Function

maxDownwardPathSum(parents: int[], values: int[], k: int) → int

Examples

Example 1

parents = [-1,0,0,1,1,2]values = [3,1,5,4,2,6]k = 3return = 14

Node 0 is the root, with children 1 and 2. Node 1 has children 3 and 4, and node 2 has child 5.

The downward paths with 3 nodes are:

  • 0 → 1 → 3, with sum 3 + 1 + 4 = 8
  • 0 → 1 → 4, with sum 3 + 1 + 2 = 6
  • 0 → 2 → 5, with sum 3 + 5 + 6 = 14

The largest sum is 14.

Example 2

parents = [2,2,-1,0,0]values = [5,2,1,7,1]k = 2return = 12

Node 2 is the root, with children 0 and 1. Node 0 has children 3 and 4.

The downward paths with 2 nodes are 2 → 0 (sum 6), 2 → 1 (sum 3), 0 → 3 (sum 12) and 0 → 4 (sum 6).

The best path, 0 → 3, does not start at the root. The answer is 12.

Example 3

parents = [-1,0,0]values = [4,6,2]k = 3return = -1

Node 0 has two children, and neither child has a child of its own, so the longest downward path has 2 nodes.

Going from node 1 up to node 0 and then down to node 2 is not a downward path. No path has 3 nodes, so the answer is -1.

Constraints

  • n == parents.length == values.length
  • 1 <= n <= 10^4
  • 0 <= values[i] <= 10^4
  • 1 <= k <= n
  • Exactly one node has parents[i] == -1. Every other parents[i] is a node index from 0 to n - 1.
  • The parent links form one tree: following parents from any node always reaches the root.

More Hudson River Trading problems

See Hudson River Trading hiring insights
Saved
public int maxDownwardPathSum(int[] parents, int[] values, int k) {
    // Write your code here.
}
Checking account…