3679. Minimum Discards to Balance Inventory

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.

class Solution {
public:
    int minArrivalsToDiscard(vector<int>& arrivals, int w, int m) {
        int res = 0, n = arrivals.size();
        unordered_map<int,int> freq;
        vector<bool> discarded(n);
        for(int day = 0; day < n; day++) {
            if(day >= w and !discarded[day-w]) {
                // remove stale inventory
                --freq[arrivals[day-w]];
                assert(freq[arrivals[day-w]] >= 0);
            }
            ++freq[arrivals[day]];
            if(freq[arrivals[day]] > m) {
                // remove latest item and increase discard day
                --freq[arrivals[day]];
                discarded[day] = true;
                assert(freq[arrivals[day]] == m);
                res++;
            }
        }
        return res;
    }
};