Split Array Largest Sum: Binary Search on the Answer

Split Array Largest Sum is LeetCode 410. You are given an integer array nums and an integer k. You need to split nums into k non-empty contiguous subarrays so that the largest sum among those subarrays is minimized. Return that minimized largest sum.

Example: nums = [7, 2, 5, 10, 8], k = 2. The optimal split is [7, 2, 5] and [10, 8], giving sums 14 and 18. The largest is 18, and no other 2-way split produces a smaller largest sum.

Why this problem matters

Split Array Largest Sum is one of the best problems for cementing the "binary search on the answer" pattern. You are not searching through an array for a target value. You are searching through all possible answers, finding the smallest one that satisfies a constraint. Once you see this framing, an entire family of hard problems becomes approachable.

This problem also shows up in real systems. Think about splitting a batch of tasks across workers so that no single worker is overloaded. Or distributing pages across volumes so no volume is too thick. Whenever you need to divide a sequence into groups while keeping the worst-case group as small as possible, this is the algorithm.

If you have already solved Koko Eating Bananas, you will recognize the skeleton immediately. The only thing that changes is the feasibility check.

The approach: binary search on the answer

The key insight is that the answer, the minimized largest subarray sum, must fall in a specific range:

• Lower bound: max(nums). No matter how you split, at least one subarray contains the largest element, so the answer cannot be smaller than that element.
• Upper bound: sum(nums). If you put everything in one group (which means k = 1), the largest sum is the total sum.

Now notice the monotonic structure. If you can split the array so that every group sum is at most X, you can also do it for X + 1 (just use the same split). If you cannot do it for X, you certainly cannot do it for X - 1. This means the range [max(nums), sum(nums)] splits into "infeasible" on the left and "feasible" on the right, and binary search finds the boundary.

For each candidate mid, you need a feasibility check: can you split nums into k or fewer subarrays such that no subarray sum exceeds mid? This check is greedy. Walk through the array, greedily extending the current subarray. When adding the next element would exceed mid, start a new subarray. Count how many subarrays you need. If it is k or fewer, the candidate is feasible.

def can_split(nums, k, max_sum):
    count = 1
    current = 0
    for num in nums:
        if current + num > max_sum:
            count += 1
            current = num
        else:
            current += num
    return count <= k

Step-by-step walkthrough

Let's binary search for the minimum valid largest sum with nums = [7, 2, 5, 10, 8] and k = 2. The search range is [10, 32], since max(nums) = 10 and sum(nums) = 32.

Four real iterations. Instead of checking all 23 possible values in the range, we checked 4 and found the answer. For larger ranges the savings are dramatic. Binary search on a range up to a billion still takes about 30 steps.

The complete solution

Here is the full Python solution for LeetCode 410:

def split_array(nums, k):
    lo, hi = max(nums), sum(nums)

    while lo < hi:
        mid = lo + (hi - lo) // 2
        count = 1
        current = 0
        for num in nums:
            if current + num > mid:
                count += 1
                current = num
            else:
                current += num

        if count <= k:
            hi = mid
        else:
            lo = mid + 1

    return lo

Let's walk through the important decisions.

lo = max(nums), hi = sum(nums). The tightest possible bounds. The answer is guaranteed to be somewhere in this range.

while lo < hi, not while lo <= hi. We are converging on a single answer. When lo == hi, that is our answer.

The greedy scan inside the loop. We walk through nums, accumulating a running sum. When adding the next element would push the sum past mid, we start a new group. This greedy approach always uses the fewest groups possible for a given mid, which is exactly what we need.

if count <= k: hi = mid. If we can split into k or fewer groups, the candidate works, but a smaller value might also work. So we keep mid in range and search left.

else: lo = mid + 1. If we need more than k groups, the candidate is too small. We need a larger max sum.

Complexity analysis

The binary search runs O(log(sum(nums) - max(nums))) iterations. Each iteration does a linear scan of the array in O(n). That gives O(n * log S) total, where S is the sum of the array.

The DP approach uses a 2D table where dp[i][j] is the answer for the first i elements split into j groups. It works, but it is much slower for large inputs. The binary search solution is both faster and simpler to implement.

Edge cases to watch for

• k = 1: No splitting at all. The answer is sum(nums).
• k = len(nums): Every element is its own group. The answer is max(nums).
• Single element: nums = [10], k = 1. The answer is 10.
• All elements equal: nums = [5, 5, 5, 5], k = 2. Split into [5, 5] and [5, 5], answer is 10.
• k equals array length: Each element stands alone, so max(nums) is the answer. The binary search handles this naturally because lo starts at max(nums).

The building blocks

This problem is built on one core pattern: binary search on the answer.

The skeleton is identical to what you see in Koko Eating Bananas and Capacity to Ship Packages (LeetCode 1011). Define a range of candidate answers, write a feasibility check, and binary search for the boundary.

while lo < hi:
    mid = lo + (hi - lo) // 2
    if is_feasible(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

What changes from problem to problem is the feasibility function. For Koko, you check if she can eat all bananas at speed mid within h hours. For Split Array Largest Sum, you check if you can partition the array into k or fewer groups where each group sums to at most mid. The binary search wrapper stays the same.

The feasibility check itself uses a greedy scan, which is a second building block. You walk through the array left to right, making the locally optimal choice at each step (extend the current group as long as possible). This greedy approach works because extending a group never makes things worse for future groups.

From understanding to recall

The logic clicks quickly. Binary search the answer range, greedily check each midpoint, narrow down. You probably see it clearly right now.

But try writing it from memory in two weeks. Was it lo < hi or lo <= hi? Do you set hi = mid or hi = mid - 1? What are the initial bounds, max(nums) and sum(nums) or something else? And the greedy check, do you start count at 0 or 1? These small details are easy to get wrong under pressure.

Spaced repetition closes the gap. You write the solution from scratch today, again tomorrow, then in a few days. After a few rounds, the while lo < hi template and the greedy partition check are automatic. You write them without hesitation and save your mental energy for problems that actually require new thinking.

Related posts

• Koko Eating Bananas - The classic introduction to binary search on the answer, searching eating speeds instead of array indices
• Binary Search (LeetCode 704) - The foundational binary search template that all search-on-answer problems build upon
• Find First and Last Position of Element in Sorted Array - Left-bound and right-bound binary search, the same convergence technique used here