C++ O(N) Prefix Sum Three Pointers Solution
Runtime: 233 ms, faster than 72.07% of C++ online submissions for Ways to Split Array Into Three Subarrays.\nMemory Usage: 81.5 MB, less than 74.31% of C++ onli
Runtime: 233 ms, faster than 72.07% of C++ online submissions for Ways to Split Array Into Three Subarrays.\nMemory Usage: 81.5 MB, less than 74.31% of C++ online submissions for Ways to Split Array Into Three Subarrays.\n\n**Solution taken from votrubac.**\n\n```\nWe use three pointer Left, Mid and Right to find the possible subarray count.\nFor calculating the range sum of values in this immutable array, we generate its prefix sum.\n\nLeft pointer is the last pointer of first part.\nMid pointer is the first / minimum pointer of middle part.\nRight pointer is the last / maximum pointer of middle part.\n\nNow we loop through array with Left value 0 to N-1. For each Left value we find the \nMid and Right pointer and the range of Mid and Right pointer is the possible ways \nto split array for that Left pointer. As Left increases, Mid and Right increases too and\nmoves forward without resetting which makes the solution O(N).\n\nWe move Mid pointer forward as long as Mid value is less than 2 * Left value\nWe move Right pointer forward as long as middle part sum <= last part sum\n```\n\n```\nclass Solution {\npublic:\n    int waysToSplit(vector<int>& nums) {\n        \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```
['C', 'Prefix Sum']