Python Binary search with explanation for linear/binary approach
The first step to solving this problem is realizing that you are choosing a first array, and for each first array, you are choosing a second and third sub array
The first step to solving this problem is realizing that you are choosing a first array, and for each first array, you are choosing a second and third sub array that fulfills the condition. By using cumulative sums, your [1,2,2,2,5,0] array becomes [1,3,5,7,12,12].\n\nThis now makes it easier to do a linear search to see if a current sub array is larger than the previous sub array by just subtracting the prefix sum at one index with another. So if you want to solve this problem in o(n^2) you can just loop for each first subarray, you find a first and last index +1 for the second array in which the second subarray sum can sum up to. Why is it first and last+1? Because for first sub array [1], you can have [2], and [2,2] which would fulfill the conditions the problem is asking. Now notice when you get to [2,2,2], the condition no longer becomes true. \n\nOnce you have your first and last index, you add the difference to your output because the difference (4-2) is how many subarrays can work with the first given subarray [1].  Then you do the same thing for first subarray [1,2], and you find only [2,2] that works with it. So your first and last index would be [2,3], and add 3-2 to your output. \n\nNow what do you look exactly for first and last index? The minimum the second subarray can be is the equivalent of the first. This is also double the first prefix sum. The maximum can be the mid point of the start of the second subarray and the end of the array. \n\nThis is how you do the linear approach, and from there since the cumulative sum array is sorted, you can do a binary search.\n```\ndef waysToSplit(self, nums: List[int]) -> int:\n        ps = list(accumulate(nums))\n        largest_split = cs[-1] / 3\n        output = 0\n\n        def find_first(arr, t, l, r):\n            while l < r:\n                m = l+(r-l)//2\n                if arr[m] >= t:\n                    r = m\n                else:\n                    l = m+1\n            return r\n        \n        def find_last(arr, t, l, r):\n            while l < r:\n                m = l+(r-l)//2\n                if arr[m] <= t:\n                    l = m+1\n                else:\n                    r = m\n            return l\n        for i in range(len(nums)-2):\n            if ps[i] > largest_split: break\n              \n            left = find_first(cs, 2*cs[i], i+1,len(nums)-1)\n            right = find_last(cs, (cs[-1] + cs[i])/2, i+1,len(nums)-1)\n            output += right-left\n\t\t\n\t\treturn output\n```
[]