Off-by-one on range boundaries
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.
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.
Example 2:
Input: nums = [1,2,3,4,5], k = 2 Output: 9 Explanation: There are four ways to split nums into two subarrays. The best way is to split it into [1,2,3] and [4,5], where the largest sum among the two subarrays is only 9.
Constraints:
1 <= nums.length <= 10000 <= nums[i] <= 1061 <= k <= min(50, nums.length)Problem summary: 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.
Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.
Pattern signal: Array · Binary Search · Dynamic Programming · Greedy
[7,2,5,10,8] 2
[1,2,3,4,5] 2
capacity-to-ship-packages-within-d-days)divide-chocolate)fair-distribution-of-cookies)subsequence-of-size-k-with-the-largest-even-sum)maximum-total-beauty-of-the-gardens)Source-backed implementations are provided below for direct study and interview prep.
// Accepted solution for LeetCode #410: Split Array Largest Sum
class Solution {
public int splitArray(int[] nums, int k) {
int left = 0, right = 0;
for (int x : nums) {
left = Math.max(left, x);
right += x;
}
while (left < right) {
int mid = (left + right) >> 1;
if (check(nums, mid, k)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
private boolean check(int[] nums, int mx, int k) {
int s = 1 << 30, cnt = 0;
for (int x : nums) {
s += x;
if (s > mx) {
++cnt;
s = x;
}
}
return cnt <= k;
}
}
// Accepted solution for LeetCode #410: Split Array Largest Sum
func splitArray(nums []int, k int) int {
left, right := 0, 0
for _, x := range nums {
left = max(left, x)
right += x
}
return left + sort.Search(right-left, func(mx int) bool {
mx += left
s, cnt := 1<<30, 0
for _, x := range nums {
s += x
if s > mx {
s = x
cnt++
}
}
return cnt <= k
})
}
# Accepted solution for LeetCode #410: Split Array Largest Sum
class Solution:
def splitArray(self, nums: List[int], k: int) -> int:
def check(mx):
s, cnt = inf, 0
for x in nums:
s += x
if s > mx:
s = x
cnt += 1
return cnt <= k
left, right = max(nums), sum(nums)
return left + bisect_left(range(left, right + 1), True, key=check)
// Accepted solution for LeetCode #410: Split Array Largest Sum
struct Solution;
impl Solution {
fn split_array(nums: Vec<i32>, m: i32) -> i32 {
let mut lo = *nums.iter().max().unwrap();
let mut hi = nums.iter().sum();
let n = nums.len();
while lo <= hi {
let mid = (lo + hi) / 2;
if Self::split(&nums, mid, n) <= m {
hi = mid - 1;
} else {
lo = mid + 1;
}
}
lo
}
fn split(nums: &[i32], max: i32, n: usize) -> i32 {
let mut sum = 0;
let mut res = 1;
for i in 0..n {
if nums[i] + sum > max {
sum = nums[i];
res += 1;
} else {
sum += nums[i];
}
}
res
}
}
#[test]
fn test() {
let nums = vec![7, 2, 5, 10, 8];
let m = 2;
let res = 18;
assert_eq!(Solution::split_array(nums, m), res);
let nums = vec![1, 2, 3, 4, 5];
let m = 2;
let res = 9;
assert_eq!(Solution::split_array(nums, m), res);
let nums = vec![1, 4, 4];
let m = 3;
let res = 4;
assert_eq!(Solution::split_array(nums, m), res);
let nums = vec![2, 3, 1, 2, 4, 3];
let m = 5;
let res = 4;
assert_eq!(Solution::split_array(nums, m), res);
}
// Accepted solution for LeetCode #410: Split Array Largest Sum
function splitArray(nums: number[], k: number): number {
let l = Math.max(...nums);
let r = nums.reduce((a, b) => a + b);
const check = (mx: number) => {
let [s, cnt] = [0, 0];
for (const x of nums) {
s += x;
if (s > mx) {
s = x;
if (++cnt === k) return false;
}
}
return true;
};
while (l < r) {
const mid = (l + r) >> 1;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
Use this to step through a reusable interview workflow for this problem.
Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.
Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).
Review these before coding to avoid predictable interview regressions.
Wrong move: Loop endpoints miss first/last candidate.
Usually fails on: Fails on minimal arrays and exact-boundary answers.
Fix: Re-derive loops from inclusive/exclusive ranges before coding.
Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.
Usually fails on: Two-element ranges never converge.
Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.
Wrong move: An incomplete state merges distinct subproblems and caches incorrect answers.
Usually fails on: Correctness breaks on cases that differ only in hidden state.
Fix: Define state so each unique subproblem maps to one DP cell.
Wrong move: Locally optimal choices may fail globally.
Usually fails on: Counterexamples appear on crafted input orderings.
Fix: Verify with exchange argument or monotonic objective before committing.