Prefix Sum + Binary Search (Detailed Code)
Approach\n\nWe need two cuts in the array to divide into three parts- firstCut and secondCut. Iterate the secondCut from index = 2 to index = nums.length-1 whic
Approach\n\nWe need two cuts in the array to divide into three parts- firstCut and secondCut. Iterate the secondCut from index = 2 to index = nums.length-1 which will form the third subarray. Now, we need to find the position of the firstCut, which can range from 0 to secodCut-2, the secondCut at 0 means that 0th element is a part of first subarray and elements from (0+1)th index to (secondCut-1)th index are part of secod subarray.\n\nOne way is to traverse through all elements from 0-secondCut-2 to check if the condition holds and count the number of ways. This will result in a complexity of O(n^2). Instead we can use binary search over the prefixSum to get the minimum and maximum values of the firstCut ie the leftMost cut and the rightMost cut to form the first and second subarray. Code-\n\n```\nclass Solution {\n    public int waysToSplit(int[] nums) {\n        int mod = 1000000007;\n        int ways = 0;\n        int[] prefixSum = new int[nums.length+1];\n        prefixSum[0] = 0;\n        for(int i =0;i<nums.length;i++){\n            prefixSum[i+1] = prefixSum[i]+nums[i];\n        }\n        for(int j = 2;j<nums.length;j++){\n            int thirdSum = prefixSum[nums.length]-prefixSum[j];\n            int minIndex = getMinIndex(0,j-2,prefixSum,thirdSum,j);\n            if(minIndex == -1){\n                continue;\n            }\n            int maxIndex = getMaxIndex(0,j-2,prefixSum,thirdSum,j);\n            ways += (maxIndex-minIndex+1);\n            ways %= mod;\n        }\n        return ways;\n    }\n    \n    public int getMinIndex(int start,int end,int[] prefixSum,int thirdSum,int j){\n        if(start>end){\n            return -1;\n        }\n        int mid = (start+end)/2;\n        int firstSum = prefixSum[mid+1]-prefixSum[0];\n        int secondSum = prefixSum[j]-prefixSum[mid+1];\n        if(firstSum<=secondSum && secondSum<=thirdSum){\n            if(mid == 0){\n                return mid;\n            }\n            int prev = mid-1;\n            int firstPrevSum = prefixSum[prev+1]-prefixSum[0];\n            int secondPrevSum = prefixSum[j]-prefixSum[prev+1];\n            if(secondPrevSum>thirdSum){\n                return mid;\n            }\n            else{\n                return getMinIndex(start,mid-1,prefixSum,thirdSum,j);\n            }\n        }\n        else if(firstSum>secondSum){\n            return getMinIndex(start,mid-1,prefixSum,thirdSum,j);\n        }\n        return getMinIndex(mid+1,end,prefixSum,thirdSum,j);\n    }\n    \n    public int getMaxIndex(int start,int end,int[] prefixSum,int thirdSum,int j){\n        if(start>end){\n            return -1;\n        }\n        int mid = (start+end)/2;\n        int firstSum = prefixSum[mid+1]-prefixSum[0];\n        int secondSum = prefixSum[j]-prefixSum[mid+1];\n        if(firstSum<=secondSum && secondSum<=thirdSum){\n            if(mid == j-2){\n                return mid;\n            }\n            int next = mid+1;\n            int firstNextSum = prefixSum[next+1]-prefixSum[0];\n            int secondNextSum = prefixSum[j]-prefixSum[next+1];\n            if(firstNextSum>secondNextSum){\n                return mid;\n            }\n            else{\n                return getMaxIndex(mid+1,end,prefixSum,thirdSum,j);\n            }\n        }\n        else if(firstSum>secondSum){\n            return getMaxIndex(start,mid-1,prefixSum,thirdSum,j);\n        }\n        return getMaxIndex(mid+1,end,prefixSum,thirdSum,j);\n    }\n}\n```\n\n\n
[]