Split array with minimum difference

Array Prefix Sum

33.6% acceptance

Feb 25, 2026

100

You are given an integer array nums. Split the array into exactly two subarrays, left and right, such that left is strictly increasing and right is strictly decreasing. Return the minimum possible absolute difference between the sums of left and right. If no valid split exists, return -1.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn split_array(nums: Vec<i32>) -> i64 {
    let n = nums.len();
    // left = nums[0..=i], right = nums[i+1..n-1]
    // left is strictly increasing: nums[0] < nums[1] < ... < nums[i]
    // right is strictly decreasing: nums[i+1] > nums[i+2] > ... > nums[n-1]
    // Precompute valid_left[i] = true if nums[0..=i] is strictly increasing.
    // Precompute valid_right[i] = true if nums[i..n-1] is strictly decreasing.
    let mut valid_left = vec![false; n];
    valid_left[0] = true;
    for i in 1..n {
      valid_left[i] = valid_left[i-1] && nums[i] > nums[i-1];
    }
    let mut valid_right = vec![false; n];
    valid_right[n-1] = true;
    for i in (0..n-1).rev() {
      valid_right[i] = valid_right[i+1] && nums[i] > nums[i+1];
    }
    // Prefix sums
    let mut prefix = vec![0i64; n + 1];
    for i in 0..n { prefix[i+1] = prefix[i] + nums[i] as i64; }
    let total = prefix[n];
    let mut ans: Option<i64> = None;
    // Split at i: left=[0..=i], right=[i+1..n-1]
    for i in 0..n-1 {
      if valid_left[i] && valid_right[i+1] {
        let left_sum = prefix[i+1];
        let right_sum = total - prefix[i+1];
        let diff = (left_sum - right_sum).abs();
        ans = Some(ans.map_or(diff, |a| a.min(diff)));
      }
    }
    ans.unwrap_or(-1)
  }
}