Example 2 — Binary Search on Answer

We now move to a more advanced pattern.

This is where many candidates fail.

They see binary search only when the array is sorted.

Senior candidates recognize:

You can binary search the answer space, not just the array.

---

Problem (Classic)

Given an array nums and an integer k, split the array into k non-empty subarrays such that the largest sum among these subarrays is minimized.
Return the minimized largest sum.

---

Step 1 — Identify Input Type

Input:

• Array
• Integer k

Common array patterns:

• Two pointers
• Sliding window
• Prefix sum
• DP
• Binary search

But nothing says substring or contiguous window optimization directly.

---

Step 2 — Look for Keywords

Important words:

• Minimize
• Largest sum
• Split into k parts

This is critical.

Whenever you see:

• Minimize the maximum
• Maximize the minimum
• Smallest possible value such that condition holds

Think:

Monotonic answer space → Binary Search on Answer

---

Step 3 — Ask This Question

If I guess a value X,
can I check whether it’s feasible?

That is the key.

Let’s define:

Let X = maximum allowed subarray sum.

Question: Can we split the array into ≤ k parts such that no part has sum > X?

If YES → X is feasible.
If NO → X is too small.

This is a monotonic property:

• If X works, any value greater than X also works.
• If X fails, any smaller value will also fail.

That is monotonicity.

Binary search requires monotonic behavior.

---

Pattern Identified

Binary Search on Answer.

Template:

1. Define search space.
2. Define feasibility function.
3. Binary search until minimum valid answer found.

---

Step 4 — Define Search Range

Minimum possible largest sum:

• max element in array.

Maximum possible largest sum:

• total sum of array.

So:

low = max(nums)
high = sum(nums)

---

Clean Java Implementation

public int minimizeLargestSubarraySum(final int[] numbers, final int k) {

    if (numbers == null || numbers.length == 0) {
        throw new IllegalArgumentException("Input array cannot be null or empty");
    }

    int lowerBound = 0;
    int upperBound = 0;

    for (int value : numbers) {
        lowerBound = Math.max(lowerBound, value);
        upperBound += value;
    }

    while (lowerBound < upperBound) {

        int mid = lowerBound + (upperBound - lowerBound) / 2;

        if (canSplit(numbers, k, mid)) {
            upperBound = mid;
        } else {
            lowerBound = mid + 1;
        }
    }

    return lowerBound;
}

private boolean canSplit(final int[] numbers, final int k, final int maxAllowedSum) {

    int requiredSubarrays = 1;
    int currentSum = 0;

    for (int value : numbers) {

        if (currentSum + value > maxAllowedSum) {
            requiredSubarrays++;
            currentSum = value;
        } else {
            currentSum += value;
        }
    }

    return requiredSubarrays <= k;
}

---

Complexity

Time Complexity: O(n log(sum))

Space Complexity: O(1)

---

Why This Pattern Works

Because:

• We are optimizing an answer.
• The answer lies in a numeric range.
• There exists a monotonic feasibility check.
• We can validate in O(n).

This is classic binary search on answer.

---

Recognition Signals for This Pattern

If you see:

• Minimize maximum
• Maximize minimum
• Capacity problems
• Allocation problems
• “Smallest X such that…”
• Range of possible answers is numeric

Immediately ask:

Can I binary search the answer?

---

Common Interview Problems Using This Pattern

• Split Array Largest Sum
• Capacity to Ship Packages Within D Days
• Koko Eating Bananas
• Aggressive Cows
• Allocate Books

All use the same pattern.

---

Recognition Summary

When you see:

Optimization over a numeric answer

• Feasibility check possible
• Monotonic property

→ Binary Search on Answer.