Skip to main content

410. Split Array Largest Sum

hard

Partition an array into k contiguous subarrays to minimize the largest subarray sum. The crown jewel of binary-search-on-answer — once you see this pattern, you'll spot it everywhere.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an integer array nums and an integer k, split nums into k non-empty subarrays such that the largest sum of any subarray is minimized. Return the minimized largest sum of the split. A subarray is a contiguous part of the array.

Constraints

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

Examples

Example 1

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

Explanation: Best split is [7,2,5] and [10,8] with sums 14 and 18. The largest is 18.

Example 2

Input
nums = [1,2,3,4,5], k = 2
Output
9

Explanation: Best split is [1,2,3] and [4,5] with sums 6 and 9.

Example 3

Input
nums = [1,4,4], k = 3
Output
4

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

The answer lies in [max(nums), sum(nums)]. Anything below max(nums) can't even hold the single largest element; anything above sum(nums) is wasteful.

Hint 2

Define canSplit(cap, k): can we partition nums into <= k subarrays with each subarray sum <= cap? Greedy left-to-right works.

Hint 3

canSplit(cap, k) is monotonic in cap. Binary-search for the smallest cap where it returns true.

Solution approach

Reveal approach

Binary search on the answer cap. Set lo = max(nums) (one subarray must hold the largest element) and hi = sum(nums) (k = 1 case). Define canSplit(cap): walk nums greedily, accumulating into the current subarray; whenever adding the next element would exceed cap, close the current subarray and start a new one. Return whether the number of subarrays used is <= k. This greedy is optimal because making any subarray smaller can only force more subarrays. The predicate is monotonic — larger cap allows fewer subarrays — so binary-search the smallest cap that satisfies it: while lo < hi, mid = lo + (hi - lo) / 2; if canSplit(mid), hi = mid; else lo = mid + 1. Return lo. Each check is O(n); we do O(log(sum)) iterations. Total O(n log(sum)) time, O(1) space. This template (binary-search the answer + greedy feasibility check) solves Koko Eating Bananas, Capacity To Ship Packages, Minimum Number of Days to Make m Bouquets, and dozens more.

Complexity

Time
O(n log(sum))
Space
O(1)

Related patterns

  • binary-search
  • binary-search-on-answer
  • dynamic-programming

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Apple

More Binary Search practice problems

See all Binary Search problems →