Sliding-window minimum with fast add and getMin
Implement a fixed-size sliding window of integers: add(value) appends a value and, once the window exceeds size w, drops the oldest; getMin() returns the current window minimum.
Constraints:
- both operations must be sub-linear —
O(log w)per call or better, notO(w) - the window keeps insertion order so the right element is evicted
class SlidingWindowMin {
SlidingWindowMin(int w) { /* your code here */ }
void add(int value) { /* your code here */ }
int getMin() { /* your code here */ }
}Write the implementation.
Keep a TreeMap<value,count> plus a FIFO queue holding the window's values in insertion order. On add, if the window is full, poll the oldest from the queue and decrement (or remove) its count in the map; then increment the new value's count and enqueue it. getMin returns map.firstKey(). Each operation is O(log w); a monotonic deque gives amortized O(1).
- ✗Rescanning the whole window for the minimum on each
getMin, givingO(w) - ✗Using a heap and assuming its head is also the oldest element to evict
- ✗Tracking only a single current min, which breaks when that min is evicted
- →Why does a
TreeMapof value to count handle duplicate values correctly? - →How does a monotonic deque reach amortized
O(1)for this problem?
Solution
class SlidingWindowMin {
private final int w;
private final NavigableMap<Integer, Integer> counts = new TreeMap<>();
private final Deque<Integer> order = new ArrayDeque<>();
SlidingWindowMin(int w) { this.w = w; }
void add(int value) {
if (order.size() == w) { // window full — drop oldest
int old = order.poll();
counts.merge(old, -1, Integer::sum);
if (counts.get(old) == 0) counts.remove(old);
}
counts.merge(value, 1, Integer::sum); // account for the new value
order.add(value);
}
int getMin() { return counts.firstKey(); } // smallest TreeMap key
}Idea. A TreeMap keeps values sorted, so firstKey() returns the minimum in O(log w). The count handles duplicates correctly: evicting one occurrence decrements the count, and the key is removed only once the count reaches zero. The FIFO order queue records insertion order so the truly oldest element is the one evicted.
Each operation is O(log w). The optimum is a monotonic deque of indices: it reaches amortized O(1) by keeping decreasing minimum candidates, but it is harder to implement correctly with the windowing.
