Partition array into disjoint intervals

Array

49.4% acceptance

Feb 25, 2026

1766

Given an integer array nums, partition it into two (contiguous) subarrays left and right so that: Every element in left is less than or equal to every element in right. left and right are non-empty. left has the smallest possible size. Return the length of left after such a partitioning. Test cases are generated such that partitioning exists.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn partition_disjoint(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut left_max = nums[0];
    let mut cur_max = nums[0];
    let mut ans = 0;
    for i in 1..n {
      if nums[i] < left_max {
        ans = i;
        left_max = cur_max;
      } else {
        cur_max = cur_max.max(nums[i]);
      }
    }
    (ans + 1) as i32
  }
}