0410. Split Array Largest Sum
Hard | Binary Search | 32 ms (92.40%), 14.3 MB (65.39%)
Source: LeetCode - Aplit Array Largest Sum GitHub: Solution / Performance
Given an array nums which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays.
Write an algorithm to minimize the largest sum among these m subarrays.
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 10^61 <= m <= min(50, nums.length)
Input: nums = [7,2,5,10,8], m = 2
Output: 18
Explanation:
There are four ways to split nums into two subarrays.
The best way is to split it into [7,2,5] and [10,8],
where the largest sum among the two subarrays is only 18.
Input: nums = [1,2,3,4,5], m = 2
Output: 9
Input: nums = [1,4,4], m = 3
Output: 4Same as LeetCode 1011
Boundary / Search Space
Left (Minimum) = MAX number (cannot seperate a single number) Right (Maximum) = TOTAL amount
Condition
While Loop = Left < Right
Return Value
Left
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
# ==================================================
# Binary Search =
# ==================================================
# time : O(nlog(m)), m is the search space
# space : O(1)
l, r = max(nums), sum(nums)
while l < r:
mid = (l + r) // 2
count, groups = 0, 1
for num in nums:
count += num
if count > mid:
count = num
groups += 1
if groups > m: break
if groups <= m: r = mid
else: l = mid + 1
return lclass Solution {
/**
* @time : O(nlog(m)), m is the search space
* @space : O(1)
*/
public int splitArray(int[] nums, int m) {
int l = 0, r = 0;
for (int n: nums) {
l = Math.max(l, n);
r += n;
}
while(l < r) {
int mid = (l + r) / 2;
int count = 0, groups = 1;
for(int n: nums) {
count += n;
if(count > mid) {
count = n;
groups += 1;
}
if(groups > m) break;
}
if(groups <= m) r = mid;
else l = mid + 1;
}
return l;
}
}Last updated
Was this helpful?