Stack Patterns — DSA Pattern

The Stack Patterns pattern applies when you need parentheses matching, monotonic stack, histogram, and expression evaluation. Its time complexity is O(n) and space complexity O(n). It is used in 25 problems on Thita, including Asteroid Collision, Basic Calculator and Basic Calculator II. Common variations are Largest Rectangle in Histogram and Valid Parentheses Matching.

Master stack-based algorithms including valid parentheses, monotonic stack for next greater element, expression evaluation, and histogram problems.

Stack Patterns is pattern 6 of 16 in the Thita.ai DSA course. It covers parentheses matching, monotonic stack, histogram, and expression evaluation, split into 6 subpatterns and about 2.5 hours of study. It is one of the interview-critical patterns, so it is worth covering before your first onsite.

Subpatterns of Stack Patterns

Each subpattern below has its own theory page and problem set. They are listed in the order the course teaches them.

• Valid Parentheses Matching — Master parentheses validation and balancing using stack. Handle multiple bracket types and minimum additions. (core technique)
• Monotonic Stack — Master monotonic stack for next greater element, daily temperatures, and stock span problems. (core technique)
• Largest Rectangle in Histogram — Learn the stack-based approach to find largest rectangle in histogram and maximal rectangle in matrix. (important variation)
• Stack - Min Stack Design — Design a stack that supports push, pop, top, and retrieving minimum element in constant time. (depth topic)
• Simulation / Backtracking Helper — Use stack for simulation problems like simplify path, decode string, and asteroid collision. (depth topic)
• Expression Evaluation (RPN/Infix) — Master expression evaluation using stack. Evaluate reverse polish notation and basic calculator problems. (depth topic)

How to practise Stack Patterns on Thita.ai

Read the theory for a subpattern, then solve its problems in the browser editor. Your solution runs against the problem's test cases, and the AI coach gives a hint on the technique you are missing rather than the finished answer. Progress is tracked per subpattern, so the tracker shows which of the 6 Stack Patterns subpatterns you have covered. Topics covered here include stack patterns, stack algorithms, valid parentheses, monotonic stack, next greater element, expression evaluation, largest rectangle histogram, stack interview questions.

Related DSA patterns

• Array/Matrix Manipulation Patterns — In-place operations, hashing, prefix sums, spiral traversal, and cyclic sort.
• Linked List Manipulation Patterns — In-place reversal, merging sorted lists, reordering, and intersection detection.
• String Manipulation Patterns — Palindrome checking, anagram detection, pattern matching, and string conversion.
• Tree Traversal Patterns (DFS & BFS) — Preorder, inorder, level order traversal, LCA, and serialization.
• Heap (Priority Queue) Patterns — Top K elements, K-way merge, two heaps for median, and scheduling.
• All 16 DSA patterns
• The DSA patterns sheet
• Coding practice