Back to main article
LC 410 Search on Answer Hard

Split Array Largest Sum

The hardest Search on Answer problem in this set. But the binary search structure is the same — only the feasibility check is more subtle.

Problem

What are we solving?

Problem Statement

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest subarray sum is minimized. Return the minimized largest sum.

Example
Input:nums = [7, 2, 5, 10, 8], k = 2
Output:18
Explanation:Split into [7,2,5] and [10,8] — largest sum = 18
Intuition

Minimize the maximum — classic search on answer

"Minimize the maximum" is the most common phrasing for Last/First True binary search on answer. We binary search the answer (the max subarray sum) and ask: "if I cap each subarray sum at X, can I split into at most k parts?"

If max sum X is feasible, any larger X is also feasible. The feasibility function is monotonic — perfect for binary search.

nums=[7,2,5,10,8], k=2 · Search space: max(nums)..sum(nums)
condition: canSplit(maxSum, k) — can split into ≤ k parts?
X=10F
X=15F
X=17F
X=18T*
X=20T
X=32T
At X=18: [7,2,5]→14, [10,8]→18. Two parts, max=18. Answer = 18.

The feasibility check

Greedily accumulate elements into the current subarray. When adding the next element would exceed the cap, start a new subarray and increment the part count. If parts ever exceed k, return false.

→

Identical to LC 1011: This is exactly the same feasibility check as Ship Packages — just with "subarrays" instead of "days" and "maxSum" instead of "capacity". Recognising this family means one template covers both.

Solution

Clean implementation

class Solution {
    public int splitArray(int[] nums, int k) {
        int left = 0, right = 0;
        for (int n : nums) { left = Math.max(left, n); right += n; }
        int boundary = right;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (canSplit(nums, mid, k)) {
                boundary = mid;
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return boundary;
    }

    private boolean canSplit(int[] nums, int maxSum, int k) {
        int parts = 1, cur = 0;
        for (int n : nums) {
            if (cur + n > maxSum) { parts++; cur = 0; }
            cur += n;
            if (parts > k) return false;
        }
        return true;
    }
}
class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        left, right = max(nums), sum(nums)
        boundary = right

        while left <= right:
            mid = left + (right - left) // 2
            if self.can_split(nums, mid, k):
                boundary = mid
                right = mid - 1
            else:
                left = mid + 1
        return boundary

    def can_split(self, nums, max_sum, k):
        parts, cur = 1, 0
        for n in nums:
            if cur + n > max_sum:
                parts += 1
                cur = 0
            cur += n
            if parts > k: return False
        return True

Complexity

Time
O(n log S)
S = sum(nums). log S binary search iterations, each O(n) greedy check.
Space
O(1)
Greedy scan uses constant space.
↑ Pattern map