Python - O(N^2) ➜ O(NLogN) | Well Commented Solution
1. BRUTE FORCE - O(N^2) - TLE\n\n\ndef waysToSplit(self, nums: List[int]) -> int:    \n\n\tways = 0      \n\n\t# Since there are three subarrays\n\t# It means, 
# **1. BRUTE FORCE - O(N^2) - TLE**\n\n```\ndef waysToSplit(self, nums: List[int]) -> int:    \n\n\tways = 0      \n\n\t# Since there are three subarrays\n\t# It means, basically, there are two boundaries. \n\t# left | mid | right => Here, each pipe (|) is a boundary\n\n\t# Wherever "left" subarray ends, let\'s say that index is "i"\n\t# Now for every "i", we can try to find the index where "mid" subarray ends\n\t# Such that, the condition given in problem is satisfied\n\tn = len(nums)\n\n\t# First, we convert the given array into a prefix sum array\n\tfor i in range(1, n): nums[i] = nums[i - 1] + nums[i]\n\n\t# The prefix sum array will help in such a way that\n\n\t# Suppose the "left" subarray ends at index "left"\n\t# Suppose the "mid" subarray starts at index "left + 1" and ends at index "mid"\n\t# And finally, suppose the "right" subarray starts at index "mid + 1" and ends at index "right"\n\n\t# To find the sum of "mid" subarray, all we need to do is nums[mid] - nums[left]\n\t# To find sum of "left" subarray, we just do nums[left]\n\t# To find sum of "right" subarray, we just do nums[right] - nums[mid]\n\n\t# For every i (index where "left" subarray ends)\n\t# Since "mid" and "right" subarrays need to have at least one element\n\t# The last index of "left" subarray can be up to "n-3" index\n\n\tfor i in range(n-2):\n\t\t# Each "j" index is the index at which "mid" subarray ends\n\t\tfor j in range(i + 1, n):\n\t\t\tleftSubarraySum = nums[i]\n\t\t\tmidSubarraySum = nums[j] - nums[i]\n\t\t\trightSubarraySum = nums[n - 1] - nums[j]\n\n\t\t\tif (leftSubarraySum <= midSubarraySum) and (midSubarraySum <= rightSubarraySum): \n\t\t\t\tways += 1\n\n\treturn ways % 1000000007\n```\n\n\n# **2. BINARY SEARCH - O(NLogN)**\n\n```\ndef waysToSplit(self, nums: List[int]) -> int:\n        \n        # Why did the Brute Force solution gave TLE?\n        # Because for each "i", we have to go through each possible "j"\n        # Instead of this, what if we can find the leftmost valid "j" and rightmost valid "j"\n        # In that way, the number of ways for that "i" is simply "rightmostIndex - leftmostIndex + 1"\n        # ANd that\'s where the Binary Search approach comes into picture.\n        \n        n = len(nums)\n        \n        # First, we convert the given array into a prefix sum array\n        for i in range(1, n): nums[i] = nums[i - 1] + nums[i]\n        \n        ways = 0\n        \n        # Here, each "i" is the last index of "left" subarray\n        # So, for every possible "i" value, we try to see how many ways are there to split\n\t\t# Since "mid" and "right" subarrays need to have at least one element\n\t\t# The last index of "left" subarray can be up to "n-3" index\n        for i in range(n-2):\n            \n            # For each "i", we will see what can be the leftmost valid position of "mid" subarray\'s right boundary\n            # That is, how much left we can keep the right boundary of "mid" subarray\n            # Such that the condition is still true\n            \n            # Since the "mid" subarray starts where the "left" subarray ends\n            # It means, start is "i + 1" since till "i" we have the "left" subarray\n            \n            start = i + 1\n            \n            # Since we want the right subarray to have at least one element\n            # The maximum index on right till where we can extend the "mid" subarray is (n - 2)\n            end = n - 2\n            \n            leftmostIndex = -1\n            \n            while start <= end:\n                mid = start + (end - start) // 2\n                \n                leftSubarraySum = nums[i]\n                midSubarraySum = nums[mid] - nums[i]\n                rightSubarraySum = nums[n - 1] - nums[mid]\n                \n                # if at "mid" the left subarray sum is <= mid subarray sum\n                # And the mid subarray sum is <= right subarray sum\n                # Then this is one possible way to split\n                # But we are looking for the leftmost valid position of "mid" subarray\'s boundary\n                # So keep searching on left side   \n                if (leftSubarraySum <= midSubarraySum) and (midSubarraySum <= rightSubarraySum):\n                    leftmostIndex = mid\n                    end = mid - 1\n                # If the leftsubarray sum is greater than mid subarray sum\n                # We need to increase the size of mid subarray so that its sum is bigger\n                # That is, its boundary should be placed at an index more than "mid"\n                # That\'s why we do start = mid + 1\n                elif leftSubarraySum > midSubarraySum:\n                    start = mid + 1      \n                # Otherwise, we can shift the boundary to left of mid as the leftsubarray sum is <= midsubarray sum\n                else: end = mid - 1\n            \n            # If leftmostIndex is -1, no need to continue further. We can skip this iteration\n            if leftmostIndex == -1: continue\n            \n            # *********************************************************************************\n                                                      \n            # Now, for each "left" boundary index "i", we will see what can be the rightmost valid position of "mid" index\n            # That is, how much right we can keep the right boundary of "mid" subarray\n            # Such that the condition is still true\n            \n            start = i + 1\n            end = n - 2\n            \n            rightmostIndex = -1\n            \n            while start <= end:\n                mid = start + (end - start) // 2\n                \n                leftSubarraySum = nums[i]\n                midSubarraySum = nums[mid] - nums[i]\n                rightSubarraySum = nums[n - 1] - nums[mid]\n                \n                # if at "mid" the left subarray sum is <= mid subarray sum\n                # And the mid subarray sum is <= right subarray sum\n                # Then this is one possible way to split\n                # But we are looking for the rightmost valid position of "mid" subarray\'s boundary\n                # So keep searching on right side   \n                if (leftSubarraySum <= midSubarraySum) and (midSubarraySum <= rightSubarraySum):\n                    rightmostIndex = mid\n                    start = mid + 1\n                # If the leftsubarray sum is greater than mid subarray sum\n                # We need to increase the size of mid subarray so that its sum is bigger\n                # That is, its boundary should be placed at an index more than "mid"\n                # That\'s why we do start = mid + 1\n                elif leftSubarraySum > midSubarraySum:\n                    start = mid + 1      \n                # Otherwise, we can shift the boundary to left of mid as the leftsubarray sum is <= midsubarray sum\n                else: end = mid - 1\n            \n            \n            if rightmostIndex != -1: \n                ways += (rightmostIndex - leftmostIndex + 1)\n\n        return ways % 1000000007\n```\n\n\n\n# **3. BINARY SEARCH - O(NLogN) - MORE READABLE CODE**\n\nInstead of writing the Binary Search logic for rightmost index again, we can create a separate helper method that takes care of both leftmost and rightmost index search.\n\n\n```\nclass Solution:\n    \n    # Helper method for Binary Search\n    def binarySearch(self, i, start, end, nums, isLeftSearch):\n        n = len(nums)\n        \n        index = -1\n        while start <= end:\n            mid = start + (end - start) // 2\n                \n            leftSubarraySum = nums[i]\n            midSubarraySum = nums[mid] - nums[i]\n            rightSubarraySum = nums[n - 1] - nums[mid]\n                \n\n            if (leftSubarraySum <= midSubarraySum) and (midSubarraySum <= rightSubarraySum):\n                    index = mid\n                    if isLeftSearch: end = mid - 1\n                    else: start = mid + 1\n            elif leftSubarraySum > midSubarraySum:\n                start = mid + 1      \n            else: end = mid - 1\n                \n        return index\n        \n        \n    \n    def waysToSplit(self, nums: List[int]) -> int:\n        \n        # Why did the Brute Force solution gave TLE?\n        # Because for each "i", we have to go through each possible "j"\n        # Instead of this, what if we can find the leftmost valid "j" and rightmost valid "j"\n        # In that way, the number of ways for that "i" is simply "rightmostIndex - leftmostIndex + 1"\n        # ANd that\'s where the Binary Search approach comes into picture.\n        \n        n = len(nums)\n        \n        # First, we convert the given array into a prefix sum array\n        for i in range(1, n): nums[i] = nums[i - 1] + nums[i]\n        \n        ways = 0\n        \n        # Here, each "i" is the last index of "left" subarray\n        # So, for every possible "i" value, we try to see how many ways are there to split\n        for i in range(n - 2):\n            \n            # For each "i", we will see what can be the leftmost valid position of "mid" subarray\'s right boundary\n            # That is, how much left we can keep the right boundary of "mid" subarray\n            # Such that the condition is still true\n            \n            leftmostIndex = self.binarySearch(i, i + 1, n - 2, nums, True)\n\n            # If leftmostIndex is -1, no need to continue further. We can skip this iteration\n            if leftmostIndex == -1: continue\n                                    \n            # Now, for each "left" boundary index "i", we will see what can be the rightmost valid position of "mid" index\n            # That is, how much right we can keep the right boundary of "mid" subarray\n            # Such that the condition is still true\n            \n            rightmostIndex = self.binarySearch(i, i + 1, n - 2, nums, False)\n            \n            if rightmostIndex != -1: ways += (rightmostIndex - leftmostIndex + 1)\n\n        return ways % 1000000007\n```
['Binary Search', 'Binary Tree', 'Python']