FastPrep
Problem · Array

Reconstruct the Root Stream

Learn this problem
● MediumArcesium logoArcesiumFULLTIMEOA

Problem statement

A perfect binary tree distributes a root data stream to its leaves. The internal nodes appear in level order in distributionNodes:

  • Type 0 is a splitting node. It sends the first half to its left child and the remaining half to its right child. For an odd-sized stream, the left child receives one more item.
  • Type 1 is a parallelizing node. It sends items at positions 0, 2, 4, ... to its left child and items at positions 1, 3, 5, ... to its right child.

streamAtLeaves lists the streams received by the leaves from left to right. Rows may be padded with -1; ignore those padding values.

Reconstruct and return the original stream at the root.

Function

reconstructRootStream(distributionNodes: int[], streamAtLeaves: int[][]) → int[]

Examples

Example 1

distributionNodes = [0,1,1]streamAtLeaves = [[1,3],[2,4],[5,7],[6,8]]return = [1,2,3,4,5,6,7,8]

Each type-1 child pair reconstructs to [1,2,3,4] and [5,6,7,8]. The type-0 root concatenates those halves.

Example 2

distributionNodes = [1,0,0]streamAtLeaves = [[10],[20],[30],[40]]return = [10,30,20,40]

The type-0 nodes reconstruct [10,20] and [30,40]. Alternating those at the type-1 root gives [10,30,20,40].

Constraints

  • 1 <= distributionNodes.length <= 10^4.
  • Every entry of distributionNodes is 0 or 1.
  • The number of leaf rows equals distributionNodes.length + 1.
  • The total number of non-padding values is at most 10^6.
  • Every stream value is positive; -1 is reserved for padding.

More Arcesium problems

drafts saved locally
public int[] reconstructRootStream(int[] distributionNodes, int[][] streamAtLeaves) {
  // Write your code here.
}
distributionNodes[0,1,1]
streamAtLeaves[[1,3],[2,4],[5,7],[6,8]]
expected[1,2,3,4,5,6,7,8]
checking account