LeetCode Problem 3679

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Sliding Window, Simulation, Counting

Solution

LeetCode 3679 - Minimum Discards to Balance Inventory

Problem Understanding

This problem models a stream of arriving items. On each day, exactly one item arrives, and each item has a type represented by an integer.

We are given two parameters:

• w, the size of the sliding window.
• m, the maximum number of times any item type may appear within a window.

For every day i, we consider the window of the most recent w days:

$$[\max(1, i-w+1), i]$$

Among the arrivals whose days fall inside that window, we only count the arrivals that were kept. Discarded arrivals do not contribute to the count.

The rule is that for every such window, each item type must appear at most m times among the kept arrivals.

A crucial detail is that discarding decisions are made online. When an item arrives on day i, if keeping it would cause its type to exceed m occurrences within the current w-day window, then that arrival must be discarded.

The goal is to compute the minimum number of arrivals that must be discarded.

The array length can be as large as 100,000, which immediately rules out any algorithm that repeatedly scans windows or recomputes frequencies from scratch. We need a solution that processes arrivals efficiently, ideally in linear time.

Several edge cases are worth noticing:

• When m == w, no item can ever violate the constraint because a type cannot appear more than w times inside a window of size w.
• When m == 1, every window may contain at most one kept occurrence of each type.
• A single type may appear many times consecutively, forcing repeated discards.
• Windows near the beginning of the array are smaller than w.
• Different item types are completely independent, so the constraint for one type does not affect another type.

The key challenge is efficiently determining whether the current arrival would become the (m+1)-th kept occurrence of its type inside the current window.

Approaches

Brute Force

A straightforward approach is to simulate the process day by day.

For each arrival on day i, we could examine the entire current window and count how many kept occurrences of the same type already exist inside that window. If the count is less than m, we keep the arrival. Otherwise, we discard it.

This approach is correct because it directly implements the problem statement. However, each day may require scanning up to w positions, leading to a worst-case time complexity of:

$$O(n \cdot w)$$

Since both n and w can be as large as 100,000, this can become $10^{10}$ operations, which is far too slow.

Key Insight

The constraint only concerns occurrences of the same type.

Suppose we process arrivals from left to right. For each item type, we only need to know which kept occurrences of that type still lie within the last w days.

If we maintain a queue of kept positions for each type, then before processing day i, we remove positions that have fallen out of the window.

After that cleanup:

• The queue contains exactly the kept occurrences of that type inside the current window.
• If the queue size is already m, keeping the current arrival would create m+1 occurrences, which is illegal.
• Therefore we must discard it.
• Otherwise we keep it and append its position to the queue.

This directly follows the problem rule and allows every arrival position to enter and leave a queue at most once.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nw)	O(n)	Repeatedly scans the current window
Optimal	O(n)	O(n)	Maintains kept positions for each type using queues

Algorithm Walkthrough

1. Create a hash map that maps each item type to a queue containing the positions of its kept occurrences.
2. Initialize a counter discards = 0.
3. Process arrivals from left to right. Let the current day be i (using 1-based indexing).
4. For the current item type, retrieve its queue of kept positions.
5. Remove positions from the front of the queue while they are outside the current window. A position p is outside the window if:

$$p < i - w + 1$$

After this cleanup, the queue contains exactly the kept occurrences of that type inside the current window. 6. Check the queue size.

• If the size is already m, then keeping the current arrival would create more than m occurrences of that type in the window.
• Increment the discard counter.
• Do not add the current position to the queue.

7. Otherwise, keep the arrival and append the current day index to the queue.
8. Continue until all arrivals have been processed.
9. Return the discard counter.

Why it works

The invariant is that before processing day i, the queue for each type contains exactly the kept occurrences of that type that lie within the current w-day window.

After removing expired positions, the queue size represents the number of currently active kept occurrences of that type. If the size is already m, adding another occurrence would immediately violate the constraint, so discarding is mandatory. If the size is less than m, keeping the arrival remains valid.

Because every decision exactly matches the rule in the problem statement, and because discarded arrivals never contribute to future counts, the algorithm produces the minimum possible number of discards.

Python Solution

from collections import defaultdict, deque
from typing import List

class Solution:
    def minArrivalsToDiscard(self, arrivals: List[int], w: int, m: int) -> int:
        positions = defaultdict(deque)
        discards = 0

        for day, item_type in enumerate(arrivals, start=1):
            queue = positions[item_type]

            window_start = day - w + 1

            while queue and queue[0] < window_start:
                queue.popleft()

            if len(queue) >= m:
                discards += 1
            else:
                queue.append(day)

        return discards

The solution uses a hash map whose values are deques. Each deque stores the positions of kept occurrences for one item type.

For every arrival, we first remove outdated positions that are no longer inside the current window. This ensures the deque always reflects the active kept occurrences of that type.

After cleanup, the deque length tells us exactly how many kept occurrences currently exist within the window. If that count is already m, the new arrival must be discarded. Otherwise, we keep it by appending its position.

Because each position is inserted once and removed once, the overall runtime remains linear.

Go Solution

func minArrivalsToDiscard(arrivals []int, w int, m int) int {
	positions := make(map[int][]int)
	discards := 0

	for day, itemType := range arrivals {
		currentDay := day + 1

		queue := positions[itemType]
		windowStart := currentDay - w + 1

		for len(queue) > 0 && queue[0] < windowStart {
			queue = queue[1:]
		}

		if len(queue) >= m {
			discards++
		} else {
			queue = append(queue, currentDay)
		}

		positions[itemType] = queue
	}

	return discards
}

The Go version uses a map from item type to a slice of kept positions.

Instead of a deque, expired positions are removed by advancing the slice with queue = queue[1:]. Every position is still removed at most once, so the total work remains linear.

There are no integer overflow concerns because all indices are at most 100000, well within Go's int range.

Worked Examples

Example 1

Input:

arrivals = [1, 2, 1, 3, 1]
w = 4
m = 2

Day	Type	Queue Before Cleanup	Queue After Cleanup	Action	Queue After
1	1	[]	[]	Keep	[1]
2	2	[]	[]	Keep	[2]
3	1	[1]	[1]	Keep	[1,3]
4	3	[]	[]	Keep	[4]
5	1	[1,3]	[3]	Keep	[3,5]

No arrival is discarded.

Result:

0

Example 2

Input:

arrivals = [1, 2, 3, 3, 3, 4]
w = 3
m = 2

Day	Type	Queue Before Cleanup	Queue After Cleanup	Action	Queue After
1	1	[]	[]	Keep	[1]
2	2	[]	[]	Keep	[2]
3	3	[]	[]	Keep	[3]
4	3	[3]	[3]	Keep	[3,4]
5	3	[3,4]	[3,4]	Discard	[3,4]
6	4	[]	[]	Keep	[6]

Exactly one arrival is discarded.

Result:

1

Additional Example

Input:

arrivals = [5,5,5,5]
w = 2
m = 1

Day	Type	Active Queue	Action
1	5	[]	Keep
2	5	[1]	Discard
3	5	[]	Keep
4	5	[3]	Discard

Result:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every position enters and leaves its queue at most once
Space	O(n)	In the worst case all kept positions may be stored across all queues

Each arrival is processed exactly once. A kept position is appended once and removed once. Therefore the total number of queue operations across the entire execution is proportional to n, giving linear time complexity.

The hash map and queues may collectively store up to n kept positions in the worst case, so the space complexity is O(n).

Test Cases

from typing import List

s = Solution()

assert s.minArrivalsToDiscard([1, 2, 1, 3, 1], 4, 2) == 0  # example 1
assert s.minArrivalsToDiscard([1, 2, 3, 3, 3, 4], 3, 2) == 1  # example 2

assert s.minArrivalsToDiscard([1], 1, 1) == 0  # single element
assert s.minArrivalsToDiscard([7, 7, 7, 7], 4, 4) == 0  # limit equals window
assert s.minArrivalsToDiscard([7, 7, 7, 7], 4, 1) == 3  # only one kept

assert s.minArrivalsToDiscard([1, 1, 1, 1], 2, 1) == 2  # alternating keep/discard
assert s.minArrivalsToDiscard([1, 2, 3, 4, 5], 3, 1) == 0  # all distinct
assert s.minArrivalsToDiscard([1, 2, 1, 2, 1, 2], 3, 1) == 2  # overlapping windows

assert s.minArrivalsToDiscard([5, 5, 5, 5, 5], 2, 1) == 2  # repeated expirations
assert s.minArrivalsToDiscard([1, 1, 2, 2, 1, 1], 3, 2) == 0  # never exceeds limit

assert s.minArrivalsToDiscard([1] * 100000, 100000, 1) == 99999  # maximum stress case

Test Summary

Test	Why
[1,2,1,3,1], w=4, m=2	Official example with no discards
[1,2,3,3,3,4], w=3, m=2	Official example with one discard
[1]	Smallest possible input
[7,7,7,7], w=4, m=4	Constraint never triggered
[7,7,7,7], w=4, m=1	Maximum discarding within one window
[1,1,1,1], w=2, m=1	Repeated expiration behavior
[1,2,3,4,5], w=3, m=1	All values distinct
[1,2,1,2,1,2], w=3, m=1	Multiple types interacting
[5,5,5,5,5], w=2, m=1	Expired occurrences leave the window
[1,1,2,2,1,1], w=3, m=2	Counts remain exactly at limit
Large repeated array	Stress test for performance

Edge Cases

Window Size Equals One

When w = 1, every window contains only the current day. Since an item can appear at most once in a single-day window, no arrival can ever violate the constraint. The implementation naturally handles this because all previous positions are removed during cleanup before the count check.

Maximum Allowed Frequency

When m = w, a type can occupy every position in the window and still remain valid. A naive implementation might incorrectly discard arrivals due to off-by-one mistakes. The algorithm checks len(queue) >= m only after removing expired positions, so arrivals are discarded only when they would truly create m + 1 active occurrences.

Long Runs of the Same Type

Consider an input such as [1,1,1,1,1,1,...]. This stresses both correctness and performance. The implementation keeps only the relevant active positions in the queue and removes expired ones as the window advances. Each position is inserted and removed once, ensuring both correctness and linear runtime.

Occurrences Leaving the Window

A common source of bugs is forgetting that older occurrences stop contributing once they leave the last w days. For example, with arrivals=[5,5,5], w=2, and m=1, the occurrence from day 1 should no longer matter when processing day 3. The cleanup step removes outdated positions before making the keep-or-discard decision, ensuring the current window is evaluated correctly.

Multiple Independent Types

Different item types must be tracked separately. A global frequency count would be incorrect because the constraint applies per type. The hash map stores a dedicated queue for each type, guaranteeing that counts never interfere with one another.