HardArrayBinary SearchDynamic ProgrammingGreedyPrefix SumUpdated Sep 2026

410. Split Array Largest Sum

Asked at Google, Amazon, Uber, Pinterest

Difficulty

Hard

Time

O(n * log(sum(nums)))

Space

O(1)

Pattern

Array

Companies

4

Problem

You are given an integer array nums and an integer k. You must cut nums into exactly k non-empty pieces. Each piece must be a contiguous block of the original array — you can only cut between neighbours, and every element must end up in exactly one piece.

For a given split, look at the sum of each piece and take the largest of those sums. Your goal is to choose the split that makes this largest sum as small as possible. Return that smallest possible largest sum.

This is a "minimize the maximum" problem. The answer is never smaller than the biggest single element (that element must live in some piece), and never bigger than the total sum of the array (one piece holding everything).

Cut into k blocks, shrink the biggest block sum

numssum 14sum 1872510801234Two contiguous blocks; the answer is the larger blocksum, 18.
With k = 2 the best cut is [7,2,5] and [10,8]; the larger block sum is 18.

Constraints

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

Examples

Example 1
Inputnums = [7,2,5,10,8], k = 2
Output18
WhyWe need two blocks. Cutting as [7,2,5] and [10,8] gives sums 14 and 18, so the largest is 18. Any other cut gives a larger maximum, so 18 is the best we can do.
Example 2
Inputnums = [1,2,3,4,5], k = 2
Output9
WhyCutting as [1,2,3] and [4,5] gives sums 6 and 9, so the largest is 9. Splitting earlier or later always pushes one side above 9.

Asked At

4 companies
CompanyDifficulty
GoogleHardView all Google questions →
AmazonHardView all Amazon questions →
UberHardView all Uber questions →
PinterestHardView all Pinterest questions →

How to Think About It

1

Brute force: try all possible ways to split the array into k subarrays. There are C(n-1, k-1) ways, which is exponential. Not feasible.

2

DP approach: dp[i][j] = minimum largest sum when splitting nums[0..i-1] into j subarrays. Transition: dp[i][j] = min over all valid p of max(dp[p][j-1], sum(p+1..i)). Time: O(n^2 * k). Works for small n but too slow for large inputs.

3

Binary search on the answer: the answer (minimum largest sum) is between max(nums) (each element in its own subarray) and sum(nums) (all elements in one subarray). Binary search this range. For each candidate sum, check if we can split into <= k subarrays where each subarray sum <= candidate.

4

Greedy check function: given a max sum limit, iterate through the array, greedily forming subarrays. Start a new subarray when adding the next element would exceed the limit. Count the number of subarrays needed. If count <= k, the candidate works (try smaller). If count > k, the candidate is too small (try larger).

5

Time: O(n * log(sum - max)). Space: O(1) for the greedy check.

Optimal Approach

Binary search on the answer. Set lo = max(nums), hi = sum(nums). While lo < hi: compute mid = (lo + hi) // 2. Greedy check: can we split into <= k subarrays with each sum <= mid? If yes, hi = mid (try smaller). If no, lo = mid + 1 (need larger). Return lo.

Greedy check: iterate through nums, maintain current subarray sum. If adding the next element exceeds mid, start a new subarray. Count subarrays.

Walkthrough: nums = [7, 2, 5, 10, 8], k = 2.

  • lo=10, hi=32, mid=21. Greedy: [7,2,5]=14, [10,8]=18. 2 <= 2. hi=21.
  • lo=10, hi=21, mid=15. Greedy: [7,2,5]=14, [10]=10, [8]=8. 3 > 2. lo=16.
  • lo=16, hi=21, mid=18. Greedy: [7,2,5]=14, [10,8]=18. 2 <= 2. hi=18.
  • lo=16, hi=18, mid=17. Greedy: [7,2,5]=14, [10]=10, [8]=8. 3 > 2. lo=18.
  • lo=hi=18. Return 18.

Time: O(n * log(sum)). Space: O(1).

Binary search the answer, check with a greedy scan

lo = max(nums) = 10hi = sum(nums) = 32guess mid, run greedy checkThe answer lies between the biggest element and thetotal sum.mid = 21141872510801234Limit 21 needs only 2 blocks, so 21 works — searchlower.mid = 151410872510801234Limit 15 needs 3 blocks, too many — search higher.canSplit(limit): pack greedily, count blockscount <= k -> hi = midcount > k -> lo = mid + 1answer = lo = 18
Guess a limit, greedily pack elements, and count how many blocks are needed.
ComplexityTime O(n * log(sum(nums)))Space O(1)Each binary search step runs one O(n) greedy scan, and the search range is the sum of the array.

What Trips People Up in Real Interviews

1

Setting the binary search bounds incorrectly. lo must be max(nums) (not 0 or 1) because each subarray must contain at least one element. hi must be sum(nums) (not infinity) because the worst case is one subarray containing everything.

2

Off-by-one in the greedy check: starting a new subarray when current + num >= maxSum instead of > maxSum. If the current subarray sum equals the limit, it is valid. Only exceed the limit triggers a new subarray.

3

Confusing "minimize the largest sum" with "minimize the number of subarrays." The problem asks to minimize the maximum subarray sum given exactly k subarrays. The binary search approach finds the minimum feasible maximum.

4

Using int for the sum in C++/Java. The sum of the array can exceed Integer.MAX_VALUE for large arrays. Use long for the binary search bounds and the running sum in the greedy check.

5

Not verifying the greedy check correctly. After the loop, the count of subarrays must be <= k. If you forget to count the last subarray (it is counted at the start when count = 1), the check will be off by one.

Solution Code

O(n * log(sum(nums))) time
def splitArray(nums, k):
    def canSplit(maxSum):
        count, current = 1, 0
        for num in nums:
            if current + num > maxSum:
                count += 1
                current = num
            else:
                current += num
        return count <= k

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

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Split Array Largest Sum problem?

Given an integer array nums and an integer k, split nums into k non-empty contiguous subarrays. The largest sum of these subarrays is minimized. Return the largest sum of the split. This is a classic "minimize the maximum" binary search problem.

How do you solve Split Array Largest Sum?

The optimal approach runs in O(n * log(sum(nums))) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Split Array Largest Sum?

Split Array Largest Sum is asked at Google, Amazon, Uber, Pinterest. It is a hard difficulty problem.

What are common mistakes on Split Array Largest Sum?
  • Setting the binary search bounds incorrectly. `lo` must be `max(nums)` (not 0 or 1) because each subarray must contain at least one element. `hi` must be `sum(nums)` (not infinity) because the worst case is one subarray containing everything.
  • Off-by-one in the greedy check: starting a new subarray when `current + num >= maxSum` instead of `> maxSum`. If the current subarray sum equals the limit, it is valid. Only exceed the limit triggers a new subarray.
  • Confusing "minimize the largest sum" with "minimize the number of subarrays." The problem asks to minimize the maximum subarray sum given exactly k subarrays. The binary search approach finds the minimum feasible maximum.
  • Using `int` for the sum in C++/Java. The sum of the array can exceed `Integer.MAX_VALUE` for large arrays. Use `long` for the binary search bounds and the running sum in the greedy check.
  • Not verifying the greedy check correctly. After the loop, the count of subarrays must be <= k. If you forget to count the last subarray (it is counted at the start when `count = 1`), the check will be off by one.