HardNo. 0410
Split Array Largest Sum — LeetCode 410 Python Solution
- Pattern
- Prefix Sum
- Topics
- Greedy, Array, Binary Search, Dynamic Programming, Prefix Sum
- Reading time
- 3 min
- Source
- leetcode.com
The 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.
Example
- Input
- nums = [7,2,5,10,8], k = 2
- Output
- 18
- Explanation
- There are four ways to split nums into two subarrays.
Python solution
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
def check(mx):
s, cnt = inf, 0
for x in nums:
s += x
if s > mx:
s = x
cnt += 1
return cnt <= k
left, right = max(nums), sum(nums)
return left + bisect_left(range(left, right + 1), True, key=check)Complexity
- Time
- O(n × log m)
- Space · auxiliary
- O(1)
Pattern: Prefix Sum
Precompute running totals once so any range query becomes a single subtraction. LeetCode 410. Split Array Largest Sum is filed here because LeetCode tags it Prefix Sum, which is the vocabulary this hub collects.
The prefix sum guide has the Python template for the pattern and the 157 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 2439 | Minimize Maximum of Array | Medium |
| 1671 | Minimum Number of Removals to Make Mountain Array | Hard |
| 2389 | Longest Subsequence With Limited Sum | Easy |
| 2448 | Minimum Cost to Make Array Equal | Hard |
| 2560 | House Robber IV | Medium |
| 2616 | Minimize the Maximum Difference of Pairs | Medium |
Frequently asked questions
- How hard is LeetCode 410. Split Array Largest Sum?
LeetCode 410. Split Array Largest Sum is rated Hard on LeetCode.
- What is the time complexity of LeetCode 410. Split Array Largest Sum?
The Python solution on this page runs in O(n × log m).
- What is the space complexity of LeetCode 410. Split Array Largest Sum?
The Python solution on this page uses O(1) auxiliary space.
- What topics does LeetCode 410. Split Array Largest Sum cover?
LeetCode 410. Split Array Largest Sum is tagged Greedy, Array, Binary Search, Dynamic Programming and Prefix Sum on LeetCode.