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 752 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |