[Question]: 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.
Example 1:
Input: nums = [7,2,5,10,8], k = 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.
// TC: O(Nlog(N))
// SC: O(1)
func splitArray(_ nums: [Int], _ splitValue: Int) -> Int {
//-1. find the boundary
var left = 0, right = 0
for num in nums {
left = max(num, left)
right += num
}
var result = Int.max
while left <= right {
let mid = left + (right - left)/2
if isValidSplitSum(nums, mid, splitValue) {
result = min(result, mid)
right = mid - 1
} else {
left = mid + 1
}
}
return result
}
private func isValidSplitSum(_ nums: [Int], _ aSplitSum: Int, _ splitValue: Int) -> Bool {
var count = 1
var current = 0
for i in 0..<nums.count {
current += nums[i]
if nums[i] > aSplitSum {
return false
}
if current > aSplitSum {
current = nums[i]
count += 1
}
}
return count <= splitValue
}
let arrSplitArray = [7,2,5,10,8]
let splitInto = 2
let opSplitSum = splitArray(arrSplitArray, splitInto)
print("op Split Sum ", opSplitSum)// 18 which is 10+8 [7,2,5] [10,8]