⬅ Previous Topic
Allocate Minimum Number of PagesNext Topic ⮕
Painter's Partition Problem⬅ Previous Topic
Allocate Minimum Number of PagesNext Topic ⮕
Painter's Partition ProblemTopic Contents
Given an array of non-negative integers and an integer K
, split the array into K contiguous subarrays such that the maximum sum among these subarrays is minimized.
K
parts.The goal is to make the largest sum among the K subarrays as small as possible.
If the array is empty or K is zero, return 0
as the answer.
low = max(arr)
and high = sum(arr)
.low ≤ high
:mid = (low + high) / 2
.answer = mid
and try a smaller value by high = mid - 1
.low = mid + 1
.answer
.public class SplitArrayLargestSum {
public static int splitArray(int[] nums, int k) {
int low = Integer.MIN_VALUE;
int high = 0;
for (int num : nums) {
low = Math.max(low, num); // Minimum possible max sum is the largest element
high += num; // Maximum possible max sum is sum of all elements
}
int result = high;
while (low <= high) {
int mid = low + (high - low) / 2;
if (canSplit(nums, k, mid)) {
result = mid; // Try a smaller maximum sum
high = mid - 1;
} else {
low = mid + 1; // Increase allowed max sum
}
}
return result;
}
private static boolean canSplit(int[] nums, int k, int maxSum) {
int currentSum = 0;
int splits = 1;
for (int num : nums) {
if (currentSum + num > maxSum) {
splits++;
currentSum = num;
if (splits > k) return false; // Too many splits needed
} else {
currentSum += num;
}
}
return true;
}
public static void main(String[] args) {
int[] arr = {7, 2, 5, 10, 8};
int k = 2;
System.out.println("Minimum largest sum: " + splitArray(arr, k));
}
}
Case | Time Complexity | Explanation |
---|---|---|
Best Case | O(n log(sum - max)) | We perform binary search over the range from max element to sum of all elements, and in each step, we scan the array once. |
Average Case | O(n log(sum - max)) | For each binary search iteration, we check if the array can be split into K subarrays using a greedy scan. |
Worst Case | O(n log(sum - max)) | Even in the worst case, binary search narrows down the search space logarithmically, with O(n) work per step. |
O(1)
Explanation: No extra space is used except a few variables for tracking sums and counters.
⬅ Previous Topic
Allocate Minimum Number of PagesNext Topic ⮕
Painter's Partition ProblemYou can support this website with a contribution of your choice.
When making a contribution, mention your name, and programguru.org in the message. Your name shall be displayed in the sponsors list.