Delivering boxes from storage to ports

Array Dynamic Programming Segment Tree Queue Heap (Priority Queue) Prefix Sum Monotonic Queue

40.1% acceptance

Feb 25, 2026

403

You have boxes to deliver from storage to ports using a ship with maxBoxes and maxWeight limits. Boxes must be delivered in order. Each batch of boxes taken in one trip counts as 2 trips (go and return) plus one trip per port change within the batch. Return minimum total trips.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

use std::collections::VecDeque;

impl Solution {
  pub fn box_delivering(
    boxes: Vec<Vec<i32>>,
    _ports_count: i32,
    max_boxes: i32,
    max_weight: i32,
  ) -> i32 {
    let n = boxes.len();
    let max_boxes = max_boxes as usize;
    let max_weight = max_weight as i64;

    // diff[i] = 1 if boxes[i].port != boxes[i-1].port, for i >= 1
    // P[i] = sum diff[1..i] (port changes among boxes 0..i-1)
    let mut p = vec![0i32; n];
    for i in 1..n {
      p[i] = p[i - 1] + (boxes[i][0] != boxes[i - 1][0]) as i32;
    }

    // Weight prefix sums
    let mut wsum = vec![0i64; n + 1];
    for i in 0..n {
      wsum[i + 1] = wsum[i] + boxes[i][1] as i64;
    }

    // dp[i] = min trips to deliver boxes[0..i)
    // dp[i] = min_{j valid} (dp[j] - P[j]) + 2 + P[i-1]
    // where P[-1] = 0, and batch is boxes[j..i)
    let mut dp = vec![i32::MAX; n + 1];
    dp[0] = 0;

    // Monotone deque storing j indices, front = min(dp[j]-P[j])
    let mut dq: VecDeque<usize> = VecDeque::new();
    dq.push_back(0);

    for i in 1..=n {
      // Remove invalid j from front
      while let Some(&j) = dq.front() {
        if j + max_boxes < i || wsum[i] - wsum[j] > max_weight {
          dq.pop_front();
        } else {
          break;
        }
      }
      if let Some(&j) = dq.front() {
        if dp[j] < i32::MAX {
          let pi_minus1 = if i >= 1 { p[i - 1] } else { 0 };
          dp[i] = dp[j] - p[j] + 2 + pi_minus1;
        }
      }
      // Maintain monotone deque: remove back if dp[back]-P[back] >= dp[i]-P[i]
      if dp[i] < i32::MAX {
        let val_i = dp[i] - p[i.min(n - 1)];
        while let Some(&j) = dq.back() {
          if dp[j] == i32::MAX || dp[j] - p[j.min(n - 1)] >= val_i {
            dq.pop_back();
          } else {
            break;
          }
        }
        dq.push_back(i);
      }
    }
    dp[n]
  }
}