[LeetCode] 915. Partition Array into Disjoint Intervals

 Problem : https://leetcode.com/problems/partition-array-into-disjoint-intervals/

The requirement of all numbers in left sub-array are less than or equal to numbers in right sub-array can be interpreted as the maximum number in left sub-array is less than or equal to the minimum number in right sub-array.

class Solution:
    def partitionDisjoint(self, nums: List[int]) -> int:
        N = len(nums)
        
        # maximum number from left of nums[i] ( includes nums[i] )
        maxFromLeft = [0] * N
        maxFromLeft[0] = nums[0]
        
        for i in range(1, N):
            maxFromLeft[i] = max(maxFromLeft[i-1], nums[i])
        
        # minimum number from right of nums[i]
        minFromRight = nums[N-1]
        result = N-1
        
        for i in reversed(range(1, N)):
            minFromRight = min(minFromRight, nums[i])
            
            if minFromRight >= maxFromLeft[i-1]:
                result = i
        
        return result