Reverse The Magic

A few observations were required to solve this problem.

• The subtree under any node appears as a subarray in the array representation
• If there is a pair of integers (u,v) where u = 0, then v = n-1. Since u = 0 represents the root, it covers the whole array.
• Let y be a node in the subarray of node x. Let (ux,vx) represent the subtree of x and (uy,vy) represent the subtree of y in the array. Then ux ≥ vx and vx ≤ vy.
• Let (ux,vx) and (uy,vy) be two pairs of integers. If ux = uy, then vx = vy must be the true. The subarray that represents the subtree of a node has a unique starting position. So there cannot be multiple ranges starting from the same position.

If these conditions hold, a tree can always be built conforming to the given ranges. We can check if these conditions hold using stacks in O(N) time.

Judge solution: Link
Complexity: O(N)
Alternate: Tarango Khan