Medium
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:
i
, consider the window of days [max(1, i - w + 1), i]
(the w
most recent days up to day i
):
m
times among kept arrivals whose arrival day lies in that window.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.
Example 1:
Input: arrivals = [1,2,1,3,1], w = 4, m = 2
Output: 0
Explanation:
m
occurrences of this type, so we keep it.[1, 2, 1]
has item 1 twice, within limit.[1, 2, 1, 3]
has item 1 twice, allowed.[2, 1, 3, 1]
has item 1 twice, still valid.There are no discarded items, so return 0.
Example 2:
Input: arrivals = [1,2,3,3,3,4], w = 3, m = 2
Output: 1
Explanation:
[1, 2]
is fine.[1, 2, 3]
has item 3 once.[2, 3, 3]
has item 3 twice, allowed.[3, 3, 3]
has item 3 three times, exceeds limit, so the arrival must be discarded.[3, 4]
is fine.Item 3 on day 5 is discarded, and this is the minimum number of arrivals to discard, so return 1.
Constraints:
1 <= arrivals.length <= 105
1 <= arrivals[i] <= 105
1 <= w <= arrivals.length
1 <= m <= w
public class Solution {
public int minArrivalsToDiscard(int[] arrivals, int w, int m) {
int n = arrivals.length;
int dis = 0;
boolean[] removed = new boolean[n];
int maxVal = 0;
for (int v : arrivals) {
maxVal = Math.max(maxVal, v);
}
int[] freq = new int[maxVal + 1];
for (int i = 0; i < n; i++) {
int outIdx = i - w;
if (outIdx >= 0 && !removed[outIdx]) {
int oldVal = arrivals[outIdx];
freq[oldVal]--;
}
int val = arrivals[i];
if (freq[val] >= m) {
dis++;
removed[i] = true;
} else {
freq[val]++;
}
}
return dis;
}
}