Design a Structure That Returns the Max of the Last k Inserted Numbers

Design a data structure that receives a stream of numbers and reports the maximum of the most recent k numbers inserted. Implement this interface:

class SlidingWindow:
 def __init__(self, k: int) -> None: ...
 def put(self, number: int) -> None: ...
 def getMax(self) -> int: ...

• SlidingWindow(k) creates an empty structure for a window of size k.
• put(number) inserts the next number of the stream.
• getMax() returns the largest of the k most recently inserted numbers.

For example, with k = 3, after put(4), put(2), put(12) and put(3), getMax() returns 12, because the last three numbers are 2, 12 and 3. After a further put(1) and put(5), it returns 5, because 12 has left the window.

Clarifying Questions

• Before k numbers have been inserted, should getMax return the maximum of everything inserted so far?
• What should getMax do when nothing has been inserted yet: raise an error or return a sentinel?
• Can numbers be negative or repeated? Is k fixed for the life of the object, and how large can it be?
• Roughly how often is getMax called compared with put?

Part 1 — A basic version

Implement a straightforward working version and analyze its time and space complexity.

What This Part Should Cover

• A correct implementation, including the cases with fewer than k numbers and with no numbers
• Time per put and per getMax
• Space as a function of the number of puts

Part 2 — Reduce space to O(k)

How do you avoid storing the whole history, so that the structure uses only O(k) space?

What This Part Should Cover

• Storage that stops growing with the number of puts
• How the oldest number is evicted on each put
• The effect of the change on the time complexity

Part 3 — Compare data structures

Compare arrays, hash maps, linked lists (including doubly linked lists) and heaps as the basis for this structure: the time and space cost of put and getMax, and the trade-offs between them.

What This Part Should Cover

• Time for put, time for getMax, and space for each structure
• Which structures find the maximum quickly and which evict the oldest number quickly, and why few do both
• When each choice is reasonable

Part 4 — The monotonic deque

Explain how a monotonic deque gives the optimal solution, implement it, and analyze its complexity.

What This Part Should Cover

• The invariant the deque maintains and why its front is the maximum
• How numbers that have left the window are detected and removed
• Amortized versus worst-case cost per operation, and the space bound