I've been working through linked list and binary search problems recently, and noticed a gap between two existing patterns on this platform. I have contributed this problem, sharing it here in case it's useful for others, and would appreciate any feedback from the community.
Problem Statement : Split Linked List Into K Parts With Minimum-Maximum Load
You are given the head of a singly linked list where each node has a positive integer val representing its "load", and an integer k.
Split the linked list into exactly k contiguous parts (each part is a non-empty sublist; if there are fewer than k nodes, the remaining parts are null), such that the maximum total load among all parts is minimized.
Return an array of k ListNode heads representing the parts, in left-to-right order.
Note: Unlike splitting by node count, parts must be chosen so that the heaviest part's total load is as small as possible. Equal node counts are not required.
Examples
Example 1:
Input: head = [1,2,3,4,5], k = 3
Output: [[1,2,3],[4],[5]]
Explanation:
Splitting into [1,2,3], [4], [5] gives loads 6, 4, 5 -> max = 6.
Splitting by node count instead, [1,2],[3,4],[5], gives loads 3, 7, 5 -> max = 7, which is worse.Example 2:
Input: head = [7,2,5,10,8], k = 2
Output: [[7,2,5],[10,8]]
Explanation:
[7,2,5] sums to 14, [10,8] sums to 18. Max = 18.
This is the best possible split into 2 contiguous parts.Example 3:
Input: head = [3], k = 5
Output: [[3],null,null,null,null]
Explanation:
Only one node exists, so part 1 gets it and the remaining 4 parts are null.Constraints
1 <= n <= 10^41 <= k <= n1 <= val <= 10^4
Why This Doesn't Reduce to an Existing Problem
"Split Array Largest Sum" (LC 410) solves this exact optimization, but only on arrays, and it returns a single number rather than the actual subarrays. "Split Linked List in Parts" (LC 725) performs real pointer manipulation on a linked list, but it only balances node count and ignores the values stored in each node entirely.
This problem sits at the intersection: the answer has to be found through binary search on the maximum load, the same way LC 410 does it, but the result has to be a set of real ListNode sublists, which means correct pointer cutting the way LC 725 requires. Neither problem alone tests both skills together.
Approach
- Binary search the answer. Lower bound is the largest single node value, upper bound is the sum of all values.
- For a candidate capacity
mid, greedily walk the list once, counting how many parts are needed if no part may exceed that capacity. - If the parts needed are
<= k, the capacity is feasible, so try a smaller one. Otherwise, try larger. - Once the minimal feasible capacity is found, walk the list one final time and physically cut it at that capacity, setting
.next = nullat each boundary and padding unused slots withnull.
Time: O(n log(sum of values))
Space: O(k)
Solution (Java)
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int val) { this.val = val; }
* }
*/
class Solution {
public ListNode[] splitListByLoad(ListNode head, int k) {
int maxVal = 0, total = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
maxVal = Math.max(maxVal, cur.val);
total += cur.val;
}
int lo = maxVal, hi = total;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (partsNeeded(head, mid) <= k) hi = mid;
else lo = mid + 1;
}
ListNode[] result = new ListNode[k];
ListNode cur = head;
for (int i = 0; i < k && cur != null; i++) {
ListNode partHead = cur, prev = cur;
int load = cur.val;
cur = cur.next;
while (cur != null && load + cur.val <= lo) {
load += cur.val;
prev = cur;
cur = cur.next;
}
prev.next = null;
result[i] = partHead;
}
return result;
}
private int partsNeeded(ListNode head, int capacity) {
int parts = 1, load = 0;
for (ListNode cur = head; cur != null; cur = cur.next) {
if (load + cur.val > capacity) {
parts++;
load = cur.val;
} else {
load += cur.val;
}
}
return parts;
}
}Dry Run (Example 1)
Input: head = [1,2,3,4,5], k = 3
Binary search bounds: lo = 5 (max val), hi = 15 (sum)
mid = 10 -> 1+2+3+4 fits, +5 doesn't -> 2 parts needed. Feasible, try smaller. hi = 10
mid = 7 -> 1+2+3 fits, +4 doesn't -> new part. 4+5 doesn't fit in 7 -> another part. 3 parts. Feasible. hi = 7
mid = 6 -> 1+2+3=6 fits exactly, +4 doesn't -> new part. 4 fits, +5 doesn't -> new part. 5 fits. 3 parts. Feasible. hi = 6
lo = 5, hi = 6 -> mid = 5 -> 1+2=3 fits, +3 doesn't -> new part. 3 fits, +4 doesn't -> new part. 4 fits, +5 doesn't -> new part. 5 fits. 4 parts needed, exceeds k=3. lo = 6
lo == hi == 6. Minimum feasible capacity is 6.
Final cut at capacity 6:
Part 1: 1+2+3 = 6, stop before 4 -> [1,2,3]
Part 2: 4, stop before 5 -> [4]
Part 3: 5 -> [5]
Result: [[1,2,3],[4],[5]], max load = 6Test Cases
head = [1,2,3,4,5], k = 3 -> [[1,2,3],[4],[5]]
head = [7,2,5,10,8], k = 2 -> [[7,2,5],[10,8]]
head = [3], k = 5 -> [[3],null,null,null,null]
head = [1,1,1,1,1,1,1,1,1], k = 3 -> [[1,1,1],[1,1,1],[1,1,1]]
head = [10], k = 1 -> [[10]]
head = [4,9,2,6,1,8,3], k = 4 -> [[4,9],[2,6],[1,8],[3]]Open to thoughts on whether the difficulty leans more Medium or Hard, and whether the constraint range feels right. Also curious if anyone sees an edge case the dry run doesn't cover.
Tags: LinkedList, Greedy, Binary Search