Clean and easy to understand solution || JAVA || Binary Search
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intution to this problem is to observe that instead of iterating over every case an
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intution to this problem is to observe that instead of iterating over every case and finding the sum of the three splits, we can do binary search to find the first and last case which satisfies the given conditions. The difference between the first and the last case will be the number of splits possible.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n[1, 2, 4, 5, 6]\nLet this be the input.\nFirst we will find the prefix sum of this array to access sum of the splits in O(1) complexity.\n\n[1, 3, 7, 12, 18]\nthen we will iterate over the array till len - 3 index, because we will require atleast two index len - 2 and len - 1 for middle and last split\n\ntwo pointers j and k can be used to satisfy the conditions:\n1. nums[j] - nums[i] >= nums[i]\n2. nums[k] - nums[i] > nums[n - 1] - nums[k]\n\nj and k are found using binary search\nRange j - k, is the accepted range.\n# Complexity\n- Time complexity: O(nlog(n))\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity: O(1)\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        long res = 0;\n        // finding prefix sum\n        for(int i = 1; i < n; i++) nums[i] += nums[i - 1];\n        for(int i = 0; i < n - 2; i++){\n            // j to k will be the range for which we get good split\n            // 0 - i, first.... i - j/k, second..... j/k - n - 1, thrid\n            int j = i + 1;\n            int right = n - 2;\n            // this binary search will satisfy the condition for first and second splits\n            while(j <= right){\n                int mid = (j + right)/2;\n                if(nums[mid] - nums[i] < nums[i]) j = mid + 1;\n                else right = mid - 1; \n            }\n            int k = j;\n            right = n - 2;\n            // this BS will satisfy the condition for second and thrid splits\n            while(k <= right){\n                int mid = (k + right)/2;\n                if(nums[mid] - nums[i] <= nums[n - 1] - nums[mid]) k = mid + 1;\n                else right = mid - 1; \n            }\n            // now we can simply add the range k - j into our result\n            res = (res + k - j) % 1000000007;\n        }\n        return (int)res;\n    }\n}\n```\n\nThank you\nUpvote if found helpful\n\n
['Binary Search', 'Prefix Sum', 'Java']