Split Array Largest Sum
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.
#Binary search + Greedy solution
class Solution:
def countPartitions(self, nums, maxSum):
partitions = 1
subSum = 0
for num in nums:
if subSum + num <= maxSum:
subSum += num
else:
partitions += 1
subSum = num
return partitions
def splitArray(self, nums: List[int], k: int) -> int:
low = max(nums)
high = sum(nums)
while low <= high:
mid = (low + high) // 2
partitions = self.countPartitions(nums, mid)
if partitions > k:
low = mid + 1
else:
high = mid - 1
return low
This is a canonical binary search problem. It is often phrased in a way where it asks to minimize the weight of shipments and there are a few variations on the same theme.
Posted by Jamie Meyer 15 days ago