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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Split Array Largest Sum and Binary Search problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →