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 <= 1051 <= arrivals[i] <= 1051 <= w <= arrivals.length1 <= m <= wProblem Overview: You are given an array representing inventory items. The goal is to discard the minimum number of items so the remaining inventory satisfies the balance rule defined in the problem (typically keeping item counts within allowed limits). The challenge is identifying the largest valid segment to keep so the number of discarded items is minimized.
Approach 1: Brute Force Simulation (O(n²) time, O(k) space)
Start by simulating every possible subarray that could represent the remaining inventory. For each starting index, expand the range to the right and maintain a frequency map using a hash table. After every expansion, check whether the current frequencies satisfy the balancing constraint. Track the longest valid segment; the minimum discards equal n - longest_valid_length. This method is easy to reason about because it directly simulates the rule, but it becomes slow for large inputs since each subarray requires repeated counting checks.
Approach 2: Simulation + Sliding Window (O(n) time, O(k) space)
A more efficient approach keeps a dynamic window using the sliding window technique. Use two pointers (left and right) and a hash map to track item frequencies while expanding the window. As you move right, update the count of the current item. If the inventory becomes unbalanced, move left forward while decrementing counts until the constraint is satisfied again. This guarantees every element enters and leaves the window at most once, giving linear time complexity. The maximum window size encountered represents the largest balanced inventory segment, and the minimum number of discards is n - max_window.
The sliding window relies on fast frequency lookups provided by a hash table and sequential traversal of the array. Since the window only moves forward, the algorithm processes each element a constant number of times. This pattern appears frequently in problems involving longest valid subarray, frequency constraints, or streaming counts.
Recommended for interviews: The sliding window solution is what interviewers expect. Mentioning the brute force simulation first shows you understand the search space, but optimizing it with a sliding window demonstrates strong algorithmic thinking and reduces the complexity from quadratic to linear.
We use a hash map cnt to record the quantity of each item type in the current window, and an array marked to record whether each item is kept.
We iterate through the array from left to right. For each item x:
i is greater than or equal to the window size w, we subtract marked[i - w] from the count of the leftmost item in the window (if that item was kept).m, we discard the item.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.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Simulation | O(n²) | O(k) | Useful for understanding the problem or verifying constraints on small inputs |
| Simulation + Sliding Window | O(n) | O(k) | Optimal solution for large arrays where frequency constraints define a valid window |
Minimum Discards To Balance Inventory | LeetCode 3679 | Biweekly Contest 165 • Sanyam IIT Guwahati • 752 views views
Watch 9 more video solutions →Practice Minimum Discards to Balance Inventory with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor