binary search on the answer. for a candidate maxSum, check if we can split the array into k subarrays where each sum ≤ maxSum. if yes, try smaller; if no, try larger.
the search range is [max(nums), sum(nums)]. the greedy check function tries to fit as many elements as possible into each subarray without exceeding maxSum.
binary search pattern
- left bound: max element (can't be smaller)
- right bound: total sum (worst case: one subarray)
- canSplit checks if k subarrays are possible
- find minimum valid maxSum
complexity
O(n log(sum)) time: binary search is O(log(sum)), each check is O(n). O(1) space. efficient search on answer approach.