Split Array Largest Sum

Split Array Largest Sum is a classic “binary search on the answer” problem. People miss it because the array is not sorted, so they think binary search cannot help. But here we do not search the array. We search the range of possible answers. That twist is exactly what the interviewer is testing.

🎯 The Problem

You cut an array into k pieces so the largest piece is as small as possible. The rules:

• You get an array of numbers and a count k.
• Cut the array into k pieces that do not overlap.
• Each piece is a chunk of numbers next to each other.
• The pieces stay in order. You cannot rearrange the numbers.
• For any cutting, look at the piece with the biggest sum.
• Cut so that this biggest piece sum is as small as it can be. You are trying to minimize the maximum piece sum.

Input:  nums = [7, 2, 5, 10, 8], k = 2
Output: 18

Explanation: Best split is [7, 2, 5] and [10, 8].
Their sums are 14 and 18. The largest is 18, and no
2-way split does better than 18.

Here is the picture. We place one cut to make two pieces, then look at the larger piece sum.

🐢 Approach 1: Try Every Split (Brute Force)

Place the cuts every possible way and keep the best result.

The idea:

• Try every way of placing the cuts.
• For each way, find the biggest piece sum.
• Remember the smallest biggest sum across all the ways.

How it works:

• Enumerate all positions for the cuts.
• Score each layout by its largest piece sum.
• The minimum of those scores is the answer.

Why it is weak:

• The number of ways to place cuts explodes as the array grows.
• This is exponential time. It doubles and doubles as the input grows.
• It works only for tiny inputs.

Here is the recursive try-every-split code:

def split_array(nums, k):
    def dfs(start, parts_left):
        if parts_left == 1:
            return sum(nums[start:])

        best = float("inf")
        current = 0
        for cut in range(start, len(nums) - parts_left + 1):
            current += nums[cut]
            largest = max(current, dfs(cut + 1, parts_left - 1))
            best = min(best, largest)
        return best

    return dfs(0, k)

⚡ Approach 2: Binary Search on the Answer (Best)

Search the range of possible answers, not the array.

The idea:

• The answer is some number, the largest piece sum.
• It cannot be below the biggest single number, since that number must sit inside some piece.
• It cannot be above the sum of all numbers, since that is one piece holding everything.
• So the answer lives between the biggest single number and the total.

The feasibility check:

• Guess a value limit. Ask: can we use k pieces or fewer with no piece sum over limit?
• That yes-or-no question is the feasibility check.
• Run it greedily. Keep adding numbers to the current piece.
• The moment the next number would push the piece over limit, start a new piece.
• Count the pieces. If the count is k or fewer, the limit works.

How it works:

• Binary search the answer range.
• If the limit works, a smaller limit might also work, so search the lower half.
• If it does not work, the limit was too tight, so search the upper half.

Why it is fast:

• Each step halves the answer range.
• Each check is one pass of the array.
• Time is O(n log S), where S is the sum of all numbers.

Here is a dry run on nums = [7, 2, 5, 10, 8] with k = 2. Watch the answer range narrow.

Steps to Solve

1. Set the low end of the search to the biggest single number in the array.
2. Set the high end to the sum of all numbers.
3. Pick the middle value limit between low and high. This is the guessed largest piece sum.
4. Run the feasibility check: greedily fill pieces without going over limit, and count how many pieces you need.
5. If the count is k or fewer, the limit works, so move high down to limit. Otherwise move low up past limit.
6. When low and high meet, low is the smallest workable largest piece sum. Return it.

#include <stdio.h>

// how many pieces if no piece sum may exceed limit
int piecesNeeded(int nums[], int n, int limit) {
    int pieces = 1, current = 0;
    for (int i = 0; i < n; i++) {
        if (current + nums[i] > limit) {  // would overflow, start new piece
            pieces++;
            current = nums[i];
        } else {
            current += nums[i];
        }
    }
    return pieces;
}

int splitArray(int nums[], int n, int k) {
    int lo = 0, hi = 0;
    for (int i = 0; i < n; i++) {
        if (nums[i] > lo) lo = nums[i];   // biggest single number
        hi += nums[i];                    // total of all numbers
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (piecesNeeded(nums, n, mid) <= k) {  // limit works
            hi = mid;                            // try a smaller limit
        } else {
            lo = mid + 1;                        // too tight, raise limit
        }
    }
    return lo;
}

int main(void) {
    int nums[] = {7, 2, 5, 10, 8};
    printf("%d\n", splitArray(nums, 5, 2));
    return 0;
}

18

#include <iostream>
#include <vector>
using namespace std;

int piecesNeeded(vector<int>& nums, int limit) {
    int pieces = 1, current = 0;
    for (int x : nums) {
        if (current + x > limit) {   // would overflow, start new piece
            pieces++;
            current = x;
        } else {
            current += x;
        }
    }
    return pieces;
}

int splitArray(vector<int>& nums, int k) {
    int lo = 0, hi = 0;
    for (int x : nums) {
        lo = max(lo, x);   // biggest single number
        hi += x;           // total of all numbers
    }
    while (lo < hi) {
        int mid = lo + (hi - lo) / 2;
        if (piecesNeeded(nums, mid) <= k) {
            hi = mid;       // try smaller
        } else {
            lo = mid + 1;   // too tight
        }
    }
    return lo;
}

int main() {
    vector<int> nums = {7, 2, 5, 10, 8};
    cout << splitArray(nums, 2) << endl;
    return 0;
}

18

public class SplitArray {
    static int piecesNeeded(int[] nums, int limit) {
        int pieces = 1, current = 0;
        for (int x : nums) {
            if (current + x > limit) {   // would overflow, new piece
                pieces++;
                current = x;
            } else {
                current += x;
            }
        }
        return pieces;
    }

    public static int splitArray(int[] nums, int k) {
        int lo = 0, hi = 0;
        for (int x : nums) {
            lo = Math.max(lo, x);   // biggest single number
            hi += x;                // total of all numbers
        }
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (piecesNeeded(nums, mid) <= k) {
                hi = mid;            // try smaller
            } else {
                lo = mid + 1;        // too tight
            }
        }
        return lo;
    }

    public static void main(String[] args) {
        int[] nums = {7, 2, 5, 10, 8};
        System.out.println(splitArray(nums, 2));
    }
}

18

def pieces_needed(nums, limit):
    pieces, current = 1, 0
    for x in nums:
        if current + x > limit:   # would overflow, start a new piece
            pieces += 1
            current = x
        else:
            current += x
    return pieces


def split_array(nums, k):
    lo, hi = max(nums), sum(nums)   # answer lives in this range
    while lo < hi:
        mid = (lo + hi) // 2        # guessed largest piece sum
        if pieces_needed(nums, mid) <= k:   # feasibility check
            hi = mid                # works, try a smaller limit
        else:
            lo = mid + 1            # too tight, raise the limit
    return lo


print(split_array([7, 2, 5, 10, 8], 2))

18

function piecesNeeded(nums, limit) {
  let pieces = 1, current = 0;
  for (const x of nums) {
    if (current + x > limit) {  // would overflow, new piece
      pieces++;
      current = x;
    } else {
      current += x;
    }
  }
  return pieces;
}

function splitArray(nums, k) {
  let lo = Math.max(...nums);
  let hi = nums.reduce((a, b) => a + b, 0);
  while (lo < hi) {
    const mid = Math.floor((lo + hi) / 2);
    if (piecesNeeded(nums, mid) <= k) {
      hi = mid;        // works, try smaller
    } else {
      lo = mid + 1;    // too tight
    }
  }
  return lo;
}

console.log(splitArray([7, 2, 5, 10, 8], 2));

18

Let us read the Python version line by line, because the two helpers together are the whole solution.

def pieces_needed(nums, limit):
    pieces, current = 1, 0
    for x in nums:
        if current + x > limit:
            pieces += 1
            current = x
        else:
            current += x
    return pieces


def split_array(nums, k):
    lo, hi = max(nums), sum(nums)
    while lo < hi:
        mid = (lo + hi) // 2
        if pieces_needed(nums, mid) <= k:
            hi = mid
        else:
            lo = mid + 1
    return lo

pieces, current = 1, 0 starts the feasibility check with one open piece and a running sum of zero. We always have at least one piece.

if current + x > limit asks if adding this number would push the current piece over the guessed limit. If yes, we close this piece and start a new one with pieces += 1 and current = x. If no, we keep adding with current += x. This greedy filling uses the fewest pieces possible for that limit.

return pieces gives the smallest number of pieces that respect the limit.

lo, hi = max(nums), sum(nums) sets the answer range. The largest piece sum can never be below the biggest single number, and never above the total. So the answer must sit between them.

while lo < hi keeps shrinking the range until the two ends meet on the answer.

mid = (lo + hi) // 2 is our guessed largest piece sum for this round.

if pieces_needed(nums, mid) <= k runs the feasibility check. If mid lets us fit inside k pieces, the limit works. So we move hi = mid to test whether an even smaller limit also works. We keep mid in the range because it might be the final answer.

else: lo = mid + 1 runs when mid forces more than k pieces. The limit was too tight, so we raise the floor past it.

return lo gives the smallest limit that still fits inside k pieces. That is the minimized maximum piece sum.

⏱️ Time and Space Complexity

The brute force tries every cut, so it is exponential and only fine for tiny arrays. The binary search runs the feasibility check, which is one pass of the array, inside a loop that halves a numeric range. So the time is O(n log S), where n is the array length and S is the sum of all numbers. It uses only a few variables, so space is O(1).

🧩 Key Takeaways

• ✅ We do not search the array. We search the range of possible answers.
• ✅ The answer sits between the biggest single number and the sum of all numbers.
• ✅ The feasibility check greedily fills pieces and counts how many a limit needs.
• ✅ If a limit fits in k pieces, try a smaller limit. If not, raise the limit.
• ✅ This runs in O(n log S) time with only O(1) extra space.

🚀 What’s Next?

• Capacity To Ship Packages Within D Days
• Median of Two Sorted Arrays