410. Split Array Largest Sum - Explanation

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

Intuition

We want to split the array into k subarrays and minimize the maximum sum among them. Using recursion, we try every possible way to form the first subarray, then recursively solve for the remaining elements with k-1 subarrays. For each split point, we track the maximum sum between the current subarray and the best result from the recursive call, then take the minimum across all choices.

Algorithm

Define dfs(i, m) where i is the starting index and m is the number of subarrays left to form.
Base cases: if i == n and m == 0, return 0 (valid split). If either condition fails alone, return infinity (invalid).
For each possible endpoint j of the current subarray:
- Accumulate the sum from index i to j.
- Recursively solve dfs(j + 1, m - 1) for the remaining portion.
- Track min(res, max(curSum, recursiveResult)).
Return the result of dfs(0, k).

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 * 2 ^ n)$
Space complexity: $O(n)$ for recursion stack.

2. Dynamic Programming (Top-Down)

Intuition

The recursive solution has overlapping subproblems since we may compute dfs(i, m) multiple times with the same parameters. By caching results in a memoization table, we avoid redundant computation. The state is defined by the current index and remaining subarrays to form.

Algorithm

Create a 2D memoization table dp[n][k+1] initialized to -1.
Use the same recursive structure as the brute force approach.
Before computing, check if dp[i][m] is already computed. If so, return the cached value.
After computing the result for state (i, m), store it in dp[i][m].
Return dfs(0, k).

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 * n ^ 2)$
Space complexity: $O(k * n)$

Where $n$ is the size of the array $nums$ and $k$ is the number of sub-arrays to form.

3. Dynamic Programming (Bottom-Up)

Intuition

We can convert the top-down approach to bottom-up by filling the DP table iteratively. We build solutions for smaller subproblems first (fewer subarrays, starting from the end of the array) and use them to solve larger problems. The table dp[i][m] represents the minimum largest sum when splitting elements from index i to the end into m subarrays.

Algorithm

Create dp[n+1][k+1] initialized to infinity, with dp[n][0] = 0 as the base case.
For each number of subarrays m from 1 to k:
- For each starting index i from n-1 down to 0:
  - Try all possible endpoints j for the first subarray.
  - Compute dp[i][m] = min(dp[i][m], max(curSum, dp[j+1][m-1])).
Return dp[0][k].

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 * n ^ 2)$
Space complexity: $O(k * n)$

Where $n$ is the size of the array $nums$ and $k$ is the number of sub-arrays to form.

4. Dynamic Programming (Space Optimized)

Intuition

In the bottom-up approach, computing dp[i][m] only depends on values from dp[...][m-1]. We can reduce space from O(k * n) to O(n) by using two 1D arrays: one for the previous layer and one for the current layer, swapping them after each iteration.

Algorithm

Create two 1D arrays dp and nextDp of size n+1, initialized to infinity with dp[n] = 0.
For each number of subarrays m from 1 to k:
- Reset nextDp to infinity.
- For each starting index i, compute the minimum largest sum using the previous dp array.
- Swap dp and nextDp.
Return dp[0].

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 * n ^ 2)$
Space complexity: $O(n)$

Where $n$ is the size of the array $nums$ and $k$ is the number of sub-arrays to form.

5. Binary Search

Intuition

Instead of trying all possible splits, we binary search on the answer itself. The minimum possible largest sum is the maximum element (when k equals n), and the maximum is the total sum (when k equals 1). For a given target sum, we greedily check if we can split the array into at most k subarrays where no subarray exceeds the target. If possible, we try a smaller target; otherwise, we need a larger one.

Algorithm

Set l = max(nums) and r = sum(nums).
Binary search while l <= r:
- For mid, check if we can split into at most k subarrays with max sum <= mid.
- The check greedily adds elements until the sum exceeds mid, then starts a new subarray.
- If feasible, record mid as a candidate and search for smaller values.
- Otherwise, search for larger values.
Return the smallest feasible value.

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(n \log s)$
Space complexity: $O(1)$

Where $n$ is the size of the array $nums$ and $s$ is the sum of all the elements in the array.

6. Binary Search + Prefix Sum

Intuition

We can optimize the feasibility check using prefix sums and binary search. Instead of linearly scanning to find where each subarray should end, we use binary search on the prefix sum array to find the farthest index where the subarray sum stays within the target. This speeds up the check from O(n) to O(k log n) for each candidate.

Algorithm

Build a prefix sum array where prefix[i] is the sum of elements from index 0 to i-1.
Binary search on the answer as before.
In the feasibility check:
- For each subarray start, binary search for the rightmost end where prefix[end] - prefix[start] <= target.
- Count subarrays and verify it does not exceed k.
Return the smallest feasible value.

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))$
Space complexity: $O(n)$

Where $n$ is the size of the array $nums$ , $s$ is the sum of all the elements in the array, and $k$ is the number of sub-arrays to form.

Common Pitfalls

Setting Incorrect Binary Search Bounds

The lower bound must be max(nums) (not 0 or 1) because no subarray sum can be smaller than the largest single element. The upper bound is sum(nums) representing the case where all elements are in one subarray. Using incorrect bounds leads to invalid answers or infinite loops.

Off-by-One in Subarray Counting

When checking if a target sum is feasible, starting the subarray count at 0 instead of 1 causes the algorithm to allow one extra split. The count should start at 1 since we always have at least one subarray before any splits occur.

Integer Overflow in Sum Calculations

For large arrays with large values, the sum of elements can overflow 32-bit integers. Using long or equivalent 64-bit types for prefix sums and running totals prevents incorrect comparisons and ensures the binary search operates on valid values.

Greedy Check Not Resetting Current Sum

In the feasibility check, when the current sum exceeds the target and a new subarray begins, the current sum must be reset to the current element (not to 0). Resetting to 0 loses the current element and produces incorrect subarray counts.

Confusing Minimizing Maximum with Maximizing Minimum

This problem asks to minimize the largest subarray sum, which means we want the smallest possible value that still allows a valid k-way split. Binary searching in the wrong direction (trying to maximize instead of minimize) yields incorrect results.