How do you solve Split Array Largest Sum?

Use binary search between max(nums) and sum(nums). For each candidate largest sum, greedily split the array into subarrays without exceeding this sum. If the number of subarrays needed is less than or equal to k, the candidate is feasible, and the search narrows to smaller sums. Otherwise, it moves to larger sums. This approach runs in O(n log(sum(nums))) time.

What pattern does Split Array Largest Sum use?

The Pattern: Binary Search on Answer Space (Feasibility Check) The Heuristic: When the problem asks for an optimal numeric value bounded by a range and feasibility can be checked in linear time, use binary search on the answer space by repeatedly testing midpoints and narrowing the range based on feasibility.

Split Array Largest Sum — Modified Binary Search

Q: What is the time complexity of Split Array Largest Sum?

O(n log S). The binary search runs over the range from max(nums) to sum(nums), which is at most sum(nums) - max(nums). Each feasibility check iterates through nums once (O(n)). Thus, total time is O(n log S), where S = sum(nums).

Problem

Given an array of non-negative integers nums and an integer k, split nums into k non-empty continuous subarrays such that the largest sum among these subarrays is minimized, and return this minimized largest sum.

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 10⁶
1 ≤ k ≤ nums.length

Example

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

Output: 18

One optimal way to split is [7,2,5] and [10,8]. The sums are 14 and 18, so the largest sum is 18. Any other split results in a larger maximum subarray sum. A brute-force approach would try all possible splits, which is exponential. Instead, the algorithm uses binary search on the range between the largest single element (10) and the total sum (32). It tests midpoints to check if the array can be split into at most k subarrays with sums not exceeding the midpoint. The critical moment is when the midpoint 18 is tested and found feasible, allowing the search to narrow down to smaller sums until the minimal feasible largest sum is found.

Approach

Straightforward Solution

A brute-force approach enumerates all possible splits into k subarrays and calculates the largest sum for each, resulting in exponential time complexity, which is infeasible for large inputs.

Core Observation

The minimal largest sum after splitting lies between the maximum single element (lower bound) and the total sum of the array (upper bound). This range forms a search space for the answer.

Path to Optimal

Preview

Recognizing that the answer is a number within a bounded range, the problem transforms into a decision problem: 'Can the array be split into at most k subarrays with sums not exceeding a given value?' This monotonic property enables binary search on the answer space…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Use binary search between max(nums) and sum(nums). For each candidate largest sum, greedily split the array into subarrays without exceeding this sum…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n log S)

The binary search runs over the range from max(nums) to sum(nums), which is at most sum(nums) - max(nums). Each feasibility check iterates through nums once (O(n)). Thus, total time is O(n log S), where S = sum(nums).

Space

O(1)

The algorithm uses only a fixed number of variables for pointers and counters, with no additional data structures proportional to input size.

Solution

Python

1class Solution:
2    def splitArray(self, nums: List[int], k: int) -> int:
3        def canSplit(max_allowed_sum):
4            subarrays = 1
5            current_sum = 0
6
7            for num in nums:
8                if current_sum + num > max_allowed_sum:
9                    subarrays += 1
10                    current_sum = 0
11
12                current_sum += num
13
14            return subarrays <= k
15
16        l, r = max(nums), sum(nums)
17
18        while l < r:
19            max_allowed_sum = (l + r) // 2
20
21            if canSplit(max_allowed_sum):
22                r = max_allowed_sum
23            else:
24                l = max_allowed_sum + 1
25
26        return l

Step-by-Step Solution

1

Greedily Check Feasibility of a Candidate Largest Sum

3def canSplit(max_allowed_sum):
  subarrays = 1
  current_sum = 0
  for num in nums:
      if current_sum + num > max_allowed_sum:
          subarrays += 1
          current_sum = 0
      current_sum += num
  return subarrays <= k

Objective

To determine if nums can be split into at most k subarrays such that no subarray sum exceeds max_allowed_sum.

Key Insight

By iterating through nums and accumulating sums, whenever adding the next number exceeds max_allowed_sum, a new subarray is started. Counting how many subarrays are needed reveals if the candidate sum is feasible. This greedy approach works because any valid split must respect the sum constraint, and the minimal number of subarrays for a given sum can be found in a single pass.

Interview Quick-Check

Core Logic

The feasibility check greedily forms subarrays by accumulating sums until exceeding max_allowed_sum, then starting a new subarray, ensuring the minimal number of subarrays for that sum.

State & Boundaries

Initialize subarrays count to 1 and current_sum to 0 before iterating through nums.

Common Pitfalls & Bugs

Forgetting to reset current_sum after starting a new subarray or miscounting subarrays leads to incorrect feasibility results.

2

Binary Search to Narrow Down the Minimal Largest Sum

To iteratively adjust the search boundaries based on feasibility until the minimal largest sum is found.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 4 Critical lines interviewers watch for.

Line 8 Critical

if current_sum + num > max_allowed_sum:

Check if adding the current number exceeds max_allowed_sum.

This conditional is the critical decision point that enforces the sum constraint, ensuring subarrays do not exceed the candidate maximum sum.

Line 14 Critical

return subarrays <= k

Return whether the number of subarrays is at most k.

Returning this condition encapsulates the feasibility test, enabling binary search to adjust boundaries based on whether the candidate sum is achievable.

Line 21 Critical

if canSplit(max_allowed_sum):

Check if the array can be split with the current midpoint as max allowed sum.

This call is the core of the binary search decision, directly influencing boundary adjustments.

Full line-by-line criticality + rationale for all 17 lines available on Pro.

Test Your Understanding

Why does binary searching on the range between max(nums) and sum(nums) guarantee finding the minimal largest subarray sum?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Split Array Largest Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Split Array Largest Sum drill

or drill a free problem

1	`class Solution:`
2	`def splitArray(self, nums: List[int], k: int) -> int:`
3	`def canSplit(max_allowed_sum):`
4	`subarrays = 1`
5	`current_sum = 0`
6
7	`for num in nums:`
8	`if current_sum + num > max_allowed_sum:`
9	`subarrays += 1`
10	`current_sum = 0`
11
12	`current_sum += num`
13
14	`return subarrays <= k`
15
16	`l, r = max(nums), sum(nums)`
17
18	`while l < r:`
19	`max_allowed_sum = (l + r) // 2`
20
21	`if canSplit(max_allowed_sum):`
22	`r = max_allowed_sum`
23	`else:`
24	`l = max_allowed_sum + 1`
25
26	`return l`

3	`def canSplit(max_allowed_sum):`
4	`subarrays = 1`
5	`current_sum = 0`
7	`for num in nums:`
8	`if current_sum + num > max_allowed_sum:`
9	`subarrays += 1`
10	`current_sum = 0`
12	`current_sum += num`
14	`return subarrays <= k`