410. Split Array Largest Sum

Quick Identifier

Topic: binary-search
Pattern: Binary Search on answer (feasibility check)
Difficulty: Hard
Companies: Google, Amazon, Bloomberg, Adobe
Frequency: High
LeetCode: 410

Quick Sights

Time Complexity: O(n · log(sum − max)) from the optimal approach.
Space Complexity: cap from the optimal approach.
Core Mechanism: Given non-negative array numbers and integer numSubarrays, split numbers into exactly numSubarrays contiguous parts to minimize the largest sum among those parts. Return that minimized largest sum.

Given non-negative array numbers and integer numSubarrays, split numbers into exactly numSubarrays contiguous parts to minimize the largest sum among those parts. Return that minimized largest sum.

The key is to state the invariant before coding: what part of the input is already settled, what state is still unresolved, and what single operation makes progress without losing correctness.

Recognition cues:

“Minimize maximum” over contiguous chunks
Answer is monotone: if cap maxSum works, any larger cap works → BS on answer
Greedy packing validates a candidate cap in O(n)

Study Pattern (SDE3+)

0-3 min: restate I/O and brittle edges aloud, then verbalize two approaches with time/space before you touch the keyboard.
Implementation pass: one-line invariant above the tight loop; state what progress you make each iteration.
5 min extension: pick one constraint twist (immutable input, stream, bounded memory, parallel readers) and explain what in your solution breaks without a refactor.

Diagram

This diagram shows the algorithm movement for this problem family.

Loading diagram…

Approaches

Brute force — enumerate partitions into exactly numSubarrays contiguous chunks — exponential / pseudopolynomial in naive enumeration.
Acceptable — DP: dp[count][index] = feasibility or minimal pain — O(n² · numSubarrays) time; viable when numSubarrays is tiny or correctness proof is clearer than monotone feasibility.
Optimal — search the minimized largest chunk sum: monotone feasibility “can we pack into ≤ numSubarrays segments with segment sums ≤ cap?” via greedy linear scan — O(n · log(sum − max)) binary search on cap.

Optimal Solution

Go

func splitArray(numbers []int, numSubarrays int) int {
	sumAll := 0
	maxValue := 0
	for _, value := range numbers {
		sumAll += value
		if value > maxValue {
			maxValue = value
		}
	}
	low, high := maxValue, sumAll
	for low < high {
		mid := low + (high-low)/2
		if canSplitWithCap(numbers, numSubarrays, mid) {
			high = mid
		} else {
			low = mid + 1
		}
	}
	return low
}

func canSplitWithCap(numbers []int, numSubarrays int, maxSegmentSum int) bool {
	segmentsUsed := 1
	currentSum := 0
	for _, value := range numbers {
		if currentSum+value > maxSegmentSum {
			segmentsUsed++
			currentSum = value
			if segmentsUsed > numSubarrays {
				return false
			}
		} else {
			currentSum += value
		}
	}
	return true
}

JavaScript

function splitArray(numbers, numSubarrays) {
	let sumAll = 0;
	let maxValue = 0;
	for (const value of numbers) {
		sumAll += value;
		if (value > maxValue) {
			maxValue = value;
		}
	}
	let low = maxValue;
	let high = sumAll;
	while (low < high) {
		const mid = Math.floor(low + (high - low) / 2);
		if (canSplitWithCap(numbers, numSubarrays, mid)) {
			high = mid;
		} else {
			low = mid + 1;
		}
	}
	return low;
}

function canSplitWithCap(numbers, numSubarrays, maxSegmentSum) {
	let segmentsUsed = 1;
	let currentSum = 0;
	for (const value of numbers) {
		if (currentSum + value > maxSegmentSum) {
			segmentsUsed++;
			currentSum = value;
			if (segmentsUsed > numSubarrays) {
				return false;
			}
		} else {
			currentSum += value;
		}
	}
	return true;
}

Walkthrough

numbers = [7,2,5,10,8], numSubarrays = 2

If cap 18: greedy gives [7,2,5] sum 14 and [10,8] sum 18 → 2 segments OK.
Binary search tightens low bound until minimal feasible cap.

Invariant: canSplitWithCap is monotone in maxSegmentSum.

Edge Cases

numSubarrays == len(numbers) → answer is max(numbers)
numSubarrays == 1 → answer is sum(numbers)
Zeros in array — still contiguous greedy works

Pitfalls

Search space upper bound must be sum, lower max — not 0..sum
Greedy must append until exceeding cap, then start new segment with current element
Integer overflow in sum on pathological inputs (language-dependent)

Variants

Minimize largest length (not sum) — feasibility changes to segment count by length.
Weighted split costs — DP often needed; BS may fail monotonicity.
Online stream — must buffer or approximate.

Mind-Map Tags

#binary-search-on-answer #minimize-maximum #greedy-feasibility #contiguous-split #hard-classic