Skip to content

3679. Minimum Discards to Balance Inventory

Description

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.

 

Example 1:

Input: arrivals = [1,2,1,3,1], w = 4, m = 2

Output: 0

Explanation:

  • On day 1, Item 1 arrives; the window contains no more than m occurrences of this type, so we keep it.
  • On day 2, Item 2 arrives; the window of days 1 - 2 is fine.
  • On day 3, Item 1 arrives, window [1, 2, 1] has item 1 twice, within limit.
  • On day 4, Item 3 arrives, window [1, 2, 1, 3] has item 1 twice, allowed.
  • On day 5, Item 1 arrives, window [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:

  • On day 1, Item 1 arrives. We keep it.
  • On day 2, Item 2 arrives, window [1, 2] is fine.
  • On day 3, Item 3 arrives, window [1, 2, 3] has item 3 once.
  • On day 4, Item 3 arrives, window [2, 3, 3] has item 3 twice, allowed.
  • On day 5, Item 3 arrives, window [3, 3, 3] has item 3 three times, exceeds limit, so the arrival must be discarded.
  • On day 6, Item 4 arrives, window [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

Solutions

Solution 1: Simulation + Sliding Window

We use a hash map \(\textit{cnt}\) to record the quantity of each item type in the current window, and an array \(\textit{marked}\) to record whether each item is kept.

We iterate through the array from left to right. For each item \(x\):

  1. If the current day \(i\) is greater than or equal to the window size \(w\), we subtract \(\textit{marked}[i - w]\) from the count of the leftmost item in the window (if that item was kept).
  2. If the quantity of the current item in the window exceeds \(m\), we discard the item.
  3. Otherwise, we keep the item and increment its count.

Finally, the answer is the number of items discarded.

The time complexity is \(O(n)\), and the space complexity is \(O(n)\), where \(n\) is the length of the array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int minArrivalsToDiscard(int[] arrivals, int w, int m) {
        Map<Integer, Integer> cnt = new HashMap<>();
        int n = arrivals.length;
        int[] marked = new int[n];
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int x = arrivals[i];
            if (i >= w) {
                int prev = arrivals[i - w];
                cnt.merge(prev, -marked[i - w], Integer::sum);
            }
            if (cnt.getOrDefault(x, 0) >= m) {
                ans++;
            } else {
                marked[i] = 1;
                cnt.merge(x, 1, Integer::sum);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int minArrivalsToDiscard(vector<int>& arrivals, int w, int m) {
        unordered_map<int, int> cnt;
        int n = arrivals.size();
        vector<int> marked(n, 0);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int x = arrivals[i];
            if (i >= w) {
                cnt[arrivals[i - w]] -= marked[i - w];
            }
            if (cnt[x] >= m) {
                ans++;
            } else {
                marked[i] = 1;
                cnt[x] += 1;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
func minArrivalsToDiscard(arrivals []int, w int, m int) (ans int) {
    cnt := make(map[int]int)
    n := len(arrivals)
    marked := make([]int, n)
    for i, x := range arrivals {
        if i >= w {
            cnt[arrivals[i-w]] -= marked[i-w]
        }
        if cnt[x] >= m {
            ans++
        } else {
            marked[i] = 1
            cnt[x]++
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
function minArrivalsToDiscard(arrivals: number[], w: number, m: number): number {
    const cnt = new Map<number, number>();
    const n = arrivals.length;
    const marked = Array<number>(n).fill(0);
    let ans = 0;

    for (let i = 0; i < n; i++) {
        const x = arrivals[i];
        if (i >= w) {
            cnt.set(arrivals[i - w], (cnt.get(arrivals[i - w]) || 0) - marked[i - w]);
        }
        if ((cnt.get(x) || 0) >= m) {
            ans++;
        } else {
            marked[i] = 1;
            cnt.set(x, (cnt.get(x) || 0) + 1);
        }
    }
    return ans;
}

Comments