Split Array Largest Sum [Hard] — Binary Search on Answer + DP

Problem Statement#

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

Example 1

Input:  nums = [7, 2, 5, 10, 8],  k = 2
Output: 18
Explanation: Split as [7,2,5] | [10,8]  → max(14, 18) = 18
             Split as [7,2,5,10] | [8] → max(24,  8) = 24
             Best possible: 18

Example 2

Input:  nums = [1, 2, 3, 4, 5],  k = 2
Output: 9
Explanation: Split as [1,2,3,4] | [5] → max(10, 5) = 10
             Split as [1,2,3] | [4,5] → max(6,  9) = 9   ← minimum

Constraints

• 1 <= nums.length <= 1000
• 0 <= nums[i] <= 10^6
• 1 <= k <= min(50, nums.length)

Why This Problem Matters#

LeetCode 410 is one of the canonical examples of a technique called "binary search on the answer" — a mental model that unlocks an entire family of hard problems. Once you see it here, you will recognise it instantly in:

• Koko Eating Bananas (LC 875)
• Capacity To Ship Packages (LC 1011)
• Minimum Number of Days to Make m Bouquets (LC 1482)
• Find the Smallest Divisor (LC 1283)
• Painter's Partition Problem (a classic Google/Amazon on-site question)

The reason this problem is rated Hard is not because the code is long — the binary search solution is around 15 lines. It is hard because the insight that lets you crack it is non-obvious: you search over the answer space, not the input array. Every candidate at a Google or Amazon interview who solves this problem cleanly is demonstrating that they think about search in a fundamentally more flexible way than the majority of candidates.

Beyond the interview room, the pattern models real scheduling and load-balancing problems: given k workers and a list of tasks, how do you assign tasks to workers to minimise the maximum workload? The mathematics is identical to this problem.

The Binary Search on Answer Insight#

Most developers first reach for binary search when they see a sorted array and need to find an element. That is binary search on the input. This problem requires something deeper.

What are we actually searching for?#

We want the smallest possible value X such that it is feasible to split nums into at most k subarrays where every subarray sum is <= X.

Notice that X — the answer — lives in a well-defined range:

• Lower bound: max(nums). Even if we put each element into its own subarray, the largest subarray must contain the largest element. So the answer can never be smaller than max(nums).
• Upper bound: sum(nums). If we put everything into one subarray (k = 1), the sum of that single subarray is sum(nums). The answer can never exceed this.

So the answer lies somewhere in [max(nums), sum(nums)]. That range can be enormous (up to 10^9 with the given constraints), but it is monotone: if X is a feasible limit, then X + 1 is also feasible. This monotonicity is the exact property that makes binary search applicable.

We binary search for the smallest feasible X:

• If the midpoint mid is feasible → the real answer might be mid or something smaller, so we try the left half.
• If mid is not feasible → the answer must be larger, so we try the right half.

This cuts a search over a billion possible values down to roughly 30 iterations.

The Greedy Feasibility Check#

For binary search to work we need a fast way to answer the question: "Can we split nums into at most k subarrays where every subarray sum is <= limit?"

The answer is a simple greedy left-to-right scan:

1. Start with one subarray. Keep a running sum.
2. Add the next element. If the running sum exceeds limit, we must start a new subarray — increment the subarray count and reset the running sum to the current element.
3. If at any point we need more than k subarrays, the limit is not feasible.

Why is greedy correct here? Because we are processing left to right and have no flexibility in the order of elements (subarrays must be contiguous). Given a fixed limit, the greedy approach of extending the current subarray as far as possible before splitting always uses the fewest possible subarrays. If even the greedy minimum number of subarrays exceeds k, no other strategy can do better.

Greedy check for nums=[7,2,5,10,8], limit=18, k=2:
 
  cur=0, groups=1
  add 7  → cur=7   (7  <= 18, ok)
  add 2  → cur=9   (9  <= 18, ok)
  add 5  → cur=14  (14 <= 18, ok)
  add 10 → cur=24  (24 >  18, split!) groups=2, cur=10
  add 8  → cur=18  (18 <= 18, ok)
 
  groups=2 <= k=2  → FEASIBLE ✓

Visual Dry Run#

Let us trace the full binary search for nums = [7, 2, 5, 10, 8], k = 2.

max(nums) = 10,  sum(nums) = 32
lo = 10,  hi = 32

Iteration 1

mid = (10 + 32) // 2 = 21
 
Greedy check with limit=21:
  cur=0, groups=1
  7  → cur=7
  2  → cur=9
  5  → cur=14
  10 → cur=24 > 21 → split, groups=2, cur=10
  8  → cur=18
 
groups=2 <= 2  → FEASIBLE
hi = mid = 21

State: lo=10, hi=21

Iteration 2

mid = (10 + 21) // 2 = 15
 
Greedy check with limit=15:
  cur=0, groups=1
  7  → cur=7
  2  → cur=9
  5  → cur=14
  10 → cur=24 > 15 → split, groups=2, cur=10
  8  → cur=18 > 15 → split, groups=3, cur=8
 
groups=3 > 2  → NOT FEASIBLE
lo = mid + 1 = 16

State: lo=16, hi=21

Iteration 3

mid = (16 + 21) // 2 = 18
 
Greedy check with limit=18:
  cur=0, groups=1
  7  → cur=7
  2  → cur=9
  5  → cur=14
  10 → cur=24 > 18 → split, groups=2, cur=10
  8  → cur=18
 
groups=2 <= 2  → FEASIBLE
hi = mid = 18

State: lo=16, hi=18

Iteration 4

mid = (16 + 18) // 2 = 17
 
Greedy check with limit=17:
  cur=0, groups=1
  7  → cur=7
  2  → cur=9
  5  → cur=14
  10 → cur=24 > 17 → split, groups=2, cur=10
  8  → cur=18 > 17 → split, groups=3, cur=8
 
groups=3 > 2  → NOT FEASIBLE
lo = mid + 1 = 18

State: lo=18, hi=18

Loop ends: lo == hi == 18. Answer is 18.

The binary search ran 4 iterations over a range of 22 values, and each iteration did a single O(n) pass. That is the power of this technique.

Common Mistakes#

1. Setting the binary search bounds wrong#

A common error is setting lo = 0 or lo = 1. If any element is larger than your lower bound, your greedy check will immediately split on every element and produce incorrect subarray counts. Always set lo = max(nums).

Similarly, some people set hi = sum(nums) - 1 thinking they can save one iteration. This can cause the loop to miss the correct answer when k = 1. Keep hi = sum(nums).

2. Off-by-one in the binary search template#

There are two classic binary search templates. For "find the leftmost feasible value" you need:

while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid):
        hi = mid        # answer could be mid or smaller
    else:
        lo = mid + 1    # mid is too small, answer is strictly larger
return lo

Using lo = mid instead of lo = mid + 1 in the infeasible branch causes an infinite loop when lo + 1 == hi. This is one of the most common sources of TLE on binary search problems.

3. Forgetting that subarrays must be contiguous#

The problem requires contiguous subarrays. You cannot rearrange elements. A greedy check that sorts elements or picks the smallest is completely wrong. The scan must proceed left to right in the original order.

4. Initialising groups = 0 in the feasibility check#

The greedy scan starts with one group already open. If you initialise groups = 0 and only increment on a split, your count is always off by one, causing the function to accept limits that are actually too small.

5. Using integer overflow-prone bounds in JavaScript#

In JavaScript, Math.max(...nums) throws a stack overflow for very large arrays because it spreads the entire array onto the call stack. Use Math.max.apply(null, nums) or reduce: nums.reduce((a, b) => Math.max(a, b), 0).

Solutions#

Approach 1 — Dynamic Programming (O(n^2 * k))#

This approach builds up the answer from smaller subproblems. dp[j][i] stores the minimum possible largest subarray sum when splitting the first i elements of nums into exactly j subarrays.

The recurrence is: to split i elements into j groups, try every possible last split point p and take the minimum over all choices of the maximum of dp[j-1][p] and the sum of elements from p+1 to i.

This is correct but runs in O(n^2 * k) time, which times out for large inputs. It is worth knowing because interviewers sometimes ask you to derive the binary search solution starting from DP.

Python — DP

def splitArray(nums: list[int], k: int) -> int:
    n = len(nums)
 
    # prefix[i] = sum of nums[0..i-1], so sum(nums[l..r]) = prefix[r+1] - prefix[l]
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
 
    # dp[j][i] = min largest sum splitting first i elements into j groups
    # Initialise with infinity; we will fill it in bottom-up
    INF = float('inf')
    dp = [[INF] * (n + 1) for _ in range(k + 1)]
 
    # Base case: 1 group — the only option is the whole prefix, so the
    # "largest sum" is just the prefix sum itself
    for i in range(1, n + 1):
        dp[1][i] = prefix[i]
 
    # Fill for j groups from 2 up to k
    for j in range(2, k + 1):
        # We need at least j elements to form j groups
        for i in range(j, n + 1):
            # Try every possible last split point p
            # The last group covers nums[p..i-1]
            for p in range(j - 1, i):
                # Sum of last group: prefix[i] - prefix[p]
                last_group_sum = prefix[i] - prefix[p]
                # The cost of this split is the max of left part and last group
                cost = max(dp[j - 1][p], last_group_sum)
                # Keep the minimum over all split points
                dp[j][i] = min(dp[j][i], cost)
 
    # Answer: split all n elements into exactly k groups
    return dp[k][n]

JavaScript — DP

function splitArray(nums, k) {
  const n = nums.length;
 
  // Build prefix sum array for O(1) range sum queries
  const prefix = new Array(n + 1).fill(0);
  for (let i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + nums[i];
  }
 
  const INF = Infinity;
 
  // dp[j][i] = min largest subarray sum splitting first i elements into j parts
  // Allocate a (k+1) x (n+1) table filled with Infinity
  const dp = Array.from({ length: k + 1 }, () => new Array(n + 1).fill(INF));
 
  // Base case: one group — cost equals the sum of all i elements
  for (let i = 1; i <= n; i++) {
    dp[1][i] = prefix[i];
  }
 
  // Build up the table for 2..k groups
  for (let j = 2; j <= k; j++) {
    // Need at least j elements to create j non-empty groups
    for (let i = j; i <= n; i++) {
      // Try every last split point p; last group is nums[p..i-1]
      for (let p = j - 1; p < i; p++) {
        const lastGroupSum = prefix[i] - prefix[p];
        // Cost: worst of the optimal left split and this last group
        const cost = Math.max(dp[j - 1][p], lastGroupSum);
        // We want the minimum such cost
        if (cost < dp[j][i]) {
          dp[j][i] = cost;
        }
      }
    }
  }
 
  // Return the answer for all n elements split into k groups
  return dp[k][n];
}

Approach 2 — Binary Search on Answer (O(n log S))#

This is the optimal solution. We binary search over the range [max(nums), sum(nums)] and for each candidate limit run the greedy feasibility check in O(n).

Python — Binary Search

def splitArray(nums: list[int], k: int) -> int:
 
    def feasible(limit: int) -> bool:
        """
        Greedy check: can we split nums into at most k subarrays
        where every subarray sum <= limit?
        """
        groups = 1   # We always start with at least one open group
        current = 0  # Running sum of the current group
 
        for num in nums:
            # Adding this number would exceed the limit for this group
            if current + num > limit:
                groups += 1   # Open a new group
                current = 0   # Reset running sum
 
                # Early exit: more groups than allowed is immediately infeasible
                if groups > k:
                    return False
 
            current += num   # Add the number to the (possibly new) group
 
        return True   # Managed to fit everything into k or fewer groups
 
    # The answer is somewhere in [max(nums), sum(nums)]
    lo = max(nums)    # Smallest possible: must accommodate the largest element
    hi = sum(nums)    # Largest possible: one big group containing everything
 
    # Standard "leftmost feasible" binary search template
    while lo < hi:
        mid = (lo + hi) // 2
 
        if feasible(mid):
            # mid works — try to find something smaller
            hi = mid
        else:
            # mid is too tight — the answer must be strictly larger
            lo = mid + 1
 
    # lo == hi at this point; this is the smallest feasible limit
    return lo

JavaScript — Binary Search

function splitArray(nums, k) {
 
  /**
   * Greedy feasibility check.
   * Returns true if we can split nums into at most k subarrays
   * where every subarray sum is <= limit.
   */
  function feasible(limit) {
    let groups = 1;   // Start with one open group
    let current = 0;  // Running sum of the current group
 
    for (const num of nums) {
      // This element would push the current group over the limit
      if (current + num > limit) {
        groups++;       // Start a fresh group
        current = 0;    // Reset the running sum
 
        // If we have already used more groups than allowed, bail out early
        if (groups > k) return false;
      }
 
      current += num;   // Accumulate into the current (possibly new) group
    }
 
    return true;   // Fit everything into k groups or fewer
  }
 
  // Binary search over the answer space
  // lo: must be at least the largest single element (can't split an element)
  // hi: at most the total sum (k=1 case, one giant group)
  let lo = nums.reduce((a, b) => Math.max(a, b), 0);
  let hi = nums.reduce((a, b) => a + b, 0);
 
  // "Leftmost true" binary search template
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
 
    if (feasible(mid)) {
      hi = mid;       // mid is feasible — try to go lower
    } else {
      lo = mid + 1;   // mid is too tight — go higher
    }
  }
 
  // lo === hi: the smallest feasible limit
  return lo;
}

Complexity Analysis#

For the binary search approach, the outer loop runs at most log(sum - max) times — roughly 30 iterations in the worst case. Each iteration does a single O(n) greedy scan. The overall work is therefore O(n * 30) = O(n log S), which handles n = 1000 trivially and scales to n = 10^5 or beyond.

The DP approach uses O(n * k) space for the table and O(n) additional space for the prefix sum array.

Follow-up Questions#

These problems use the identical binary search on answer + greedy feasibility template. If you can solve LC 410, you can solve all of these.

LC 1011 — Capacity To Ship Packages Within D Days#

Given weights of packages and a number of days D, find the minimum ship capacity to ship all packages within D days. Packages must be shipped in order (contiguous, just like subarrays). The greedy check is character-for-character the same as LC 410 — just replace "k subarrays" with "D days".

LC 875 — Koko Eating Bananas#

Koko can eat at most k bananas per hour. Given piles of bananas, find the minimum k such that she finishes all piles within h hours. The answer space is [1, max(piles)]. The feasibility check: for each pile, she takes ceil(pile / k) hours. Sum those up and compare to h. Different surface problem, identical structure.

LC 1283 — Find the Smallest Divisor Given a Threshold#

Given an array of integers and a threshold, find the smallest positive integer divisor such that the sum of ceil(nums[i] / divisor) for all i is <= threshold. Again: binary search on divisor, O(n) feasibility check.

LC 1482 — Minimum Number of Days to Make m Bouquets#

Given bloomDay arrays and parameters m (bouquets) and k (flowers per bouquet), find the minimum number of days. Binary search on the day, greedy check whether enough contiguous bloomed flowers exist.

The unifying insight: whenever a problem asks for the minimum X such that some condition holds, and that condition is monotone (once X is large enough for the condition to hold, all larger values also satisfy it), binary search on X with a greedy checker is likely the right approach.

This Pattern Solves#

Binary search on answer applies whenever:

1. The answer lives in a bounded, integer range.
2. The feasibility function is monotone: if limit X works, then X + 1 also works (or vice versa — for maximisation problems you flip the direction).
3. You can check feasibility for a given X in O(n) or O(n log n) — much faster than the O(answer range) naive search.

Common triggers in problem statements:

• "Minimise the maximum ..." — binary search for the smallest feasible maximum.
• "Maximise the minimum ..." — binary search for the largest feasible minimum.
• "Find the minimum capacity / speed / divisor ..." — same idea.
• "Within D days / k groups / m workers ..." — check feasibility greedily.

When you see these phrases, immediately ask yourself: "Can I binary search on the answer and write a greedy check?" More often than not, the answer is yes.

Key Takeaways#

• Binary search on the answer (not the array): the search space is [max(nums), sum(nums)] — the minimum possible subarray max and the maximum possible subarray max.
• The feasibility check is a greedy left-to-right scan: greedily extend each subarray until adding the next element would exceed mid, then start a new subarray. If the total groups needed is <= k, mid is feasible.
• The binary search template: lo = max(nums), hi = sum(nums), if feasible(mid): hi = mid, else: lo = mid + 1, return lo.
• lo = max(nums) is critical — any limit smaller than the largest single element is always infeasible since that element must be in some subarray.
• O(n log S) time where S = sum(nums); O(1) space for the greedy check.
• The same binary-search-on-answer + greedy-feasibility pattern solves: Koko Eating Bananas (LC 875), Capacity to Ship Packages (LC 1011), Minimize Maximum of Array (LC 2439), and Cutting Ribbons (LC 1891).
• Trigger phrases in problem statements: "minimize the maximum", "maximize the minimum", "within K groups/workers/days" — these signal binary search on answer.