Split array largest sum

Array Binary Search Dynamic Programming Greedy Prefix Sum

59.9% acceptance

Jan 13, 2026

11251

270

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.

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn split_array(nums: Vec<i32>, k: i32) -> i32 {
    let can_split = |max_sum: i64| -> bool {
      let mut count = 1;
      let mut current_sum = 0i64;
      
      for &num in &nums {
        if current_sum + num as i64 > max_sum {
          count += 1;
          current_sum = num as i64;
        } else {
          current_sum += num as i64;
        }
      }
      
      count <= k
    };
    
    let mut left = *nums.iter().max().unwrap() as i64;
    let mut right: i64 = nums.iter().map(|&x| x as i64).sum();
    
    while left < right {
      let mid = left + (right - left) / 2;
      if can_split(mid) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    
    left as i32
  }
}