Monotonic Stack

Definition and Concept

Monotonic Stack Explained

Monotonic stack: specialized stack maintaining elements in strictly increasing or decreasing order. Purpose: enable efficient queries on array elements related to order. Core idea: maintain sorted sequence of candidates while processing input.

Motivation

Common problems: next greater/smaller element, histogram largest rectangle, sliding window optimization. Naive solutions: quadratic time. Monotonic stack: reduces to linear time by pruning irrelevant elements.

Basic Mechanism

Operation: push elements while preserving monotonicity. Pop elements violating order before push. Result: stack top always best candidate for query. Enables direct access to next relevant elements.

Key Properties

Monotonicity

Definition: stack elements sorted in one direction,non-increasing or non-decreasing. Ensures predictable order for comparisons. Simplifies decision making during traversal.

Uniqueness

Each element appears once. Duplicate handling: depends on strict or non-strict order. Maintains clean state to avoid redundant checks.

Stack Invariance

Invariant maintained: after processing i elements, stack contains only candidates relevant for future queries. Guarantees correctness and efficiency.

Types of Monotonic Stacks

Increasing Monotonic Stack

Stack elements strictly or non-strictly increasing from bottom to top. Usage: find next smaller element to the right or left.

Decreasing Monotonic Stack

Stack elements strictly or non-strictly decreasing from bottom to top. Usage: find next greater element to the right or left.

Variants

Variants: strict vs. non-strict monotonicity, circular arrays, dual-stack approaches. Adapts to problem constraints.

Construction and Implementation

Initialization

Initialize empty stack. Iterate over input array indices/elements. Maintain auxiliary arrays if required for results.

Iteration Process

For each element: while stack top violates monotonicity, pop. Push current element index. Maintain monotonic property throughout.

Result Extraction

During or after iteration, use stack status to determine next greater/smaller elements or other queries. Store results accordingly.

for i in range(0, n): while stack not empty and arr[stack.top()] > arr[i]: stack.pop() if stack empty: result[i] = -1 else: result[i] = stack.top() stack.push(i)

Primary Applications

Next Greater/Smaller Element

Problem: find next element larger or smaller to right/left of each element. Use monotonic stack to achieve O(n) time.

Largest Rectangle in Histogram

Compute largest rectangle area under histogram bars. Monotonic stack tracks indices for width and height efficiently.

Sliding Window Optimization

Maintain max/min in sliding window using monotonic queue (variant). Enables O(n) computation of window extremes.

Other Uses

Applications in stock span, temperature analysis, array range queries, and dynamic programming optimizations.

Algorithmic Patterns

Push-Pop Invariants

Each element pushed once and popped once. Guarantees linear time complexity. Monotonicity guides push-pop decisions.

Directional Traversal

Left-to-right or right-to-left traversal chosen based on problem. Determines whether stack tracks next greater or smaller element.

Index vs. Value Storage

Store indices for result referencing or values for direct comparison. Choice impacts ease of implementation.

Use with Auxiliary Arrays

Auxiliary arrays store results like next greater index or distance. Facilitates post-processing and query answering.

Time and Space Complexity

Time Complexity

Overall O(n) time: each element pushed and popped at most once. Linear scan combined with stack operations.

Space Complexity

O(n) auxiliary space: stack and result arrays. Minimal overhead relative to input size.

Comparison with Naive Methods

Naive: O(n²) for next greater/smaller queries. Monotonic stack reduces to O(n). Significant performance gain.

Comparison with Other Data Structures

Monotonic Stack vs. Segment Trees

Segment trees: support range queries with O(log n) updates. Monotonic stack: linear scan, simpler but limited query types.

Monotonic Stack vs. Balanced BST

BSTs maintain order dynamically with O(log n) operations. Monotonic stack optimized for specific linear queries.

Monotonic Stack vs. Queue

Queue orders by insertion time, monotonic stack orders by element value. Monotonic queue variant combines both.

Optimizations and Variants

Strict vs. Non-Strict Monotonicity

Strict: elements strictly increasing/decreasing. Non-strict: allow equality. Selection depends on tie-breaking rules.

Circular Arrays

Extend monotonic stack logic to circular arrays by simulating double traversal. Addresses wrap-around queries.

Dual Stack Approaches

Use two stacks to track different monotonic properties simultaneously. Useful in complex scenarios.

Memory Optimization

Reuse input array for stack indices. Minimize auxiliary arrays. Inline result computation to reduce space.

Common Problems and Examples

Next Greater Element

Given array, find for each element the next greater element to right. Classic monotonic stack application.

function nextGreater(arr): stack = empty result = array of -1 for i = 0 to n-1: while stack not empty and arr[stack.top()] < arr[i]: result[stack.top()] = arr[i] stack.pop() stack.push(i) return result

Largest Rectangle in Histogram

Find largest rectangle area under histogram bars using decreasing monotonic stack. Track indices for width calculation.

Daily Temperatures

Find how many days until warmer temperature. Use increasing stack for indices of days with unresolved temperatures.

Stock Span Problem

Calculate span of stock price days greater or equal to current price. Monotonic stack enables efficient computation.

Limitations and Constraints

Limited Query Types

Monotonic stack suited for next greater/smaller, range extrema queries. Not suited for arbitrary range queries or updates.

Input Order Dependency

Algorithm depends on linear traversal order. Random access or dynamic insertions/deletions require other structures.

Handling Duplicates

Duplicates require careful handling of strict vs. non-strict monotonicity. May complicate logic or results.

Implementation Tips and Best Practices

Use Indices Instead of Values

Store indices in stack to link to input array and results. Facilitates range calculations and output mapping.

Clear Stack Before Each Query

Reset stack for independent queries to avoid stale data. Ensures correctness in multi-query settings.

Edge Case Handling

Handle empty stack states carefully. Set default result values (-1, 0) when no next greater/smaller element exists.

Code Readability

Use descriptive variable names (stack, result, i). Comment push/pop conditions clearly. Avoid unnecessary complexity.

References

• Tarjan, R.E., "Data Structures and Network Algorithms," SIAM, vol. 44, 1983, pp. 45-67.
• Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C., "Introduction to Algorithms," MIT Press, 3rd ed., 2009, pp. 171-174.
• Knuth, D.E., "The Art of Computer Programming: Fundamental Algorithms," Addison-Wesley, vol. 1, 1997, pp. 237-240.
• Tarjan, R.E., "Amortized Computational Complexity," SIAM Journal on Algebraic and Discrete Methods, vol. 6, 1985, pp. 306-318.
• LeetCode, "Monotonic Stack Technique," Online Resource, 2020, https://leetcode.com/problems/next-greater-element/.