Max Minus Min Weight in Every Subtree
Updated
Problem statement
You are given a tree with n nodes numbered from 0 to n - 1. Node 0 is the root. The array parent describes the tree: parent[0] is -1, and for every other node i, parent[i] is the node directly above i. A parent can have a larger number than its child.
Each node has a weight. The weight of node i is weights[i], and weights can be negative.
The subtree of a node v is v itself together with every node below it: its children, their children, and so on.
For every node v, find the largest weight and the smallest weight in the subtree of v, and subtract the smallest from the largest. Return an array answer of length n, where answer[v] is this value for node v. A leaf's subtree holds only the leaf, so its answer is 0.
The tree can be a single chain of 10^4 nodes, so a recursive solution must be able to go that deep.
Function
subtreeWeightRange(parent: int[], weights: int[]) → int[]Examples
Example 1
parent = [-1,0,0,1,1,2,2]weights = [5,3,8,-2,4,6,10]return = [12,6,4,0,0,0,0]Node 1 has children 3 and 4, so its subtree is nodes 1, 3 and 4, with weights 3, -2 and 4. The answer for node 1 is 4 - (-2) = 6.
The subtree of node 2 is nodes 2, 5 and 6, with weights 8, 6 and 10. Its answer is 10 - 6 = 4.
The subtree of node 0 is the whole tree. The largest weight is 10 (node 6) and the smallest is -2 (node 3), so its answer is 12.
Nodes 3, 4, 5 and 6 are leaves. Each subtree holds one node, so each answer is 0.
Example 2
parent = [-1,0,0]weights = [0,1000000000,-1000000000]return = [2000000000,0,0]The root's subtree holds all three nodes. Its largest weight is 1000000000 and its smallest is -1000000000, so its answer is 2000000000. This is the largest answer the limits allow, and it still fits in a 32-bit signed integer.
Nodes 1 and 2 are leaves, so their answers are 0.
Example 3
parent = [-1,2,0,1,2,0]weights = [4,9,1,7,2,4]return = [8,2,8,0,0,0]Here a parent can have a larger number than its child: parent[1] = 2. Node 0 has children 2 and 5, node 2 has children 1 and 4, and node 1 has child 3.
The subtree of node 1 is nodes 1 and 3, with weights 9 and 7, so its answer is 2.
The subtree of node 2 is nodes 2, 1, 3 and 4, with weights 1, 9, 7 and 2. Its answer is 9 - 1 = 8.
The subtree of node 0 is the whole tree. Its largest weight is 9 and its smallest is 1, so its answer is also 8. Nodes 3, 4 and 5 are leaves, so their answers are 0.
Constraints
n == parent.length == weights.length1 <= n <= 10^4parent[0] == -10 <= parent[i] <= n - 1for everyifrom1ton - 1- Following
parentlinks from any node always reaches node0, soparentdescribes one tree rooted at node0. -10^9 <= weights[i] <= 10^9
More Hudson River Trading Online Assessment questions
- Count Palindrome Addition ChoicesOA · Seen Nov 2026
- Count Multiples of Three with Two SevensOA · Seen Oct 2026
- Recursively Expanded Shell Command CountsOA · Seen Oct 2026
- Rotate Matrix Regions Around the DiagonalsOA · Seen Oct 2026
- Maximum Diamond SumOA · Seen Oct 2026
- Smallest Most-Lit Street PositionOA · Seen Oct 2026
- Rearrange String by Alternating EndsOA · Seen Sep 2026
- Most Items Within Budget from a Start IndexOA · Seen Sep 2026
- Count Sawtooth SubarraysOA · Seen Aug 2026
- Backtick Identifier ConverterOA · Seen Jun 2026
Similar questions at other companies
- Maximum Data Transfer TimeMicrosoft · OAMicrosoft interview questions
- Special Diameter EndpointsAgoda · OAAgoda interview questions
- Longest Transfer Time in a Server TreeRippling · OARippling interview questions
- Binary Tree Level OrderMorgan Stanley · OAMorgan Stanley interview questions
- Symmetric Binary TreeDocuSign · PHONE SCREENDocuSign interview questions
- Maximum Depth of Binary TreeLinkedIn · PHONE SCREEN · ONSITE INTERVIEWLinkedIn interview questions
- Symmetric Binary TreeFigma · ONSITE INTERVIEWFigma interview questions
- Tree Level with the Most NodesBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Left View of a Binary TreeMygate · PHONE SCREENMygate interview questions
- Mirror a Binary TreeAdobe · PHONE SCREENAdobe interview questions