Leetcode 1831 Solution

This article provides solution to leetcode question 1831 (ways-to-split-array-into-three-subarrays)
Categories:
Tags:
Access this page by simply typing in "lcs 1831" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/ways-to-split-array-into-three-subarrays

Solution

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        sums = []
        s = 0
        for num in nums:
            s += num
            sums.append(s)

        ans = 0
        for i in range(2, len(nums)):
            max_bound = sums[-1] - sums[i - 1]
            l, r = 1, i - 1
            while l < r:
                m = (l + r) // 2
                if sums[i - 1] - sums[m] + nums[m] <= max_bound:
                    r = m
                else:
                    l = m + 1
            if sums[i - 1] - sums[l] + nums[l] > max_bound:
                continue
            left = l

            l, r = 1, i - 1
            while l < r:
                m = (l + r + 1) // 2
                if sums[i - 1] - sums[m - 1] < sums[m - 1]:
                    r = m - 1
                else:
                    l = m
            if sums[i - 1] - sums[l - 1] < sums[l - 1]:
                continue
            right = l

            ans += max(0, right - left + 1)

        return ans % 1000000007