You are given two integers w and m, and an integer array arrivals, where arrivals[i] represents the type of item arriving on day i (days are 1-indexed).

Items follow these management rules:

• When an item arrives, you must decide immediately whether to keep it or discard it. An item can only be discarded on the exact day it arrives — you cannot remove it later.
• For every day i, look at the sliding window of the last w days: [max(1, i - w + 1), i].
  • Within any such window, each item type can appear at most m times among the kept items.
  • If keeping the item arriving on day i would push its type's count in the window above m, then that item must be discarded.

Your task is to return the minimum number of arrivals that need to be discarded so that every w-day window contains at most m kept items of each type.

In other words, as items arrive one by one, you maintain a sliding window of size w. Whenever a newly arriving item would cause its type to exceed the limit m within the current window, you have no choice but to throw it away. You need to count how many items end up being discarded.

Key points to understand:

1. The decision is made online: each item is processed in order, and once kept, it stays in the window until it slides out naturally after w days.
2. Discarded items do not count toward the window's type counts — only kept items matter.
3. The greedy strategy of keeping an item whenever possible is optimal: keeping an earlier item never hurts, because it leaves the window sooner than any later item of the same type would, freeing up capacity earlier.

Example walkthrough:

Suppose arrivals = [1, 2, 1, 1], w = 3, m = 1:

• Day 1: type 1 arrives. Window [1,1] has zero kept items of type 1, so keep it.
• Day 2: type 2 arrives. Window [1,2] has no type 2, so keep it.
• Day 3: type 1 arrives. Window [1,3] already contains one kept type 1 (from day 1), so this item must be discarded.
• Day 4: type 1 arrives. Window [2,4] — the item from day 1 has slid out, and the day-3 item was discarded, so type 1 count is 0. Keep it.

Total discarded: 1.

The solution simulates this process with a counter cnt tracking kept items per type in the current window, and a marked array recording which items were kept, so counts can be correctly decremented when items slide out of the window.

The first thing to notice is that the problem statement itself almost forces our hand: when an arriving item would make its type exceed m in the current window, it must be discarded — there's no decision to make in that moment. So the only real question is: should we ever voluntarily discard an item that could legally be kept, hoping it saves more items later?

The answer is no, and here's the key insight why.

Consider two items of the same type — one arriving earlier, one arriving later. The earlier item entered the window sooner, which means it will also leave the window sooner. If we're choosing which occurrences of a type to keep, an earlier item "occupies" a slot for less remaining time than a later one would. So keeping items as early as possible frees up capacity at the earliest possible moment, which can never be worse for future arrivals.

Put differently: suppose an optimal solution discards some item A that could have been kept, and later keeps an item B of the same type. We can always swap the choice — keep A and discard B instead — without ever violating the window constraint, because A exits every window no later than B does. The total number of discards stays the same. This exchange argument tells us the greedy strategy — keep every item unless the rules force a discard — is optimal.

Once we trust the greedy approach, the implementation becomes a straightforward simulation with a sliding window:

• We need to know, for each arriving item, how many kept items of the same type currently sit in the window [i - w + 1, i]. A hash map cnt tracks this.
• As the window slides forward, the item from day i - w falls out. But we must be careful: only items that were actually kept should be subtracted from the counts. Discarded items never contributed to cnt in the first place. This is exactly why we maintain the marked array — marked[j] = 1 means the item on day j was kept, so when day j exits the window we decrement cnt[arrivals[j]] by marked[j] (subtracting 0 for discarded items, 1 for kept ones).
• For the current item x: if cnt[x] >= m, keeping it would exceed the limit, so we discard it and increment the answer. Otherwise, we keep it, set marked[i] = 1, and bump cnt[x].

Each item is processed exactly once with O(1) work, giving a clean O(n) time solution with O(n) space for the marked array.

Pattern Learn more about Sliding Window patterns.

if i >= w: cnt[arrivals[i - w]] -= marked[i - w]

The subtlety here is the multiplication-by-`marked` trick: if the item on day `i - w` was **discarded**, `marked[i - w]` is `0` and the count stays unchanged — exactly right, since discarded items never counted in the first place. If it was **kept**, we subtract `1`.

**Step 2: Check the constraint for the current item.**

If the window already contains `m` kept items of type `x`, keeping one more would exceed the limit, so the item must be discarded:

```python
if cnt[x] >= m:
    ans += 1

Note that we do not set marked[i], and cnt[x] is not incremented — a discarded item leaves no trace in the window state.

Step 3: Otherwise, keep the item.

else:
    marked[i] = 1
    cnt[x] += 1

We record that the item was kept and increment its type count, so future days within the next w - 1 days will see it in their windows.

Step 4: Return the result.

After processing all arrivals, ans holds the minimum number of discards, which is guaranteed minimal by the greedy exchange argument established earlier.

Trace Example

With arrivals = [1, 2, 1, 1], w = 3, m = 1:

The answer is 1.

Complete Code

class Solution:
    def minArrivalsToDiscard(self, arrivals: List[int], w: int, m: int) -> int:
        cnt = Counter()
        n = len(arrivals)
        marked = [0] * n
        ans = 0
        for i, x in enumerate(arrivals):
            if i >= w:
                cnt[arrivals[i - w]] -= marked[i - w]
            if cnt[x] >= m:
                ans += 1
            else:
                marked[i] = 1
                cnt[x] += 1
        return ans