DSA sheet · Binary Search · Binary search on answer (min of max)

Split Array Largest Sum

Cut an array into k continuous pieces so that the heaviest piece is as light as possible. The teacher calls this the last question of the binary-search-on-answer pattern, and she says it's Allocate Minimum Pages with a new story: books become numbers and students become pieces. Her video is short and keeps pointing back to that problem, so this page writes out the full reasoning here, so it can be read on its own. She lists all the splits by hand, picks low and high, shows the brute force (try every possible largest sum, TLE), and then binary searches.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · What you must know before starting
• Part A · Brute force: try every largest sum one by one
• Part B · Optimal: binary search on the largest sum
• Part C · Revision page

Part 0 · Before starting

Normal binary search in one paragraph

Binary search needs a sorted line where a yes/no question flips only once. Keep low and high, test mid, drop the half that can't hold the answer, and repeat. About log₂(size) steps.

How to compute mid, and why that form

mid = low + (high - low) // 2

It's the same number as (low + high) // 2. In Java/C++, low + high can overflow the int limit (about 2.1 × 10⁹) when both are large. Here high is a sum that can reach 10³ × 10⁶ = 10⁹, so two such values added together can cross the limit. The subtraction form never overflows. Python integers have no size limit, so in Python this is just a good habit.

The pattern: binary search on the answer

1. Answer range: the smallest and the largest value the answer could possibly be.
2. Yes/no check: "if no piece may have a sum above X, can I cut the array into at most k pieces?"
3. Monotonic: a bigger X never needs more pieces, so the answers go no, no, …, yes, yes. One flip → binary search.

The tell-tale sign: the answer (18 in the example) is a sum, not an element you can find in the array. We search a range of possible sums.

Minimise the maximum vs maximise the minimum

The teacher points out the two directions in one line: when the question says minimise the maximum, the lowest sensible value is a maximum (the biggest element); when it says maximise the minimum, you push the minimum up. And the direction of the search flips with it:

Part A · Brute force: try every largest sum one by one

LeetCode 410

1The question in simple words

You get an array nums and a number k. Cut the array into exactly k pieces. Each piece must be a subarray: a continuous stretch, never empty, and you can't take numbers from different places. For each way of cutting, find the piece with the largest sum. Choose the cutting where that largest sum is smallest, and return it.

Example: nums = [7, 2, 5, 10, 8], k = 2 → answer 18.

2What the constraints tell us

• n from 1 to 1000 (10³). One pass over the array is cheap.
• nums[i] from 0 to 10⁶. Zeros are allowed. The total sum can reach 10³ × 10⁶ = 10⁹.
• k from 1 to min(50, n). k is never more than n, so a valid split always exists (no −1 case). k = 1 is allowed.
• The teacher's warning: two nested loops of 10⁶ and 10³ give 10⁹ steps, which is TLE (over 10⁸). So we'll have to optimise.

3Intuition

Instead of trying all cuts, fix a cap X and ask: "if no piece may sum to more than X, how many pieces do I need?" Walk left to right, keep adding numbers to the current piece, and when the next number would push it over X, start a new piece with that number. If the count is ≤ k, X is possible. Try X from small to big. The first possible X is the answer.

4Building the logic from examples

Step 1: all the ways to cut [7, 2, 5, 10, 8] into 2 pieces

The teacher gets the second sums quickly from the total: 7 + 2 + 5 + 10 + 8 = 32, so the other piece is 32 minus the first piece (32 − 7 = 25, 32 − 9 = 23, …). The largest in each row is 25, 23, 18, 24, and the smallest of those is 18, matching the expected output. "Minimise the largest sum."

Step 2: high = the total sum

k can be 1. Then the whole array is one piece and the answer is the total, 32. With more pieces the largest piece can only shrink. So nothing above the total is ever needed. high = sum(nums).

Step 3: low = the largest element

Looking at the four splits, you might guess the smallest number, 7, or perhaps 8. The teacher shows why that's wrong: imagine the array ended with …, 8, 10. You could put 10 alone and everything else in the other piece, but the piece containing 10 still weighs at least 10. Every number has to go in some piece, and a piece is at least as heavy as its biggest number. So the answer can never be below max(nums) = 10. low = max(nums).

The answer lives on 10 … 32.

Step 4: the check, tried at a few caps

• X = 15: 7 → 9 → 14. Adding 10 makes 24 > 15 → new piece [10]. Adding 8 makes 18 > 15 → new piece [8]. Pieces [7,2,5] [10] [8] = 3 > 2 → no.
• X = 18: [7,2,5] = 14, then 10 + 8 = 18 ≤ 18 fits → [10,8]. 2 pieces → yes.
• X = 17: [7,2,5], then 10 + 8 = 18 > 17 → [10] [8]. 3 pieces → no.

The yes/no line

The check function, piece by piece (same as Allocate Pages)

• count = 1: the first piece is open. current = 0: its running sum.
• For each number: if current + num <= max_sum → it joins the current piece.
• Else → count += 1, and the new piece starts with this number: current = num. (Resetting to 0 would drop the number.)
• Return count <= k.

The brute-force loop

The teacher's version: set answer = high first. Loop X from low to high. On the first X where the check says yes, save it and break (or return it right away). Going upward, the first yes is the smallest. If nothing broke the loop, answer is still the total sum, which is always valid.

5Approach steps

1. low = max(nums), high = sum(nums), answer = high.
2. For X = low … high: if canSplit(nums, k, X) → answer = X, break.
3. Return answer.

6Code (Python)

class Solution:
    def splitArray(self, nums, k):
        low = max(nums)
        high = sum(nums)
        answer = high
        for max_sum in range(low, high + 1):
            if self.canSplit(nums, k, max_sum):
                answer = max_sum        # first yes = smallest largest-sum
                break
        return answer

    def canSplit(self, nums, k, max_sum):
        count = 1
        current = 0
        for num in nums:
            if current + num <= max_sum:
                current += num          # stays in this piece
            else:
                count += 1              # open a new piece...
                current = num           # ...starting with this number
        return count <= k

7Code line by line

8Dry run (hand table)

nums = [7, 2, 5, 10, 8], k = 2. low = 10, high = 32.

9 caps tried (10 through 18). Return 18 ✓.

9Complexity & remember

• Time O(n · (sum − max)). The teacher's estimate: the outer loop goes up to about 10⁶ (the biggest value) and the inner loop is 10³ (the length), so 10⁹ → TLE.
• Space O(1).

Part B · Optimal: binary search on the largest sum

1The question

Same problem, same range, same canSplit. The teacher's only change: replace the for loop with a binary-search while loop.

2Constraints

Same. The cap range is at most about 10⁹ values wide, so about 30 checks of 10³ steps each.

3Intuition

The caps 10 … 32 form a sorted line that reads N … N Y … Y, and we want the first Y (we're minimising).

• check(mid) yes → save mid and look for a smaller cap on the left: high = mid - 1.
• check(mid) no → mid is too tight, and so is everything smaller → go right: low = mid + 1.

4Building the logic

The range shrinking

5Approach steps

1. low = max(nums), high = sum(nums), answer = high.
2. While low <= high: mid = low + (high - low) // 2.
3. canSplit(mid) → answer = mid, high = mid - 1. Else → low = mid + 1.
4. Return answer.

6Code (Python)

class Solution:
    def splitArray(self, nums, k):
        low = max(nums)
        high = sum(nums)
        answer = high
        while low <= high:
            mid = low + (high - low) // 2      # candidate largest sum
            if self.canSplit(nums, k, mid):
                answer = mid                   # enough: save it...
                high = mid - 1                 # ...and try a smaller cap
            else:
                low = mid + 1                  # too many pieces: bigger cap
        return answer

    def canSplit(self, nums, k, max_sum):
        count = 1
        current = 0
        for num in nums:
            if current + num <= max_sum:
                current += num
            else:
                count += 1
                current = num
        return count <= k

7Code line by line

8Dry run (hand table)

nums = [7, 2, 5, 10, 8], k = 2.

9Complexity & remember

• Time O(n · log(sum − max)). She writes it as log(10⁶) × 10³. With the full range (sum up to 10⁹) it's about 30 × 10³ = 3 × 10⁴ steps. Very fast.
• Space O(1).

Part C · Revision page

s = Solution()
print(s.splitArray([7, 2, 5, 10, 8], 2))     # 18
print(s.splitArray([1, 2, 3, 4, 5], 2))      # 9
print(s.splitArray([1, 4, 4], 3))            # 4
print(s.splitArray([0, 0, 0], 1))            # 0

Based on this video: Split Array Largest Sum | Binary Search on Answer