Skip to main content
Talentd

Minimum Discards to Balance Inventory - Solution & Explanation

MediumArrayHash TableSliding WindowSimulation9 min read
Practice this problem

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] (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

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.

Solution

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:

  1. If the current day 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).
  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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force SimulationO(n²)O(k)Useful for understanding the problem or verifying constraints on small inputs
Simulation + Sliding WindowO(n)O(k)Optimal solution for large arrays where frequency constraints define a valid window

Video Solution

Minimum Discards To Balance Inventory | LeetCode 3679 | Biweekly Contest 165 • Sanyam IIT Guwahati • 789 views views

Watch 9 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Minimum Discards to Balance Inventory with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays