410. Split Array Largest Sum

At a Glance

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

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.

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)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

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