Split Array Largest Sum — Binary Search on Answer [LC 410, Google, Facebook]

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 that minimized largest sum.

Constraints:

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

Input:  nums = [7,2,5,10,8], k = 2
Output: 18
Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [7,2,5] and [10,8], where the largest sum among the two subarrays is only 18.

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

Why This Problem Matters#

LC 410 is a classic hard binary-search-on-answer problem asked by Google and Facebook. It is the direct minimise-maximum counterpart of the Aggressive Cows maximise-minimum problem. The same binary search template (lower-mid, hi = mid on feasibility) applies here.

The problem also has a DP solution in O(n^2 * k), but the binary search approach is strictly better — O(n log(sum - max)) — and is the expected answer at senior-level FAANG interviews.

The Core Insight#

Binary search on the maximum subarray sum m in [max(nums), sum(nums)]. For a given m, greedily count how many subarrays are needed if no subarray can exceed sum m: accumulate elements; when adding the next would exceed m, start a new subarray. If the number of subarrays needed <= k, then m is feasible.

Feasibility is monotone: higher m always requires fewer or equal subarrays. Find the minimum m where feasibility holds.

Visual Dry Run#

nums = [7,2,5,10,8], k = 2, bounds: lo=10 (max), hi=32 (sum)

Solution (Optimal)#

class Solution:
    def splitArray(self, nums: list[int], k: int) -> int:
        def feasible(limit: int) -> bool:
            parts = 1
            current = 0
            for x in nums:
                if current + x > limit:
                    parts += 1
                    current = 0
                current += x
            return parts <= k
 
        lo = max(nums)      # minimum possible: must carry the largest element
        hi = sum(nums)      # maximum possible: carry everything in one subarray
 
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if feasible(mid):
                hi = mid    # feasible: try a smaller limit
            else:
                lo = mid + 1  # not feasible: need a larger limit
 
        return lo

var splitArray = function(nums, k) {
    function feasible(limit) {
        let parts = 1, current = 0;
        for (const x of nums) {
            if (current + x > limit) {
                parts++;
                current = 0;
            }
            current += x;
        }
        return parts <= k;
    }
 
    let lo = Math.max(...nums);
    let hi = nums.reduce((a, b) => a + b, 0);
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (feasible(mid)) hi = mid;
        else lo = mid + 1;
    }
 
    return lo;
};

Time: O(n log(sum - max)) — O(log S) binary search iterations, each O(n) feasibility check Space: O(1) — only counter variables

Common Mistakes#

• Setting lo = 0 — the minimum possible answer must be at least max(nums), or a single element would exceed the limit.
• Setting hi = max(nums) — the maximum possible answer is sum(nums) (put everything in one subarray).
• Initialising parts = 0 instead of parts = 1 — you always start with at least one subarray.
• Not resetting current = 0 when starting a new subarray.
• Confusing this with the maximise-minimum template — this is minimise-maximum, so use lower-mid and hi = mid on success.

Interview Tips#

• State the search bounds clearly before coding: "minimum is max(nums) (can't be less or the largest element overflows), maximum is sum(nums) (everything in one part)."
• The feasibility check is the same greedy as Koko Eating Bananas and Capacity to Ship Packages — mention the connection.
• The DP alternative is O(n^2 k) — valid but binary search is better; mention the trade-off.
• This is the direct counterpart of Aggressive Cows: where that problem maximises the minimum, this minimises the maximum.

Follow-up Questions#

• DP solution: dp[i][j] = minimum largest sum to split nums[0..i] into j parts. O(n^2 * k) time, O(n * k) space.
• LC 875 (Koko Eating Bananas): Identical binary search template. Same feasibility structure.
• LC 1011 (Capacity to Ship Packages): Another minimise-maximum problem with the same template.
• What if k = 1? The answer is sum(nums) — one subarray containing everything.
• What if k = n? Each element is its own subarray, so the answer is max(nums).

Key Takeaways#

• LC 410 is the canonical minimise-maximum binary search on answer problem, asked by Google and Facebook at hard difficulty.
• Search bounds: lo = max(nums) (can't be smaller or the largest single element violates the limit), hi = sum(nums) (all elements in one subarray).
• The feasibility check is a greedy O(n) scan: accumulate sum; when adding the next element would exceed limit, start a new part. Count total parts needed.
• Use lower-mid (lo + hi) // 2 with hi = mid on feasibility and lo = mid + 1 on infeasibility — converges to the minimum feasible limit.
• Structurally identical to LC 875 (Koko), LC 1011 (shipping), and LC 1482 (bouquets) — mastering one teaches all.
• The DP alternative (O(n^2 * k)) is valid but slower; binary search is O(n log S) and is the expected interview answer.
• This is the direct minimise-maximum counterpart of the Aggressive Cows maximise-minimum problem — same template, opposite objective.