Minimum discards to balance inventory

Array Hash Table Sliding Window Simulation Counting

34.8% acceptance

Feb 25, 2026

You are given two integers w and m, and an integer array arrivals, where arrivals[i] is the type of item arriving on day i (days are 1-indexed). Items are managed according to the following rules: Each arrival may be kept or discarded; an item may only be discarded on its arrival day. For each day i, consider the window of days [max(1, i - w + 1), i] (the w most recent days up to day i): For any such window, each item type may appear at most m times among kept arrivals whose arrival day lies in that window. If keeping the arrival on day i would cause its type to appear more than m times in the window, that arrival must be discarded. Return the minimum number of arrivals to be discarded so that every w-day window contains at most m occurrences of each type.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn min_arrivals_to_discard(arrivals: Vec<i32>, w: i32, m: i32) -> i32 {
    use std::collections::HashMap;
    let n = arrivals.len();
    let w = w as usize;
    let m = m as usize;
    // For each type, maintain a deque of the days (indices) when it was kept.
    // When a new arrival of type t comes on day i:
    //   1. Remove from deque all days < i - w + 1 (outside the window).
    //   2. If deque.len() >= m, we must discard this arrival.
    //   3. Otherwise keep it (push i to deque).
    let mut kept: HashMap<i32, std::collections::VecDeque<usize>> = HashMap::new();
    let mut discards = 0i32;
    for i in 0..n {
      let t = arrivals[i];
      let window_start = if i + 1 >= w { i + 1 - w } else { 0 };
      let dq = kept.entry(t).or_default();
      // Remove stale entries
      while dq.front().map_or(false, |&d| d < window_start) {
        dq.pop_front();
      }
      if dq.len() >= m {
        discards += 1;
      } else {
        dq.push_back(i);
      }
    }
    discards
  }
}