Both binary Search -  O(n log n) and Two Pointers - O(n) with O(n) space
Since we want to split array into 3 subarrays, we need to make two cuts, so that array will be divided into 3 parts. Also given sum of numbers in each parts mus
Since we want to split array into 3 subarrays, we need to make two cuts, so that array will be divided into 3 parts. Also given sum of numbers in each parts must be greater than or equal to its previous part. It seems reasonable to take prefix sum of all elements and store them in array since **all elements in array are greater than or equal to 0. If we want to get the sum of elements in a given range [i,j] we can do prefixsum[j] - prefixsum[i - 1]**.\n\n**For each prefix sum P, we want to find F and L where F is the first position where F - P >= P and similary L -1 - P > E - (L - 1) where E is end of array**. \n\n**Now number of subarrays that satisfies our condition for a given prefix P is L - F**\n\n**Two pointers: O(n)**\nWe maintain two pointers **j** and **k** For a given prefix P, from P + 1 to find F, we can increment a pointer as long as F - P >= P. This works since prefix sums are sorted in non-decreasing order. \nSimilarly, to find F we do the same thing with another pointer k\n```\npublic int waysToSplit(int[] nums) {\n\tint count = 0, mod = 1_000_000_007, l = nums.length;\n\tfor(int i = 1; i < l; i++){\n\t\tnums[i] += nums[i - 1];\n\t}\n\tfor(int i = 0, j = 0, k = 0; i < l - 2; i++){\n\t\tif(j <= i){\n\t\t\tj = i + 1; //if j is less than i, move it after i to find F\n\t\t}\n\t\twhile(j < l - 1 && nums[i] > nums[j] - nums[i]){\n\t\t\tj++;\n\t\t}\n\t\tif(k < j) {\n\t\t\tk = j; //if k is greather than j, assign j to k, so that we find L\n\t\t}\n\t\twhile(k < l - 1 && nums[k] - nums[i] <= nums[l - 1] - nums[k]){\n\t\t\tk++;\n\t\t}\n\t\t//here k is the position where second subarray [i, k] is greater than third subarray [k, e]\n\t\t//hence from j till before k, all those elements form second subarray for a given prefix sum P which is at i\n\t\tcount = (count + k - j) % mod;\n\t}\n\treturn count;\n}\n```\n\n**Binary Search: O(n logn)**\n1) For each prefix sum **P**, find where we can make next cut so that its sum is bigger than or equal to current prefix sum **P**. We can do binary search since prefix sums array is non-decreasing. Lets call it **F**\n2) Similarly, once you find #1, do another binary search from F and find a position **L** where sum of elements from P to L is less than remaining sum (sum of elements from L to end of array **E**). Once we find L, we know that array is divided as [0, P] [P + 1, F] [P + 1, F + 1] [P + 1, F + 2] .... [p + 1, L - 1], [L - 1, E]. \n```\npublic int waysToSplit(int[] nums) {\n\tint[] psum = new int[nums.length];\n\tpsum[0] = nums[0];\n\tfor(int i = 1; i < nums.length; i++){\n\t\tpsum[i] = nums[i] + psum[i - 1];\n\t}\n\tint mod = 1_000_000_007;\n\tint count = 0;\n\tfor(int i = 0; i < nums.length - 2; i++){\n\t\tint fpos = findSecond(psum, i + 1, psum[i]);\n\t\tint spos = findThird(psum, i + 1, psum[i]);\n\t\tif(fpos < nums.length - 1 && spos < nums.length){\n\t\t\tif(psum[fpos] - psum[i] >= psum[i] && psum[spos - 1] - psum[i] <= psum[nums.length - 1] - psum[spos - 1]){\n\t\t\t\tcount = (count + spos - fpos) % mod;\n\t\t\t}\n\t\t}\n\t}\n\treturn count;\n}\n\nprivate int findSecond(int[] psum, int l, int esum){\n\tint h = psum.length - 1;\n\twhile(l < h){\n\t\tint mid = l + (h - l) / 2;\n\t\tif(psum[mid] - esum < esum) {\n\t\t\tl = mid + 1;\n\t\t}else if(psum[mid] - esum <= psum[psum.length - 1] - psum[mid]){\n\t\t\th = mid;\n\t\t}else {\n\t\t\th = mid - 1;\n\t\t}\n\t}\n\treturn l;\n}\nprivate int findThird(int[] psum, int l, int esum){\n\tint h = psum.length - 1;\n\twhile(l < h){\n\t\tint mid = l + (h - l) / 2;\n\t\tif(psum[mid] - esum < esum) {\n\t\t\tl = mid + 1;\n\t\t}else if(psum[mid] - esum <= psum[psum.length - 1] - psum[mid]){\n\t\t\tl = mid + 1;\n\t\t}else {\n\t\t\th = mid;\n\t\t}\n\t}\n\treturn l;\n}\n```\n\n
[]