Min-max stack in C#: constant-time extrema

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.

C# implementation

The class separates ordinary stack contents from extremum history. Equal extrema need repeated history entries so one pop does not erase all copies.

The runner constructs the solution class and supplies standard collection namespaces and any declared node types. Arrays, lists, and class instances share references when assigned. Follow the method's exact capitalization and return type from the starter. The integer operations in this implementation are bounded; wider inputs may require long intermediates and a corresponding change to the return contract.

public class MaxMinStack {
    private readonly Stack<int> stack;

    // Stacks for internal tracking of the max/min
    private readonly Stack<int> maxValueStack;
    private readonly Stack<int> minValueStack;

    public MaxMinStack() {
        stack = new Stack<int>();
        maxValueStack = new Stack<int>();
        minValueStack = new Stack<int>();
    }

    public int Peek() {
        return stack.Peek();
    }

    public int Push(int item) {
        stack.Push(item);

        if (maxValueStack.Count == 0 || item >= GetStackMax()) {
            maxValueStack.Push(item);
        }
        if (minValueStack.Count == 0 || item <= GetStackMin()) {
            minValueStack.Push(item);
        }

        return item;
    }

    public int Pop() {
        int item = stack.Pop();

        if (item == GetStackMax()) {
            maxValueStack.Pop();
        }
        if (item == GetStackMin()) {
            minValueStack.Pop();
        }

        return item;
    }

    // Effectively a "Peek()" for the max/min values of the stack
    public int GetStackMax() {
        return maxValueStack.Peek();
    }

    public int GetStackMin() {
        return minValueStack.Peek();
    }
}

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 C# conventions and practice problems, use the C# interview guide.