Welcome to Subscribe On Youtube

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.

• Java
• C++
• Python
• Go
• TypeScript

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

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

• 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
  
  

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

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

All Problems

All Solutions