Leetcode 951 Solution

This article provides solution to leetcode question 951 (partition-array-into-disjoint-intervals)
Categories:
Tags:
Access this page by simply typing in "lcs 951" in your browser address bar if you have bunnylol configured.

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

Solution

class Solution:
    def partitionDisjoint(self, A: List[int]) -> int:
        dp1 = [0] * len(A)
        dp2 = [0] * len(A)



        dp1[0] = A[0]
        for i in range(1, len(A)):
            dp1[i] = max(dp1[i - 1], A[i])



        dp2[-1] = A[-1]
        for i in range(len(A) - 2, -1, -1):
            dp2[i] = min(dp2[i + 1], A[i])



        for i in range(0, len(A) - 1):
            if dp1[i] <= dp2[i + 1]:
                return i + 1