Maximum balanced shipments

Array Dynamic Programming Stack Greedy Monotonic Stack

61.3% acceptance

Feb 25, 2026

You are given an integer array weight of length n, representing the weights of n parcels arranged in a straight line. A shipment is defined as a contiguous subarray of parcels. A shipment is considered balanced if the weight of the last parcel is strictly less than the maximum weight among all parcels in that shipment. Select a set of non-overlapping, contiguous, balanced shipments such that each parcel appears in at most one shipment (parcels may remain unshipped). Return the maximum possible number of balanced shipments that can be formed.

Solution

Rust

Time O(n)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn max_balanced_shipments(weight: Vec<i32>) -> i32 {
    // Greedy: scan left to right, maintain running max.
    // When weight[i] < running_max, we can end a shipment at i.
    // Start a new shipment from i+1.
    let n = weight.len();
    let mut count = 0;
    let mut cur_max = weight[0];
    let mut i = 1;
    while i < n {
      if weight[i] < cur_max {
        // End shipment here, start new one
        count += 1;
        i += 1;
        cur_max = if i < n { weight[i] } else { 0 };
        i += 1;
      } else {
        cur_max = cur_max.max(weight[i]);
        i += 1;
      }
    }
    count
  }
}