<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>

'''
Not sure how to traverse in a way for O(n)

Brute Force seems to be for every length of the array, you have this window of size n, and then you iterate that as if it was the "middle" portion

Can I simplify the problem down -> for my left window if my sum is X -> can i split the rest of the array into two that are greater than X?

Can I do this in O(n) processing in two passes?

Or it's more like -> I just need to split it up so that the sum of the left is greater than the sum of the right given a minimum sum X

mid pointer is as far as left as possible to make sure it is greater than the first sum, and the right pointer is as far as right as possible to account for all the possible ranges

so you add res right_pointer - mid_pointer

You need a j pointer because not everything iwll work from i + 1, you need to have some elements for j so it is >= i
Conditions are a bit tricky since you don't know how to figure out m_sum without k and you want to do m first...

I think the traversal problem I've had -> if it's fixed you can use pointers...and the fact that they move linearly is what you need to know that it is O(n) so those two points
- Fixed splits
- O(n) since all pointers move linearly
'''

class Solution:
    def waysToSplit(self, nums: List[int]) -> int:
        i = 0
        j = 1
        k = 2
        prefix_sum = [0] * len(nums)
        
        cur_sum = 0
        for i in range(len(nums) - 1, -1, -1):
            cur_sum += nums[i]
            prefix_sum[i] = cur_sum
            
        l_sum = 0
        res = 0
        mod = pow(10, 9) + 7
        while i <= len(nums) - 3:
            l_sum += nums[i]
           
            # Make sure j is in a minimum spot that is good (inclusive)
            while j <= i or (j < len(nums) - 1 and prefix_sum[i + 1] - prefix_sum[j + 1] < l_sum):
                j += 1
                
            while k < j or (k < len(nums) - 1 and prefix_sum[k + 1] >= prefix_sum[i + 1] - prefix_sum[k + 1]):
                k += 1
            
 
            i += 1
            
            if j < k:
                res = (res + k - j) % mod
            
            
        return res
            
            
            
            
886