Marc Lester Tan

We can solve this medium LC problem by recursively finding the index of the highest value (let’s call it as maxIndex) then splitting the array into two subarrays starting from 0 to maxIndex - 1 and maxIndex + 1 to array’s size - 1.

We construct the tree everytime we encounter the max value.

/**
 * Example:
 * var ti = TreeNode(5)
 * var v = ti.`val`
 * Definition for a binary tree node.
 * class TreeNode(var `val`: Int) {
 *     var left: TreeNode? = null
 *     var right: TreeNode? = null
 * }
 */
class Solution {
    val indexOfMax: (IntArray) -> Int = { array ->
            var indexOfMax = -1
            var max = Integer.MIN_VALUE
            array.forEachIndexed { index, i ->
                if(i > max) {
                    indexOfMax = index 
                    max = i
                }
            }
            
            indexOfMax
        }
    
    fun constructMaximumBinaryTree(nums: IntArray): TreeNode? {
        fun constructMaximumBinaryTree_(nums: IntArray, start: Int, end: Int): TreeNode? {
            if(start > end) return null
            
            val newArray = nums.sliceArray(start..end)
            val max = indexOfMax(newArray)
            var node = TreeNode(newArray[max])
            node.left = constructMaximumBinaryTree_(newArray, 0, max-1)
            node.right = constructMaximumBinaryTree_(newArray, max + 1, newArray.size-1)
            return node
        }
        
        return constructMaximumBinaryTree_(nums, 0, nums.size-1)       
    }
}

Runtime: 248 ms, faster than 57.14% of Kotlin online submissions for Maximum Binary Tree.
Memory Usage: 38.7 MB, less than 100.00% of Kotlin online submissions for Maximum Binary Tree.