Minimum Discards to Balance Inventory - Video Solutions
Minimum Discards To Balance Inventory | LeetCode 3679 | Biweekly Contest 165
Minimum Discards to Balance Inventory - Video Solution
Watch 10 video solutions for Minimum Discards to Balance Inventory, a medium level problem involving Array, Hash Table, Sliding Window. This walkthrough by Sanyam IIT Guwahati has 789 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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](thewmost recent days up to dayi):- For any such window, each item type may appear at most
mtimes among kept arrivals whose arrival day lies in that window. - If keeping the arrival on day
iwould cause its type to appear more thanmtimes in the window, that arrival must be discarded.
- For any such window, each item type may appear at most
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
moccurrences 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 <= 1051 <= arrivals[i] <= 1051 <= w <= arrivals.length1 <= m <= w
Approach Overview
Problem 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.
Complexity Analysis
| 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 |