Python: Easily explained brute force to optimized
Here, they are asking to count such events/occurances where:\n the array can be splitted into two non-empty parts, such that \n the sum of elements in first par
Here, they are asking to **count such events**/occurances where:\n* the array can be splitted into **two non-empty parts**, such that \n* the sum of elements in first part **>=** sum of elements in second parts.\n\nA prefix sum array is an array that stores at ith index,  the sum of all elements encountered from 0th index upto the ith index (inclusive). How can this help?\n* The prefix sum has a property that it `avoids recomputation of sum`. \n* The sum upto element i can be obtained by `prefix_sum[i]`.\n* The sum from i + 1 to last element of array can be obtained by `prefix_sum[n-1] - prefix_sum[i]`\n\nThe full code (***written during contest***) is given below:\n```\nclass Solution:\n    def waysToSplitArray(self, nums: List[int]) -> int:\n        prefix_sum = [nums[0]]\n        n = len(nums)\n        for i in range(1, n):\n            prefix_sum.append(nums[i] + prefix_sum[-1]) \n        \n        count = 0\n        for i in range(n-1):\n            if prefix_sum[i] >= prefix_sum[n-1] - prefix_sum[i]:\n                count += 1\n        return count\n```\n\n**Time and Space Complexity Analysis:**\nWe iterate through each element of the array in a linear fashion. Hence, **time complexity = O(n)**.\nAlso, we maintain a extra space of size \'n\' for prefix_sum array. Hence, **space complexity = O(n)**.\n\n***Can we do any better?***\n* In terms of time: **NO**. We will need to traverse the array atleast once (at any cost, in any situation).\n* In terms of space: **YES**. We actually do not need a complete prefix array.\n\nLet\'s see how!\n\nWe just need to have two sum variables storing the sum of left part and right part.\nInitially, the left part will contain the `first element` and right part will contain `sum of array - the first element`.\nAs we increment the index, we take the current nums[i] value and add it to the left part and remove it from the right part.\n\nHence ***reducing the space complexity to O(1).***\n\nSimple and Sweet.\n\nThe full code (***space optimized***) is given below:\n```\nclass Solution:\n    def waysToSplitArray(self, nums: List[int]) -> int:\n        count = 0\n        left_sum, right_sum = 0, sum(nums)\n        for i in range(len(nums) - 1):\n            left_sum += nums[i]\n            right_sum -= nums[i]\n            if left_sum >= right_sum:\n                count += 1\n        return count\n```\n\nUpvote, if helpful.
['Python']