410. Split Array Largest Sum - Explanation

Problem Link

Description

You are given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized.

Return the minimized largest sum of the split.

A subarray is a contiguous part of the array.

Example 1:

Input: nums = [2,4,10,1,5], k = 2

Output: 16

Explanation: The best way is to split into [2,4,10] and [1,5], where the largest sum among the two subarrays is only 16.

Example 2:

Input: nums = [1,0,2,3,5], k = 4

Output: 5

Explanation: The best way is to split into [1], [0,2], [3] and [5], where the largest sum among the two subarrays is only 5.

Constraints:

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1,000,000
  • 1 <= k <= min(50, nums.length)


Company Tags

Please upgrade to NeetCode Pro to view company tags.



1. Recursion

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)

        def dfs(i, m):
            if i == n:
                return 0 if m == 0 else float("inf")
            if m == 0:
                return float("inf")

            res = float("inf")
            curSum = 0
            for j in range(i, n - m + 1):
                curSum += nums[j]
                res = min(res, max(curSum, dfs(j + 1, m - 1)))

            return res

        return dfs(0, k)

Time & Space Complexity

  • Time complexity: O(n∗2n)O(n * 2 ^ n)
  • Space complexity: O(n)O(n) for recursion stack.

2. Dynamic Programming (Top-Down)

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [[-1] * (k + 1) for _ in range(n)]

        def dfs(i, m):
            if i == n:
                return 0 if m == 0 else float("inf")
            if m == 0:
                return float("inf")
            if dp[i][m] != -1:
                return dp[i][m]

            res = float("inf")
            curSum = 0
            for j in range(i, n - m + 1):
                curSum += nums[j]
                res = min(res, max(curSum, dfs(j + 1, m - 1)))

            dp[i][m] = res
            return res

        return dfs(0, k)

Time & Space Complexity

  • Time complexity: O(k∗n2)O(k * n ^ 2)
  • Space complexity: O(k∗n)O(k * n)

Where nn is the size of the array numsnums and kk is the number of sub-arrays to form.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [[float("inf")] * (k + 1) for _ in range(n + 1)]
        dp[n][0] = 0

        for m in range(1, k + 1):
            for i in range(n - 1, -1, -1):
                curSum = 0
                for j in range(i, n - m + 1):
                    curSum += nums[j]
                    dp[i][m] = min(dp[i][m], max(curSum, dp[j + 1][m - 1]))

        return dp[0][k]

Time & Space Complexity

  • Time complexity: O(k∗n2)O(k * n ^ 2)
  • Space complexity: O(k∗n)O(k * n)

Where nn is the size of the array numsnums and kk is the number of sub-arrays to form.

4. Dynamic Programming (Space Optimized)

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        dp = [float("inf")] * (n + 1)
        dp[n] = 0

        for m in range(1, k + 1):
            nextDp = [float("inf")] * (n + 1)
            for i in range(n - 1, -1, -1):
                curSum = 0
                for j in range(i, n - m + 1):
                    curSum += nums[j]
                    nextDp[i] = min(nextDp[i], max(curSum, dp[j + 1]))
            dp = nextDp

        return dp[0]

Time & Space Complexity

  • Time complexity: O(k∗n2)O(k * n ^ 2)
  • Space complexity: O(n)O(n)

Where nn is the size of the array numsnums and kk is the number of sub-arrays to form.

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        def canSplit(largest):
            subarray = 1
            curSum = 0
            for num in nums:
                curSum += num
                if curSum > largest:
                    subarray += 1
                    if subarray > k:
                        return False
                    curSum = num
            return True

        l, r = max(nums), sum(nums)
        res = r
        while l <= r:
            mid = l + (r - l) // 2
            if canSplit(mid):
                res = mid
                r = mid - 1
            else:
                l = mid + 1
        return res

Time & Space Complexity

  • Time complexity: O(nlog⁡s)O(n \log s)
  • Space complexity: O(1)O(1)

Where nn is the size of the array numsnums and ss is the sum of all the elements in the array.

6. Binary Search + Prefix Sum

class Solution:
    def splitArray(self, nums: List[int], k: int) -> int:
        n = len(nums)
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]

        def canSplit(largest):
            subarrays = 0
            i = 0
            while i < n:
                l, r = i + 1, n
                while l <= r:
                    mid = l + (r - l) // 2
                    if prefix[mid] - prefix[i] <= largest:
                        l = mid + 1
                    else:
                        r = mid - 1
                subarrays += 1
                i = r
                if subarrays > k:
                    return False
            return True

        l, r = max(nums), sum(nums)
        res = r
        while l <= r:
            mid = l + (r - l) // 2
            if canSplit(mid):
                res = mid
                r = mid - 1
            else:
                l = mid + 1

        return res

Time & Space Complexity

  • Time complexity: O(n+(k∗log⁡n∗log⁡s))O(n + (k * \log n * \log s))
  • Space complexity: O(n)O(n)

Where nn is the size of the array numsnums, ss is the sum of all the elements in the array, and kk is the number of sub-arrays to form.