Split Array Largest Sum — Binary Search on Answer

What does it solve?

Split nums into k non-empty contiguous subarrays so the largest subarray sum is as small as possible. This is exactly the Book Allocation problem with a different story: books → numbers, students → subarrays.

Key insight: binary search on the answer (the max allowed subarray sum). For a candidate limit mid, greedily count how many subarrays you'd need if no subarray may exceed mid. If that count ≤ k, the limit is feasible, try smaller; otherwise go bigger. Range is [max(nums), sum(nums)] → O(N log S).

The core idea

// binary search on answer
lo = max(nums), hi = sum(nums)
while lo <= hi:
  mid = (lo+hi)/2
  if pieces(mid) <= k:
    ans = mid; hi = mid-1
  else: lo = mid+1

Complexity

Time complexity

O(N log S)

Binary search runs O(log S) times over the sum range; each feasibility check is an O(N) greedy scan.

Space complexity

O(1)

A handful of counters. No DP table (the DP formulation is O(N²k) and much slower).

Examples & edge cases

Live animation — binary search on the answer

lo hi mid (testing) feasible → record too many pieces

Search space — [lo … hi]

lo—

mid—

hi—

best answer—

feasible?—

nums (values)— testing mid = —

Greedy split for mid = —

lo = — hi = — mid = — ans = —

Step — of —

lo (lower bound)

—

max single num

hi (upper bound)

—

sum of all

mid (candidate)

—

Best answer

—

Select an example and press Play to start.

✓ Answer: —

SpeedMedium

Step-by-step table

Step	Phase	lo	hi	mid	pieces	Feasible?	Action	Best ans

C++ implementation

split_array_largest_sum.cpp

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

// How many pieces if no subarray may exceed 'limit'?
int pieces(vector<int>& a, int limit) {
    int cnt = 1, cur = 0;
    for (int x : a) {
        if (cur + x > limit) { cnt++; cur = x; } // start a new piece
        else cur += x;
    }
    return cnt;
}

int splitArray(vector<int>& a, int k) {
    int lo = *max_element(a.begin(), a.end());
    int hi = accumulate(a.begin(), a.end(), 0);
    int ans = hi;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / 2;
        if (pieces(a, mid) <= k) {
            ans = mid;   // feasible — try a smaller max
            hi = mid - 1;
        } else {
            lo = mid + 1; // too many pieces — allow bigger max
        }
    }
    return ans;
}

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

My Notes

📝Notes✅

▼

●Start typing to save...0 chars

Practice this problem