2270. Number of Ways to Split Array - Explanation

Problem Link



1. Brute Force

Intuition

A valid split at index i means the sum of elements from 0 to i is at least as large as the sum from i+1 to the end. The straightforward approach is to compute both sums for every possible split point by iterating through the relevant portions of the array each time.

Algorithm

  1. For each possible split index i from 0 to n - 2:
    • Compute leftSum by iterating from 0 to i.
    • Compute rightSum by iterating from i + 1 to n - 1.
    • If leftSum >= rightSum, increment res.
  2. Return the count of valid splits.
class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0

        for i in range(n - 1):
            leftSum = 0
            for j in range(i + 1):
                leftSum += nums[j]

            rightSum = 0
            for j in range(i + 1, n):
                rightSum += nums[j]

            res += (1 if leftSum >= rightSum else 0)

        return res

Time & Space Complexity

  • Time complexity: O(n2)O(n ^ 2)
  • Space complexity: O(1)O(1)

2. Prefix Sum

Intuition

Recomputing sums from scratch for each split is wasteful. By precomputing a prefix sum array, we can find the sum of any subarray in constant time. The left sum up to index i is prefix[i], and the right sum is prefix[n] - prefix[i].

Algorithm

  1. Build a prefix sum array where prefix[i] is the sum of the first i elements.
  2. For each split index i from 1 to n - 1:
    • left = prefix[i].
    • right = prefix[n] - prefix[i].
    • If left >= right, increment res.
  3. Return the count.
class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)

        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        res = 0
        for i in range(1, n):
            left = prefix[i]
            right = prefix[n] - prefix[i]
            if left >= right:
                res += 1

        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(n)O(n)

3. Prefix Sum (Optimal)

Intuition

We don't need to store the entire prefix sum array. Instead, we can maintain a running left sum and right sum. Start with right as the total, then shift elements from right to left as we iterate through possible split points.

Algorithm

  1. Compute the total sum and assign it to right.
  2. Initialize left = 0 and res = 0.
  3. For each index i from 0 to n - 2:
    • Add nums[i] to left and subtract it from right.
    • If left >= right, increment res.
  4. Return res.
class Solution:
    def waysToSplitArray(self, nums: List[int]) -> int:
        right = sum(nums)
        left = res = 0

        for i in range(len(nums) - 1):
            left += nums[i]
            right -= nums[i]
            res += 1 if left >= right else 0

        return res

Time & Space Complexity

  • Time complexity: O(n)O(n)
  • Space complexity: O(1)O(1)