<p>A split of an integer array is <strong>good</strong> if:</p>

<ul>
	<li>The array is split into three <strong>non-empty</strong> contiguous subarrays - named <code>left</code>, <code>mid</code>, <code>right</code> respectively from left to right.</li>
	<li>The sum of the elements in <code>left</code> is less than or equal to the sum of the elements in <code>mid</code>, and the sum of the elements in <code>mid</code> is less than or equal to the sum of the elements in <code>right</code>.</li>
</ul>

<p>Given <code>nums</code>, an array of <strong>non-negative</strong> integers, return <em>the number of <strong>good</strong> ways to split</em> <code>nums</code>. As the number may be too large, return it <strong>modulo</strong> <code>10<sup>9 </sup>+ 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,1,1]
<strong>Output:</strong> 1
<strong>Explanation:</strong> The only good way to split nums is [1] [1] [1].</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,2,2,2,5,0]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three good ways of splitting nums:
[1] [2] [2,2,5,0]
[1] [2,2] [2,5,0]
[1,2] [2,2] [5,0]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> nums = [3,2,1]
<strong>Output:</strong> 0
<strong>Explanation:</strong> There is no good way to split nums.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>3 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>
</ul>

"""
main goal:
Ensure the sum of the first part is less than or equal to the sum of the second part.
Ensure the sum of the second part is less than or equal to the sum of the third part.

Good if:
- array is split into 3 non-empty contiguous subarrays (left, mid and right) from left to right
- sum of elements in less is less than or equal to sum of elements in mid and sum in mid is less than or equal 
to sum of elements in right

strategy: prefix sums + 3 pointer

nums is array of non-negative ints
return: number of good ways to split nums (int)
return it modulo 10^9 + 7
"""

from typing import List

class Solution:
    """
    Time: O(n), since inner loops never reset
    Space: O(n)
    """
    def waysToSplit(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        
        # Compute prefix sums
        prefix_sums = [0]
        for num in nums:
            prefix_sums.append(prefix_sums[-1] + num)
        
        result = 0
        j, k = 0, 0
        
        # i gives end index of first subarray sum
        # j and k give the starting indexes of the second and third sums
        for i in range(1, n - 1):
            # Objective: increment j until it satisfies prefix_sums[i] <= (prefix_sums[j] - prefix_sums[i]).
            # ie as long as (j < n and prefix_sums[i] > (prefix_sums[j] - prefix_sums[i])) we need to increment j
            while j <= i or (j < n and prefix_sums[i] > (prefix_sums[j] - prefix_sums[i])):
                j += 1
            # Find the smallest k such that prefix_sums[k] - prefix_sums[i] <= prefix_sums[n] - prefix_sums[k]
            # The condition is structured to find the first position k where the middle subarray is no longer smaller or equal to R.
            # ie we take k 1 beyond the valid range to simplify the calculation of result
            while k < j or (k < n and prefix_sums[k] - prefix_sums[i] <= prefix_sums[n] - prefix_sums[k]):
                k += 1
            # k is now one past the valid range, so subtract 1 from k
            if k <= n:
                result = (result + k - j) % MOD
        
        return result
28900