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.
Related Problems
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.
Return true if you can reach the last index, or false otherwise.
You are given an array of CPU tasks, each represented by letters A to Z, and a cooling time, n. Each cycle or interval allows the completion of one task. Tasks can be completed in any order, but there's a constraint: identical tasks must be separated by at least n intervals due to cooling time.
Return the minimum number of intervals required to complete all tasks.
Given an array nums with n integers, your task is to check if it could become non-decreasing by modifying at most one element.
We define an array is non-decreasing if nums[i] <= nums[i + 1] holds for every i (0-based) such that (0 <= i <= n - 2).