Number of Ways to Split Array

main.md

Question

Approach

Approach 1

My first approach was to create count and left_arr varaible to store my valid count and left split.

I then iterated through the array, stopping at the second-to-last index. This is because a valid split must leave at least one element on the right side. At each iteration, I appended the current element (nums[i]) to left_arr, gradually building the left portion of the split. To define the right portion, I took a slice of the array starting from the next index (i + 1) to the end, ensuring the right side always included all elements after the split point.

Next, I calculated the sum of the elements in both the left and right portions. For the left portion, I summed the elements in left_arr, and for the right portion, I summed the sliced array nums[i + 1:]. I then checked if the sum of the left side was greater than or equal to the sum of the right side. If the condition was satisfied, I considered the split valid and incremented the count.

After iterating through the whole split points, I calculate the count and return the final value of count. This solution looks good but it results to a TLE submssion due to large test cases (and maybe other factors idk about).

Implementation

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        count = 0
        left_arr = []

        for i in range(len(nums) - 1):
            left_arr.append(nums[i])
            right_arr = nums[i + 1:]

            left_sum = sum(left_arr)
            right_sum = sum(right_arr)

            if left_sum >= right_sum:
                count += 1

        return count

Complexities

• Time: O(n^2) due to the repeated slicing and summing.
• Space: O(n) for storing the left_arr and right_arr.

Approach 2 - Using Prefix Sum

This method eliminates the repeated computation of sums for both the left and right parts of the array at each split.

I first calculated the total sum of the entire array. This total sum serves as a reference to dynamically compute the sum of the right side of the split at any point, without explicitly creating a separate array for it. Next, I created a variable, left_sum, to keep track of the cumulative sum of elements on the left side as I iterated through the array. At each step in the iteration, I updated the left_sum by adding the current element to it, representing the sum of all elements from the beginning of the array up to the current index.

Using the total sum and the updated left_sum, I calculated the sum of the right side dynamically by subtracting left_sum from total_sum using right_sum = total_sum − left_sum to avoid creating a suffix sum array or recalculating the right-side sum from scratch.

After getting the sums for both sides, I then checked if the left_sum was greater than or equal to the right_sum. If the condition was met, I incremented a counter. This process continued for each possible split point until the second-to-last index, as the split must leave at least one element on the right side. After the iteration was complete, I now returned the final value of count.

Implementation

class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        count = 0
        left_count = 0
        total_sum = sum(nums)

        for i in range(len(nums) - 1):
            left_sum += nums[i]
            right_sum = total_sum - left_sum

            if left_sum >= right_sum:
                count += 1

        return count

Complexities

• Time: O(n) because I iterate through the array once.
• Space: O(1) since I only use a few variables for storage.