This problem should be under leetcode hard
Though the concepts used in this problem is of medium level, the thought process to come up with the solution using prefix sum coupled with binary search is dif
Though the concepts used in this problem is of medium level, the thought process to come up with the solution using prefix sum coupled with binary search is difficult especially during a contest.\n\nMy solution : \n```\nclass Solution {\n    public int waysToSplit(int[] nums) {\n        int n = nums.length;\n        int[] prefix = new int[n + 1];\n        prefix[0] = nums[0];\n        for (int i = 1; i < n; i++) {\n            prefix[i] = prefix[i - 1] + nums[i];\n        }\n        int mod = 1000000007;\n        long count = 0;\n        \n        for (int i = 0; i < n - 2; i++) {\n            int x = prefix[i];\n            int y = 2 * x;\n            int low = i + 1;\n            int high = n - 2;\n            int ans = -1;\n            while (low <= high) {\n                int mid = low + (high - low) / 2;\n                if (prefix[mid] >= y) {\n                    ans = mid;\n                    high = mid - 1;\n                } \n                else low = mid + 1;\n            }\n            if (ans == -1) continue;\n            low = ans;\n            int ans2 = -1;\n            high = n - 2;\n            while (low <= high) {\n                int mid = low + (high - low) / 2;\n                 int diff2 = prefix[n - 1] - prefix[mid];\n                int diff1 = prefix[mid] - prefix[i];\n                if (diff1 <= diff2) {\n                    ans2 = mid;\n                    low = mid + 1;\n                }\n                else {\n                    high = mid - 1;\n                }\n                \n            }\n            if (ans2 == -1) continue;\n            count += (ans2 - ans + 1);\n       \n        }\n        return (int)(count % mod);\n    }\n}
[]