[Java/Scala] Detailed Explanation - Prefix Sum - Binary Search
Key Notes:\n- Naive solution would be: O(N^2), searching all two points, which separates leftSum, midSum and rightSum\n- To quickly find the range sum, we will 
**Key Notes:**\n- Naive solution would be: O(N^2), searching all two points, which separates leftSum, midSum and rightSum\n- To quickly find the range sum, we will use **prefix sum** here (10^4 * 10^5 not out of bound of Integer, we good)\n- By fixing one point (A), we could use binary search to find another point (B).\n\t- If the point B is too left, the **midSum** will be too small\n\t- If the point B is too right, the **rightSum** will be too small\n\t- Basically, we are finding **a range of the point B**, which satisfies the condition (leftSum <= midSum <= rightSum)\n\t\t- Similar the to question [34. Find First and Last Position of Element in Sorted Array](https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/)\n\n![image](https://assets.leetcode.com/users/images/9ca8c136-7c3d-4e6c-ad2a-3f9090c26053_1609657205.8195658.png)\n\n```java\npublic int waysToSplit(int[] nums) {\n        \n\tint MOD = (int) (1e9 + 7);\n\n\tint N = nums.length;\n\n\t// prefix array\n\tint[] A = new int[N];\n\tA[0] = nums[0];\n\tfor (int i = 1; i < N; ++i) A[i] = A[i - 1] + nums[i];\n\n\tint res = 0;\n\tfor (int i = 1; i < N - 1; ++i) {\n\t\n\t\tif (A[i - 1] > (A[N - 1] - A[i - 1]) / 2) break;  // early termination\n\n\t\tint left = helper(A, A[i - 1], i, true);\n\t\tint right = helper(A, A[i - 1], i, false);\n\n\t\tif (left == -1 || right == -1) continue;  // none is satisfied\n\n\t\tres = (res + (right - left + 1) % MOD) % MOD;\n\t}\n\n\treturn res;\n}\n\nprivate int helper(int[] A, int leftSum, int index, boolean searchLeft) {\n\n\tint N = A.length;\n\tint l = index, r = N - 2;\n\tint res = -1;\n\n\twhile (l <= r) {\n\n\t\tint m = (r - l) / 2 + l;\n\t\tint midSum = A[m] - A[index - 1];\n\t\tint rightSum = A[N - 1] - A[m];\n\n\t\tif (leftSum <= midSum && midSum <= rightSum) {\n\t\t\tres = m;\n\t\t\tif (searchLeft) r = m - 1;\n\t\t\telse l = m + 1;\n\t\t} else if (leftSum > midSum) {  // shrink left\n\t\t\tl = m + 1;\n\t\t} else {  // shrink right\n\t\t\tr = m - 1;\n\t\t}\n\n\t}\n\n\treturn res;\n}\n```\n**Poor Scala Version** (Feel free to correct/improve/accuse my poor/naive Scala code, I would really appreciate that!)\n```scala\ndef waysToSplit(nums: Array[Int]): Int = {\n        \n\tval MOD = (1e9 + 7).toInt\n\tval N = nums.length\n\n\t// prefix array\n\tval A: Array[Int] = nums.map{var s = 0; d => {s += d; s}}\n\n\tdef binarySearch(A: Array[Int], leftSum: Int, index: Int, searchLeft: Boolean): Int = {\n\t\n\t\t@tailrec\n\t\tdef binarySearchHelper(l: Int, r: Int, acc: Int): Int = {\n\t\t\tif (l > r) acc\n\t\t\telse {\n\t\t\t\tval m = (r - l) / 2 + l\n\t\t\t\tval midSum = A(m) - A(index - 1)\n\t\t\t\tval rightSum = A(N - 1) - A(m)\n\n\t\t\t\tif (leftSum <= midSum && midSum <= rightSum)\n\t\t\t\t\tbinarySearchHelper(if (searchLeft) l else m + 1, if (searchLeft) m - 1 else r, m)\n\t\t\t\telse if (leftSum > midSum) binarySearchHelper(m + 1, r, acc)\n\t\t\t\telse binarySearchHelper(l, m - 1, acc)\n\t\t\t}\n\t\t}\n\t\t\n\t\tbinarySearchHelper(index, N - 2, -1)\n\t}\n\n\t@tailrec\n\tdef waysToSplitHelper(i: Int, res: Int): Int = {\n\t\tif (i == N - 1) res\n\t\telse {\n\t\t\tval left = binarySearch(A, A(i - 1), i, searchLeft = true)\n\t\t\tval right = binarySearch(A, A(i - 1), i, searchLeft = false)\n\t\t\twaysToSplitHelper(i + 1, if (left == -1 || right == -1) res else (res + (right - left + 1)) % MOD)\n\t\t}\n\t}\n\t\n\twaysToSplitHelper(1, 0)\n}\n```\nHappy new year!
[]