Build a stack with push, pop, peek, getStackMax, and getStackMin. Each operation should take constant time, apart from a dynamic array's occasional capacity growth. The course's push operation returns the value pushed. Tests never pop, peek, or request an extreme from an empty stack, so empty-operation behavior is outside the contract.
Keep histories of record values
An ordinary stack already supports pushing and removing the most recent value. Scanning its contents for each minimum or maximum would make those queries O(n). Instead, keep two additional stacks containing the history of minimum and maximum values that may need to be restored after later pops.
When pushing x, always push it onto the main stack. Also push it onto the maximum history when that history is empty or x is at least its top. Do the symmetric comparison for the minimum history. The tops of those histories then expose the current extrema without scanning the main stack.
Preserve duplicate extrema
Push 4, then 9, then another 9. The maximum history must contain both occurrences of 9. Popping the latest 9 should reveal the earlier 9 as the maximum. If the history recorded only strict improvements, popping once would remove the only recorded 9 and incorrectly expose 4.
The same issue occurs for repeated minima. Using >= and <= when adding history entries records duplicate records. An alternative stores a count beside each record value, but then pop must decrement that count and remove the record only when the count reaches zero.
Undo exactly the history created by a push
Pop the main value. If it equals the top of the maximum history, pop that history too. Do the same for the minimum history. A value can match both, such as the only element or a stack of equal values, so the two checks must be independent rather than an either-or branch.
For pushes [4, 9, 2, 7], the maximum history is [4, 9] and the minimum history is [4, 2]. Popping 7 changes neither history. Popping 2 removes the minimum record and restores 4. Popping 9 removes the maximum record and restores 4. These histories describe earlier stack states, not sorted copies of the whole stack.
Prove the query invariant
After every operation, each history's top equals the corresponding extreme of the main stack. A push that does not improve or equal an extreme leaves the correct top unchanged. A push that does records the new extreme. On pop, a non-record value cannot change the extreme; a record value reveals the previous valid record beneath it.
That argument depends on recording equal extrema, because one occurrence can remain after another is removed. It also depends on updating the histories during pop. Returning the last value while leaving stale history entries would make a later query report a value that no longer exists in the stack.
Costs and operation-sequence tests
Each method performs a fixed number of stack operations, giving O(1) query work and amortized O(1) pushes when backed by a growing array. The histories can each contain n entries, so storage is O(n). A strictly increasing input maximizes the maximum history, while equal values can fill both histories.
Test increasing, decreasing, repeated, and mixed positive and negative values. Alternate queries with pops so restoration is exercised, not merely initial maxima. Compare generated legal operation sequences against a simple array model whose queries use a full scan. The oracle may be slow because it runs only in tests. As a follow-up, add a middle deletion operation and explain why these history stacks no longer support it with the same constant-time guarantees.
Go implementation
The slice-backed histories remove their final elements. Queries read those final elements directly rather than iterating the stack.
The course uses the function name and concrete slice or pointer types shown here. A slice describes shared backing storage, so reslicing or passing it to a helper does not automatically copy its elements. A nil pointer is distinct from an empty slice. Keep the course's expected result shape and provide explicit copies if an adaptation must preserve mutable input.
type MaxMinStack struct {
stack []int
// Stacks for internal tracking of the max/min
maxValueStack []int
minValueStack []int
}
func Constructor() MaxMinStack {
return MaxMinStack{}
}
func (this *MaxMinStack) Peek() int {
return this.stack[len(this.stack)-1]
}
func (this *MaxMinStack) Push(item int) int {
this.stack = append(this.stack, item)
if len(this.maxValueStack) == 0 || item >= this.GetStackMax() {
this.maxValueStack = append(this.maxValueStack, item)
}
if len(this.minValueStack) == 0 || item <= this.GetStackMin() {
this.minValueStack = append(this.minValueStack, item)
}
return item
}
func (this *MaxMinStack) Pop() int {
item := this.stack[len(this.stack)-1]
this.stack = this.stack[:len(this.stack)-1]
if item == this.GetStackMax() {
this.maxValueStack = this.maxValueStack[:len(this.maxValueStack)-1]
}
if item == this.GetStackMin() {
this.minValueStack = this.minValueStack[:len(this.minValueStack)-1]
}
return item
}
// Effectively a Peek() for the max/min values of the stack
func (this *MaxMinStack) GetStackMax() int {
return this.maxValueStack[len(this.maxValueStack)-1]
}
func (this *MaxMinStack) GetStackMin() int {
return this.minValueStack[len(this.minValueStack)-1]
}
Practice this implementation
Open Max Min Stack to run the implementation against the course tests, then change one boundary condition and explain the first failing case. The editor supplies the starter signature and any node types or helper APIs used above. Copy the implementation into that environment; the snippet is the solution body, without the input parser or test driver. Your saved progress belongs to the original lesson.
For more Go conventions and practice problems, use the Go interview guide.