Maximum Binary Tree (Leetcode) - Optimal Solution Explanation?

user_14427790 0
Viewed 254

I was going through the Maximum Binary Tree leetcode problem. The TL;DR is that you have an array, such as this one:

[3,2,1,6,0,5]

You're supposed to take the maximum element and make that the root of your tree. Then split the array into the part to the left of that element and the part to its right, and these are used to recursively create the left and right subtrees in the same way, respectively.

LeetCode claims that the optimal solution (shown in the "Solution" tab) uses a linear search for the maximum value of the sub-array in each recursive step. This is O(n^2) in the worst case. This is the solution I came up with, and it's simple enough.

However, I was looking through other submissions and found a linear time solution, but I've struggled to understand how it works! It looks something like this:

def constructMaximumBinaryTree(nums):
    nodes=[]
    for num in nums:
        node = TreeNode(num)
        while nodes and num>nodes[-1].val:
            node.left = nodes.pop()
        if nodes:
            nodes[-1].right = node
        nodes.append(node)
        
    return nodes[0]

I've analysed this function and in aggregate, this appears to be linear time (O(n)), since each unique node is added to and popped from the nodes array at most once. I've tried running it with different example inputs, but I'm struggling to connect the dots and wrap my head around how this works. Can someone please explain it to me?

time-complexity algorithm python
1 Answers

One way to understand the algorithm is to consider the loop invariants. In this case, the array of nodes always satisfies the condition that before and after each execution of the for-loop, either:

  1. nodes is empty and a max binary tree does not exist (for example, if the input nums was empty)
  2. the first item in nodes is the max binary tree based on the data processed so far from the input nums

The while-loop ensures that the current max binary tree is the first item in the nodes array, since otherwise, it would have been popped and added as a left subtree.

During each iteration of the for-loop, the check:

if nodes:
    nodes[-1].right = node

adds the current node as a right subtree to the last item in the nodes array. And when this happens, the current node is less than the last node in the nodes array (since each input integer is defined to be unique). And since the current node is less than the last node in the array, the last node acts as a partition point whose value is greater than the current item, which is why the current node is added as a right subtree.

When there are multiple items in the nodes array, each item is a subtree of the item to its left.

Running Time

For the running time, let n be the length of the input nums. There are n executions of the for-loop. If the input data were sorted in descending order, but with the max input value at the end of the input (such as: 4, 3, 2, 1, 5), then the inner while-loop would be skipped during each iteration until the last for-loop iteration. During the last for-loop iteration, the while loop would run n - 1 times, for a total running time of n + (n - 1) => 2n - 1 => O(n).

user_11644650
Related