Java Solution using Binary Search
Intuition\nI have to say this problem is not Medium at all. The idea about using Binary Search is not hard, yet to pass all the test cases, I have to spend 1 hr
# Intuition\nI have to say this problem is not Medium at all. The idea about using Binary Search is not hard, yet to pass all the test cases, I have to spend 1 hr working on this.\n\n# Approach\nFirst, we need to keep the left sum fixed. Then we find the leftmost middle position that left <= mid and the rightmost middle position that mid >= right.\n\n# Complexity\n- Time complexity: O(nlogn)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```\nclass Solution {\n    public int waysToSplit(int[] nums) {\n        int n = nums.length;\n        int[] prefix = new int[n];\n        for(int i = 0; i < n; i++){\n            prefix[i] = nums[i] + (i > 0 ? prefix[i-1] : 0);\n        }\n        //Binary search the range in which left will be <= than mid\n        //For each of that left, binary search the range in which mid will be <= right (add the range to the result)\n        long result = 0;\n        long MOD = 1000000007;\n\n        for(int i = 0; i < n-2; i++){\n            //Calculate by the range which mid <= right - the range which left <= mid\n            //Find the leftmost pos that mid >= left\n            //FInd the rightmost pos that mid <= right\n            int left = findLeftMid(i+1, n-1, prefix, prefix[i]);\n            int right = findRightMid(i+1, n-1, prefix);\n            if(left != -1 && right != -1 && right >= left){\n                //System.out.println(i + " " + left + " " + right);\n                int temp =  right - left + 1;\n                //System.out.println(temp);\n                result += ((long) temp % MOD);\n                result %= MOD;\n            }\n        }\n        return (int) result;\n    }\n    public int findLeftMid(int start, int end, int[] prefix, int threshold){\n        int left = start;\n        int right = end - 1;\n\n        while(right - left > 1){\n            int mid = left + (right - left)/2;\n            int sum = prefix[mid] - (start == 0 ? 0 : prefix[start-1]);\n            if(threshold <= sum){\n                right = mid;\n            }else{ //threshold > sum\n                left = mid;\n            }\n        }\n        if(threshold <= prefix[left] - (start == 0 ? 0 : prefix[start-1])){\n            return left;\n        }\n        if(threshold <= prefix[right] - (start == 0 ? 0 : prefix[start-1])){\n            return right;\n        }\n        return -1;\n    }\n\n    public int findRightMid(int start, int end, int[] prefix){\n        int left = start;\n        int right = end - 1;\n\n        while(right - left > 1){\n            int mid = left + (right - left)/2;\n            int leftSum = prefix[mid] - (start == 0 ? 0 : prefix[start-1]);\n            int rightSum = prefix[end] - prefix[mid];\n            if(leftSum <= rightSum){\n                left = mid;\n            }else{ //leftSum > rightSum\n                right = mid;\n            }\n        }\n        int leftSum = prefix[right] - (start == 0 ? 0 : prefix[start-1]);\n        int rightSum = prefix[end] - prefix[right];\n        if(leftSum <= rightSum){\n            return right;\n        }\n        leftSum = prefix[left] - (start == 0 ? 0 : prefix[start-1]);\n        rightSum = prefix[end] - prefix[left];\n        if(leftSum <= rightSum){\n            return left;\n        }\n        return -1;\n    }\n}\n```
['Java']