2270. Number of Ways to Split Array - Explanation

Problem Link



1. Brute Force

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

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)

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)