C# | Linear solution | First divide position any, second one is in a range
April 6, 2022\nIntroduction\nI came cross this algorithm and read votrubac\'s solution, but I did not understand, so I took 10 minutes to convert his Java code 
April 6, 2022\n**Introduction**\nI came cross this algorithm and read votrubac\'s solution, but I did not understand, so I took 10 minutes to convert his Java code to C# code, and then asked myself a few times during those 15 minutes, why it is a linear solution, why it is (j - k)? What is the special for the range?\n\n**Analysis by votrubac | My quick study**\nInput: nums = [1,2,2,2,5,0]\nOutput: 3\nExplanation: There are three good ways of splitting nums:\n[1] [2] [2,2,5,0]\n[1] [2,2] [2,5,0]\n[1,2] [2,2] [5,0]\n\nThe first subarray can start from index = 0, and stop at any position with the condition: i < length - 2. \nSecond array position ends where? We have to find the minimum index to make sure that sum of second subarray is bigger than the first leftmost subarray\'s sum. \n\nThird array position starts where? What is maximum start position for the third array? Skip this discussion for my own analysis. \n\nBased on the above analysis, the second array minimum end position and third subarray last start position is total count of ways to divide. \n\nRead more carefully about the analysis provided by votrubac in the following:\nFirst, we prepare the prefix sum array, so that we can compute subarray sums in O(1). Then, we move the boundary of the first subarray left to right. This is the first pointer - i.\nFor each point i, we find the minimum (j) and maximum (k) boundaries of the second subarray:\n```\n* nums[j] >= 2 * nums[i]\n* nums[sz - 1] - nums[k] >= nums[k] - nums[i]\n```\nNote that in the code and examples below, k points to the element after the second array. In other words, it marks the start of the (shortest) third subarray. This makes the logic a bit simpler.\n\nTime complexity: O(N)\n\n**My thought process | Not good enough | Ensure linear solution is correct!**\nBrute force solution - it is easy, two position to determine, so time complexity should be O(N^2). \n\nHow to find optimal one? What is optimal time complexity? O(N) or O(NlogN)?\n\nI did not come out my own option solution, and I thought about using prefix sum array first, and then think about how to find maximum end position of second subarray using binary search, bigggest start position of third subarray using binary search. \n\nIt seems to be O(NlogN) best approach. \n\nI came cross this discuss post in votrubac linear solution:\n**"..to realize that j and k will only move forward, which result in a linear-time solution.." ---The key point of the solution. I like it.**\nIn other words, the following statement for loop in terms of i will take O(N) time.\n```\nfor (int i = 0, j = 0, k = 0; i < length - 2; ++i)\n```\nInside for loop, while loop for j also takes O(N) time, since j will only increase, not go back to 0 for next iteration in for loop. So j iteration steps also is O(N)\n```\nwhile (j <= i || (j < length - 1 && nums[j] < nums[i] * 2))\n```\nThe above statement, i = 0, j will be a number; next iteration i = 1, j will start from previous number and continue to increment one by one. \n\nInside for loop, while loop for k also takes O(N) time. Same argument as j. \n```\nwhile (k < j || (k < length - 1 && nums[k] - nums[i] <= nums[length - 1] - nums[k]))\n```\n\n\n\nThe following C# code passes online judge. \n\n```\nusing System;\nusing System.Collections.Generic;\nusing System.Linq;\nusing System.Text;\nusing System.Threading.Tasks;\n\nnamespace _1712_ways_to_split\n{\n    class Program\n    {\n        static void Main(string[] args)\n        {\n        }\n        /// <summary>\n        /// study code\n        /// https://leetcode.com/problems/ways-to-split-array-into-three-subarrays/discuss/999257/C%2B%2BJavaPython-O(n)-with-picture\n        /// time complexity: O(N)\n        /// </summary>\n        /// <param name="nums"></param>\n        /// <returns></returns>\n        public int WaysToSplit(int[] nums)\n        {\n            var length = nums.Length;\n            var count = 0;\n\n            for (int i = 1; i < length; ++i)\n            {\n                nums[i] += nums[i - 1];\n            }\n\n            // i < j < k\n            for (int i = 0, j = 0, k = 0; i < length - 2; ++i)\n            {\n                // j - maximum count: O(N) - make sure that j > i, but nums[j] >= nums[i] * 2\n                while (j <= i || (j < length - 1 && nums[j] < nums[i] * 2))\n                {\n                    ++j;\n                }\n\n                // k - make sure that k >= j, but rightmost subarray\'s sum is bigger than second one\n                while (k < j || (k < length - 1 && nums[k] - nums[i] <= nums[length - 1] - nums[k]))\n                {\n                    ++k;\n                }\n\n                // find k - j ways to divide the way into three subarrays. \n                // because if the second array is stopped between any index position from j to k, it will work. \n                count = (count + k - j) % 1000000007;\n            }\n\n            return count;\n        }\n    }\n}\n```\n
[]