C++ | Binary Search | Prefix Sum
\n\n\nclass Solution {\npublic:\n    int waysToSplit(vector<int>& nums) {\n     int n = nums.size();\n        \n        // generate prefix sum\n        for(int 
\n\n```\nclass Solution {\npublic:\n    int waysToSplit(vector<int>& nums) {\n     int n = nums.size();\n        \n        // generate prefix sum\n        for(int i=1;i<n;i++)nums[i]+=nums[i-1];\n        \n        int left  = 0;  // last pointer of first part\n        int mid = 1;    // first pointer of middle part\n        int right = 2;  // last pointer of middle part\n        int count = 0;\n        \n        // loop through array and find the mid and right for each left pointer\n        // as left pointer moves forward, mid and right pointer moves forward too\n        while(left < n-2)\n        {\n            mid = max(mid,left+1);\n            \n            // move mid forward as long as sum till mid < 2 * sum till left  \n            // goal is to find the minimum pointer of middle part for current left part\n            while(mid<n-1 && nums[mid]<2*nums[left])mid++;\n            \n            right = max(mid,right);\n\n            // move right forward as long as mid part sum <= right part sum\n            // goal is to find the maximum pointer of middle part for current left part\n            while(right<n-1 && nums[right]-nums[left]<=nums[n-1]-nums[right])right++;\n            \n            count = (count + right - mid) % 1000000007;\n            \n            left++;\n        }\n        \n        return count;   \n    }\n};\n```\n\nUpvote If you liked.
['Binary Tree', 'Prefix Sum']