LeetCode 410 — Split Array Largest Sum

What does it solve?

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

Example: nums=[7,2,5,10,8], k=2 → best split is [7,2,5] | [10,8] → max sum = 18.

Binary Search + Greedy

// Search space: [max(nums), sum(nums)]
lo = max(nums), hi = sum(nums)
while lo ≤ hi:
  mid = (lo + hi) / 2
  // Can we fit in ≤ k subarrays?
  if canSplit(nums, k, mid):
    hi = mid − 1 // try smaller
  else: lo = mid + 1

💡 Key insight: Binary search over the answer value (the allowed max sum), not the array indices. For any candidate limit mid, greedily check: can we split the array into ≤ k subarrays where no subarray exceeds mid? If yes → try lower. If no → try higher. The search space shrinks from O(sum) to O(log·sum).

Complexity

Time complexity

O(n·log S)

O(log S) binary search iterations × O(n) greedy check per iteration. S = sum(nums).

Space complexity

O(1)

Only a few integer variables — no extra arrays needed.

Examples & edge cases

Live animation — Binary Search + Greedy

Current mid (candidate) Valid split (answer updated) Too small (need more room) Active subarray in greedy check

Binary search range

Array — greedy partition with limit = mid

Greedy check — running sum per partition

Step — of —

lo (search low)

—

lower bound

mid (candidate)

—

current guess

hi (search high)

—

upper bound

Best answer

—

min largest sum

Select an example and press Play to begin.

✓ Answer found!

Speed Medium

Step-by-step table

Step	lo	mid	hi	Partitions needed	vs k	Action	Answer

C++ implementation

split_array.cpp

#include <bits/stdc++.h>
using namespace std;

// Greedy check: can we split nums into ≤ k parts, each sum ≤ limit?
bool canSplit(vector<int>& nums, int k, long long limit) {
    int parts = 1;
    long long curSum = 0;
    for (int x : nums) {
        if (curSum + x > limit) {
            parts++;          // start a new partition
            curSum = x;
            if (parts > k) return false;
        } else {
            curSum += x;
        }
    }
    return true;
}

int splitArray(vector<int>& nums, int k) {
    long long lo = *max_element(nums.begin(), nums.end());
    long long hi = accumulate(nums.begin(), nums.end(), 0LL);
    long long ans = hi;

    while (lo <= hi) {
        long long mid = lo + (hi - lo) / 2;
        if (canSplit(nums, k, mid)) {
            ans = mid;        // valid — try smaller limit
            hi = mid - 1;
        } else {
            lo = mid + 1;    // too tight — allow bigger limit
        }
    }
    return (int)ans;
}

int main() {
    vector<int> nums = {7, 2, 5, 10, 8};
    int k = 2;
    cout << splitArray(nums, k) << "\n";  // 18
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars