Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Stack Min Function

Problem Statement

Write a Java program that extends a stack implementation to include a min() function that returns the minimum element in the stack in O(1) time. Use an additional stack to track the minimum elements, pushing the current minimum when a new element is added and popping it when an element is removed. The program should support standard stack operations (push, pop, isEmpty) and the min function, handling integers as stack elements. Test the implementation with various sequences of push and pop operations, including edge cases like empty stacks and single-element stacks. You can visualize this as maintaining a leaderboard alongside a stack of scores, where the leaderboard always shows the lowest score at a glance without recalculating.

Input: A sequence of operations (push, pop, min) on a stack of integers (e.g., push 3, push 5, min, push 2, min, pop, min). Output: Results of operations, including the minimum element when requested (e.g., min returns 3, then 2, then 3). Constraints:

  • Stack size is between 0 and 10^5.
  • Elements are integers in the range [-10^9, 10^9].
  • The stack may be empty when min or pop is called. Example:
  • Input: Operations = [push(3), push(5), min, push(2), min, pop, min]
  • Output: [-, -, 3, -, 2, -, 3]
  • Explanation: Push 3 (min=3), push 5 (min=3), min returns 3, push 2 (min=2), min returns 2, pop 2 (min=3), min returns 3.
  • Input: Operations = [min on empty stack]
  • Output: [null]
  • Explanation: Min on empty stack returns null.

Pseudocode

CLASS MinStack
    SET dataStack to new integer array of size 1000
    SET minStack to new integer array of size 1000
    SET top to -1
    
    FUNCTION push(value)
        IF top equals dataStack length - 1 THEN
            RETURN false (stack full)
        ENDIF
        INCREMENT top
        SET dataStack[top] to value
        IF minStack is empty OR value is less than or equal to minStack[top] THEN
            PUSH value to minStack
        ENDIF
        RETURN true
    ENDFUNCTION
    
    FUNCTION pop()
        IF top equals -1 THEN
            RETURN null (stack empty)
        ENDIF
        SET value to dataStack[top]
        IF value equals minStack[top] THEN
            POP from minStack
        ENDIF
        DECREMENT top
        RETURN value
    ENDFUNCTION
    
    FUNCTION min()
        IF top equals -1 THEN
            RETURN null (stack empty)
        ENDIF
        RETURN minStack[top]
    ENDFUNCTION
    
    FUNCTION isEmpty()
        RETURN top equals -1
    ENDFUNCTION
ENDCLASS

FUNCTION testMinStack(operations)
    CREATE stack as new MinStack
    FOR each operation in operations
        IF operation.type equals "push" THEN
            CALL stack.push(operation.value)
            PRINT push result
        ELSE IF operation.type equals "pop" THEN
            SET result to stack.pop()
            PRINT popped value
        ELSE IF operation.type equals "min" THEN
            SET result to stack.min()
            PRINT minimum value
        ENDIF
    ENDFOR
ENDFUNCTION

FUNCTION main()
    SET testCases to array of operation sequences
    FOR each testCase in testCases
        PRINT test case details
        CALL testMinStack(testCase)
    ENDFOR
ENDFUNCTION

Algorithm Steps

  1. Define a MinStack class with: a. Two arrays: dataStack for values, minStack for tracking minimums. b. A top index for both stacks. c. Methods: push (add value and update minStack), pop (remove value and update minStack), min (return top of minStack), isEmpty (check if empty).
  2. In push(value): a. If stack is full, return false. b. Add value to dataStack. c. If minStack is empty or value ≤ current minimum, push value to minStack.
  3. In pop(): a. If stack is empty, return null. b. If popped value equals current minimum, pop from minStack. c. Return popped value.
  4. In min(): a. If stack is empty, return null. b. Return top of minStack.
  5. In the main method, test with sequences of push, pop, and min operations, including empty stacks and single-element cases.

Java Implementation

import java.util.*;

public class StackMinFunction {
    // MinStack class with min() function
    static class MinStack {
        private int[] dataStack;
        private int[] minStack;
        private int top;
        private static final int DEFAULT_SIZE = 1000;

        public MinStack() {
            dataStack = new int[DEFAULT_SIZE];
            minStack = new int[DEFAULT_SIZE];
            top = -1;
        }

        public boolean push(int value) {
            if (top == dataStack.length - 1) {
                return false; // Stack full
            }
            dataStack[++top] = value;
            if (top == 0 || value <= minStack[top - 1]) {
                minStack[top] = value; // Push to minStack if value is new minimum
            } else {
                minStack[top] = minStack[top - 1]; // Copy previous minimum
            }
            return true;
        }

        public Integer pop() {
            if (top == -1) {
                return null; // Stack empty
            }
            return dataStack[top--]; // Pop from dataStack, minStack follows
        }

        public Integer min() {
            if (top == -1) {
                return null; // Stack empty
            }
            return minStack[top]; // Return current minimum
        }

        public boolean isEmpty() {
            return top == -1;
        }
    }

    // Helper class for operations
    static class Operation {
        String type;
        Integer value; // For push operations

        Operation(String type, Integer value) {
            this.type = type;
            this.value = value;
        }
    }

    // Tests the MinStack with a sequence of operations
    public void testMinStack(List<Operation> operations) {
        MinStack stack = new MinStack();
        for (Operation op : operations) {
            if (op.type.equals("push")) {
                boolean success = stack.push(op.value);
                System.out.println("Push " + op.value + ": " + (success ? "Success" : "Failed"));
            } else if (op.type.equals("pop")) {
                Integer result = stack.pop();
                System.out.println("Pop: " + (result != null ? result : "null"));
            } else if (op.type.equals("min")) {
                Integer result = stack.min();
                System.out.println("Min: " + (result != null ? result : "null"));
            }
        }
    }

    // Main method to test MinStack
    public static void main(String[] args) {
        StackMinFunction tester = new StackMinFunction();

        // Test cases
        List<List<Operation>> testCases = new ArrayList<>();
        
        // Test case 1: Normal sequence
        List<Operation> case1 = Arrays.asList(
            new Operation("push", 3),
            new Operation("push", 5),
            new Operation("min", null),
            new Operation("push", 2),
            new Operation("min", null),
            new Operation("pop", null),
            new Operation("min", null)
        );
        testCases.add(case1);
        
        // Test case 2: Empty stack
        List<Operation> case2 = Arrays.asList(
            new Operation("min", null),
            new Operation("pop", null)
        );
        testCases.add(case2);
        
        // Test case 3: Single element
        List<Operation> case3 = Arrays.asList(
            new Operation("push", 1),
            new Operation("min", null)
        );
        testCases.add(case3);
        
        // Test case 4: Large sequence
        List<Operation> case4 = new ArrayList<>();
        case4.add(new Operation("push", 10));
        case4.add(new Operation("push", 5));
        case4.add(new Operation("push", 15));
        case4.add(new Operation("min", null));
        case4.add(new Operation("pop", null));
        case4.add(new Operation("min", null));
        testCases.add(case4);

        // Run test cases
        for (int i = 0; i < testCases.size(); i++) {
            System.out.println("Test case " + (i + 1) + ":");
            tester.testMinStack(testCases.get(i));
            System.out.println();
        }
    }
}

Output

Running the main method produces:

Test case 1:
Push 3: Success
Push 5: Success
Min: 3
Push 2: Success
Min: 2
Pop: 2
Min: 3

Test case 2:
Min: null
Pop: null

Test case 3:
Push 1: Success
Min: 1

Test case 4:
Push 10: Success
Push 5: Success
Push 15: Success
Min: 5
Pop: 15
Min: 5

Explanation:

  • Test case 1: Push 3 (min=3), push 5 (min=3), min returns 3, push 2 (min=2), min returns 2, pop 2 (min=3), min returns 3.
  • Test case 2: Min and pop on empty stack return null.
  • Test case 3: Push 1 (min=1), min returns 1.
  • Test case 4: Push 10 (min=10), push 5 (min=5), push 15 (min=5), min returns 5, pop 15 (min=5), min returns 5.

How It Works

  • MinStack:
    • Uses two arrays: dataStack for values, minStack for minimums.
    • push: Adds value to dataStack; pushes to minStack if value ≤ current minimum, else copies current minimum.
    • pop: Removes value from dataStack; adjusts minStack to maintain minimum.
    • min: Returns top of minStack in O(1) time.
    • isEmpty: Checks if stack is empty.
  • Example Trace (Test case 1):
    • Push 3: dataStack=[3], minStack=[3], top=0.
    • Push 5: dataStack=[3,5], minStack=[3,3], top=1.
    • Min: Returns 3.
    • Push 2: dataStack=[3,5,2], minStack=[3,3,2], top=2.
    • Min: Returns 2.
    • Pop: Removes 2, dataStack=[3,5], minStack=[3,3], top=1.
    • Min: Returns 3.
  • Main Method: Tests normal sequences, empty stacks, single elements, and larger sequences.

Complexity Analysis Table

OperationTime ComplexitySpace Complexity
PushO(1)O(1)
PopO(1)O(1)
MinO(1)O(1)
Full AlgorithmO(n)O(n)

Note:

  • n is the number of operations.
  • Time complexity: O(1) for push, pop, and min operations.
  • Space complexity: O(n) for both stacks, as each push may add to both.
  • Worst case: O(n) space for all operations, O(1) time per operation.

✅ Tip: Use an additional stack to track minimums for O(1) min queries, pushing the minimum at each step. Test with sequences that include repeated minimums to verify correctness.

⚠ Warning: Ensure both stacks are synchronized during push and pop to avoid incorrect minimums. Handle empty stack cases to prevent null pointer issues.