p85 — Split Array Largest Sum

Source: LeetCode 410 · Hard · Topics: Binary Search on Answer, DP, Greedy Companies (2024–2025): Google (high), Amazon (high), Meta (medium), Stripe (medium) Loop position: The DP↔binary-search bijection. Two complete solutions; choosing correctly given constraints is the Staff signal.

1. Quick Context

Given non-negative nums and integer k, split nums into k contiguous subarrays so that the maximum subarray sum is minimized. Return that minimum.

Two solutions:

  • DP dp[i][j] = min largest-sum of splitting nums[:i] into j parts. O(n² · k).
  • Binary search on answer: search S ∈ [max(nums), sum(nums)]; feasibility check = “can we partition into ≤ k parts each with sum ≤ S?” Greedy left-to-right. O(n log(sum)).

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/split-array-largest-sum/

STOP. 40-min timer. Try DP first to understand the problem; then derive binary search on answer.

3. Prerequisite Concepts

  • Binary search on a monotone predicate (parametric search).
  • 1D DP with index split.
  • Monotonicity of “feasible to fit in ≤ k parts” as a function of cap S.

4. How to Approach (FRAMEWORK 1–9)

1. Restate: Partition into k contiguous parts; minimize the maximum part-sum.

2. Clarify: Contiguous (yes); non-negative (yes); k ≤ n.

3. Examples: nums=[7,2,5,10,8], k=2 → 18 (split [7,2,5,10] | [8] would be max 24; [7,2,5] | [10,8] is max 18).

5. Brute: Try all C(n-1, k-1) split positions; track min of max. Combinatorial.

6. Target: O(n log(sum(nums))) binary search.

7. Pattern: Binary search on answer with greedy feasibility.

8. Develop: see solution.py.

9. Test: k=1 (= sum); k=n (= max); all zeros; single huge element.

5. Progressive Hints

See hints.md.

6. Deeper Insight

6.1 Why binary search works (monotonicity)

Predicate feasible(S) = “can we partition into ≤ k parts with each sum ≤ S”. This is monotonic in S: if S works, any S’ ≥ S works. The minimum S where feasible(S) = True is the answer.

6.2 Search bounds

  • Lower bound lo = max(nums): any part must contain at least one element, so part-sum ≥ max(nums).
  • Upper bound hi = sum(nums): a single part trivially fits.

6.3 The greedy feasibility check

Greedy from left: start a new part; accumulate while sum ≤ S; when adding next element would exceed S, close part and start new. Count parts. Feasible iff count ≤ k.

Why greedy is optimal for feasibility: if you close a part earlier than needed, the suffix has more to fit → never helps. (Standard exchange argument for “first-fit on a line”.)

6.4 DP formulation

dp[i][j] = min over split point t < i of: max(dp[t][j-1], sum(nums[t:i]))
base: dp[i][1] = prefix_sum[i]

O(n² · k) with prefix sums. Reconstructing actual splits: track argmin t.

6.5 DP vs binary search: when to pick which

  • Binary search when nums are large (sum dominates k), n moderate, only the answer matters. O(n log(sum)).
  • DP when you need the actual partition or k is tiny. O(n²·k).
  • Practical: at the FAANG bar, binary search is the expected answer; DP is the warmup.

6.6 Family: binary-search-on-answer

  • LC 410 Split Array Largest Sum (this).
  • LC 1011 Capacity to Ship Packages in D Days (identical structure).
  • LC 875 Koko Eating Bananas (per-pile feasibility).
  • LC 1482 Min Days to Make m Bouquets (per-day feasibility).
  • LC 1283 Smallest Divisor (per-element ceil-division feasibility).

All share: search a numeric parameter; greedy feasibility check.

7. Anti-Pattern Analysis

  1. Search bounds wrong — lo = 0 lets feasible(0) be tested unnecessarily; lo = max(nums) is tight.
  2. Off-by-one in binary search — use lo < hi with hi = mid on success, lo = mid + 1 on failure; final answer = lo.
  3. Greedy that splits “after exceeding” — must split before exceeding (close current part, start new with this element).
  4. DP without prefix sums — recomputes sums; O(n³·k).
  5. Confuse “≤ k parts” with “= k parts” — feasibility uses ≤ k (fewer parts = larger max, won’t help); but problem requires exactly k, which is fine since any ≤k-feasible can be “split more finely” → still ≤ S.
  6. Try the DP first in a 30-min interview — runs out of time.

8. Skills & Takeaways

  • Binary search on numeric answer with monotone predicate.
  • Greedy first-fit feasibility check.
  • Recognizing when to prefer binary search over DP.

9. When to Move On

  • Solve both ways cold in 30 min.
  • Justify the monotonic predicate.
  • Cite Capacity to Ship Packages and Koko as siblings.

10. Company Context

  • Google: L5/L6; binary-search-on-answer is a fixture.
  • Amazon: L5/L6; load-balancing flavor.
  • Meta: E5; expects you to identify the pattern fast.
  • Stripe: mid+; rate-limiting / capacity problems.

Strong: “Two solutions: O(n log(sum)) binary search on answer with greedy feasibility, and O(n²·k) DP; chose binary search for the constraints; cited the binary-search-on-answer family.”

11. Interviewer’s Lens

SignalJuniorMidSeniorStaff+
Monotone predicateNoneAfter hintCold+ proves monotonicity formally
Bounds[0, sum][max, sum] after test[max, sum] cold+ tight reasoning
Greedy feasibilityOff-by-oneAfter testCold+ proves exchange-argument optimality
FamilyNoneNoneLC 1011+ LC 875/1482/1283 + DP↔BSA tradeoff

12. Level Delta

  • Mid (L4): DP after struggle; binary search after hint.
  • Senior (L5): Both solutions cold; correct bounds and greedy.
  • Staff (L6): + articulates DP↔BSA tradeoff + reconstructs split.
  • Principal (L7+): + parametric-search framework (Megiddo) + connects to scheduling / load balancing LP relaxations + recognizes this as a discrete analog of the continuous max-min partition problem (solvable in O(n) via prefix-sum balancing).

13. Follow-up Q&A

Q1: Return the actual partition? A1: After finding S via binary search, run greedy once more and record cut points.

Q2: Negative numbers allowed? A2: Monotonicity of greedy breaks (adding a negative could let you fit more). Use DP.

Q3: Maximize the minimum part-sum instead? A3: Symmetric binary search; greedy fits “≥ S” parts, count ≥ k means feasible.

Q4: Parts don’t have to be contiguous? A4: NP-hard (multiway number partitioning); LP relaxation or approximations.

Q5: 2D — grid into k rectangles? A5: Becomes NP-hard for general k; the 1D contiguity is what makes it tractable.

14. Solution Walkthrough

See solution.py:

  • split_array_bsa — O(n log(sum)) binary search on answer with greedy feasibility.
  • split_array_dp — O(n²·k) DP.
  • split_array_brute — try all combinations of split points; oracle.

15. Beyond the Problem

Principal code review: “Split Array Largest Sum is the prototype for the binary-search-on-answer pattern, which dominates real-world capacity-planning problems: ship-loading deadlines, autoscaler thresholds, rate-limit configuration, batch-size tuning. The Staff+ recognition is: whenever you need to find the smallest (or largest) numeric value X such that some greedy predicate P(X) holds, and P is monotonic in X, prefer binary search. The cost is log(range) predicate evaluations vs DP’s polynomial in input size — usually a huge win. The deeper move: parametric search (Megiddo) lets you do this even when the bounds aren’t obvious, by running the greedy symbolically on an unknown X and resolving comparisons via a smaller subproblem. Most engineers never reach for this even when it’s perfect — they default to DP because that’s what was drilled. The exam: when you see ‘minimize the maximum of…’ or ‘maximize the minimum of…’, binary-search-on-answer should be your first move.”