LeetCode-in-Java

3679. Minimum Discards to Balance Inventory

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:

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:

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:

Item 3 on day 5 is discarded, and this is the minimum number of arrivals to discard, so return 1.

Constraints:

Solution

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;
    }
}