Partition Array

Split an array into k contiguous groups of near-equal sum.

arrays partition contiguous sum

Given a list of non-negative integers `arr` and a positive integer `k`, partition `arr` into exactly `k` contiguous non-empty subarrays (each element belongs to exactly one subarray, and the subarrays appear in the original order) such that the maximum sum among the subarrays is as small as possible.

Write a function `min_max_partition(arr, k)` that returns the minimum possible value of the largest subarray sum.

For example, for `arr = [7, 2, 5, 10, 8]` and `k = 2`, the optimal partition is `[7,2,5]` and `[10,8]` with sums 14 and 18, so the maximum is 18. No other split gives a smaller maximum, so the function returns 18.

**Important:**
- The subarrays must be contiguous and non-empty.
- If `k` is greater than the length of `arr`, return `-1` because a valid partition is impossible.
- If `arr` is empty and `k` is positive, return `-1` because you cannot form non-empty subarrays.
- All elements are non-negative, and `k` is positive.

Constraints

Constraints:
- 0 <= len(arr) <= 10^5
- 0 <= arr[i] <= 10^9
- 1 <= k <= 10^5
- Expected time complexity: O(n log S) where n is the number of elements and S is the sum of the array (binary search over the answer). The solution must handle large inputs efficiently (do not brute-force all partitions).

Example

>>> min_max_partition([7, 2, 5, 10, 8], 2)
18
>>> min_max_partition([1, 2, 3], 3)
3
>>> min_max_partition([1, 2, 3], 1)
6
>>> min_max_partition([1, 2, 3], 4)
-1
>>> min_max_partition([], 1)
-1

25 points ~25 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Decide whether a given candidate maximum `X` is feasible: can you split the array into at most `k` groups, each with sum ≤ X? If yes, a maximum of X is attainable.

The answer lies between `max(arr)` (or 0 if empty) and `sum(arr)`. Use binary search on this range to find the smallest feasible maximum.

For feasibility, greedily accumulate elements into the current group as long as the sum doesn't exceed X; when it would exceed, start a new group. Count the groups and check if the count <= k.

Remember that every group must be non-empty: if a single element is larger than X, the candidate is infeasible.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.