Is Minimum Discards to Balance Inventory easy or hard?

The problem is typically rated Medium because the logic is simple once the sliding window pattern is recognized, but identifying the correct window constraint and maintaining counts efficiently requires experience with frequency-based window problems.

Minimum Discards to Balance Inventory Python/Java solution

Implement the sliding window using a dictionary or HashMap to track frequencies. Move the right pointer to include items and update counts, and move the left pointer whenever the balance rule is violated. The logic is identical across Python, Java, C++, Go, and TypeScript, differing mainly in the syntax for hash maps.

How to solve Minimum Discards to Balance Inventory in O(n)?

Maintain two pointers representing a sliding window and track item frequencies using a hash map. Expand the right pointer while updating counts. If the inventory violates the balance condition, move the left pointer forward and decrease counts until the constraint is restored. Track the maximum valid window size and compute the minimum discards as total length minus that size.

What is the best approach for Minimum Discards to Balance Inventory?

The optimal approach uses a sliding window with a hash table to maintain item frequencies while scanning the array. The window expands and shrinks to ensure the inventory remains balanced. This method finds the longest valid segment and computes discards as n minus the window size. Time complexity is O(n) with O(k) additional space for frequency counts.

Is Minimum Discards to Balance Inventory asked at Google/Amazon/Meta?

Sliding window and frequency-count problems similar to this appear frequently in interviews at companies like Amazon, Google, and Meta. Variants often involve longest valid subarray problems, balanced frequency constraints, or minimizing removals. Interviewers expect candidates to recognize the sliding window pattern quickly.

What data structure is used in Minimum Discards to Balance Inventory?

The main data structure is a hash table (or dictionary) that stores the frequency of each inventory item within the current window. Combined with two pointers for the sliding window, this allows constant-time updates and checks while scanning the array.

What is the time complexity of Minimum Discards to Balance Inventory?

The optimal sliding window solution runs in O(n) time because each element enters and leaves the window at most once. Frequency updates and hash map lookups are constant time on average. Space complexity is O(k), where k is the number of distinct inventory items tracked in the window.

Description Hints 4 Solution Video 15:53

3679. Minimum Discards to Balance Inventory

Medium35.5% acceptance

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 <= 10⁵
1 <= arrivals[i] <= 10⁵
1 <= w <= arrivals.length
1 <= m <= w

Topics

Hints open one at a time

Hint 1

Use a sliding window of up to w days with two pointers left and right to represent the current interval.

Hint 2

Maintain a hash map cnt from item type to its current count in the window. When you advance right to day i, do cnt[arrivals[i]]++.

Hint 3

If the window size exceeds w (i.e. right - left + 1 > w), shrink it by doing cnt[arrivals[left]]-- and then left++.

Hint 4

After each increment, check if cnt[arrivals[right]] > m. If so, we must discard the current arrival.

15:53

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minArrivalsToDiscard(self, arrivals: List[int], w: int, m: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,1,3,1]
4
2

Input

[1,2,3,3,3,4]
3
2

Your code is saved on this device.Solution