Pattern this teaches:Binary Search on Answer
Split Array Largest Sum
A hard Binary Search interview guide. Task statement, worked examples, intuition, and step-by-step solutions.
- Topic
- Binary Search
- Sheets
- 1
- Core for
- 7 roles
The problem
Given an array of positive integers and an integer m, split the array into m non-empty contiguous subarrays. Minimize the largest sum among these subarrays and return that value.
Example 1
- Input
- nums = [4,9,3,6,10], m = 2
- Output
- 16
- Why
- Split as [4,9,3] and [6,10]: the larger sum is 16, the smallest possible.
Example 2
- Input
- nums = [2,4,6,8,10], m = 3
- Output
- 12
- Why
- Split as [2,4,6], [8] and [10]: no split does better than a largest sum of 12.
Constraints
- 1 <= nums.length <= 1000
- 1 <= nums[i] <= 10^6
- 1 <= m <= min(50, nums.length)
How to think about it
Updated 2026-09-29The problem asks to minimize a maximum subarray sum. Rather than deciding where to cut subarrays, guess the ceiling sum S. If an allowance of S permits partitioning nums into m or fewer contiguous subarrays, any allowance greater than S also does, yielding a clean binary search on S.
Approaches, worst first
Dynamic programming with prefix sums
time O(m * n^2) · space O(m * n)
Let dp[i][j] be the minimum largest subarray sum splitting prefix i into j subarrays. Transitions iterate over all possible previous split positions. Correct but expensive in both computation and memory.
Binary search on max subarray sumWrite this one
time O(n log(sum(nums))) · space O(1)
Search target sum between max(nums) and sum(nums). Greedily absorb elements into the current subarray until adding another exceeds mid, then spawn a new subarray. If count of subarrays <= m, narrow upper bound; otherwise increase lower bound.
Where people lose marks · 3
- Setting the search floor lower than max(nums) produces impossible test targets where a single element cannot fit into any subarray.
- Greedily starting the subarray count at 0 instead of 1 underestimates required subarrays by one because the initial running segment is not counted.
- Using 32-bit signed integer for sum(nums) risk overflow when summing up to 1000 numbers of value 10^6; use 64-bit integers.
The theory behind it
Binary Search — the ground this problem stands on. All Binary Search problems
What Binary Search is
Binary search is the guessing strategy used when searching a thick telephone directory or guessing a secret number between one and a hundred. Rather than inspecting names one by one from the first page, the search opens straight to the middle page. If the target precedes that middle entry, the entire back half is discarded; if it follows, the front half is eliminated. Repeating this halved split finds the item with remarkable speed.
When to reach for it
Reach for binary search when queries target sorted collections, rotated sorted arrays, or monotonic answer spaces. Strong hints include logarithmic time constraints like O(log n) or search ranges exceeding one billion where stepping one value at a time times out. It also applies when validating whether a guessed solution is possible via a monotonic boolean check, known as binary search on answer.
How the pattern works
Define the search territory with two inclusive pointers, low and high. Compute the midpoint using low plus half the difference to high, avoiding integer overflow. Formulate an exact boolean condition that divides the range into true and false halves. Decide whether the boundary condition includes the midpoint or shifts strictly past it. The loop invariant states that the sought target, if it exists, remains trapped inside the interval throughout every iteration.
More Binary Search problems
Target Roles
Core requirement for 7 roles:
Track in your role's order
Pick your target role and all 370 problems resequence to what that interview actually asks.
Start freeProblem set and role mapping as of .