DSA Notes
HubAlgorithm vs Data Structure — Key Differences, Definitions, and How They Work TogetherApplications of DSA — How Data Structures and Algorithms Power Real-World SoftwareTime and Space Complexity — A Complete BeginnerWhat is DSA? — A Complete BeginnerWhy Learn DSA? — Career Benefits, Real-World Impact, and Long-Term ValueAsymptotic Analysis — Complete Framework with Recurrence Relations and Master TheoremBest, Average, and Worst Case Analysis — A Practical Guide for Every AlgorithmBig O Notation — Complete Guide with Formal Definition, Rules, and ExamplesBig Omega Notation — Lower Bounds, Best Case, and Formal DefinitionBig Theta (Θ) Notation — Tight Bounds and Exact Growth RatesSpace Complexity — Memory Analysis, Auxiliary Space, and Time-Space TradeoffsTime Complexity Examples — 25 Worked Problems from Basic to AdvancedArray Interview Problems — 15 Classic Problems with Complete SolutionsArray Operations — Every Operation Explained with Code, Complexity, and Edge CasesArray Rotation — Algorithms, Techniques, and Interview ProblemsArray Searching — Linear Search, Binary Search, and Advanced TechniquesArrays — The Complete Introduction to the Most Fundamental Data StructureDynamic Arrays — How Python Lists and ArrayLists Work InternallyMultidimensional Arrays — 2D Arrays, Matrices, and Memory LayoutSliding Window Technique — Complete Guide with 10 Classic ProblemsAnagram Problems — Detection, Grouping, and Sliding Window VariationsPalindrome Problems — Check, Longest, Count, and Expand Around CenterPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsString Interview Problems — 10 Classic Problems with Complete SolutionsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmString Operations — Complete Reference with Complexity and ImplementationStrings — Complete Introduction to String Data Structure and OperationsCircular Linked List — Structure, Operations, and ApplicationsDoubly Linked List — Complete Implementation with Bidirectional OperationsLinked List Interview Problems — 12 Classic Problems with Complete SolutionsLinked Lists — A Complete Introduction with Memory Model and TypesLinked List Operations — Every Technique with Code and ComplexityReverse Linked List — All Approaches from Basic to AdvancedSingly Linked List — Complete Implementation with All OperationsBalanced Parentheses — Stack-Based Validation with All VariantsInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationStack Implementation — Three Complete Implementations with Edge CasesStack Interview Problems — 10 Classic Problems with Complete SolutionsStack — Complete Introduction to LIFO Data StructureStack Using Arrays — Memory Layout, Capacity Management, and PerformanceStack Using Linked List — Implementation, Analysis, and When to Use ItCircular Queue — The Ring Buffer Explained with ImplementationDeque — Double-Ended Queue with Complete Implementation and ApplicationsPriority Queue — Complete Guide from Concept to ImplementationQueue Applications — BFS, Level-Order Traversal, 01-BFS, and MoreQueue Implementation — Array, Linked List, and Two-Stack ApproachesQueue Interview Problems — 10 Classic Problems with Complete SolutionsQueue — Complete Introduction to the FIFO Data StructureAVL Tree - Self-Balancing Binary Search TreeBinary Search Tree (BST)Binary Tree - Structure and OperationsFenwick Tree (Binary Indexed Tree)Red-Black Tree - Another Balanced BSTSegment Tree - Range Query Data StructureTree Interview Problems CollectionTree Data Structure FundamentalsTree Traversals - Inorder, Preorder, Postorder, Level OrderHeap — Complete Introduction to the Priority-Based Tree Data StructureHeap Operations — Complete Reference with Complexity AnalysisHeap Problems — 8 Classic Interview Problems with Complete SolutionsMax Heap — Complete Implementation and ApplicationsMin Heap — Complete Implementation with All OperationsPriority Queue Using Heap — Implementation, Applications, and PatternsBellman-Ford Algorithm — Shortest Path with Negative Weights and Cycle DetectionBFS Algorithm — Breadth-First Search with All Applications and VariantsDFS Algorithm — Depth-First Search with Cycle Detection and All ApplicationsDijkstraFloyd-Warshall Algorithm — All-Pairs Shortest Paths with Complete AnalysisGraph Interview Problems — 12 Classic Problems with Complete SolutionsGraph — Complete Introduction to the Most Powerful Data StructureGraph Representation — Adjacency List, Matrix, Edge List with Complete AnalysisKruskalMinimum Spanning Tree — Definition, Properties, and ApplicationsPrimShortest Path Algorithms — Complete Comparison and Selection GuideTopological Sorting — DFS and BFS (KahnUnion-Find (DSU) in Graphs — Connected Components and Dynamic ConnectivitySeparate Chaining — Complete Implementation and AnalysisCollision Handling — Chaining vs Open Addressing Complete ComparisonHash Functions — Design, Properties, and Common ImplementationsHashing — Complete Introduction to Hash Tables and Hash FunctionsHashing Problems — 10 Classic Interview Problems with Complete SolutionsOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingBubble Sort — Complete Analysis with Optimizations and When to Use ItCounting Sort — O(n+k) Sorting That Breaks the Comparison Lower BoundHeap Sort — Guaranteed O(n log n) with O(1) SpaceInsertion Sort — The O(n) Best Case Sort That Powers PythonMerge Sort — Complete Guide to the Guaranteed O(n log n) Stable SortQuick Sort — The Fastest Practical Sorting Algorithm with Complete AnalysisRadix Sort — O(nk) Digit-by-Digit Sorting for Large Integer RangesSelection Sort — Complete Analysis with Swaps Minimization PropertySorting Algorithm Comparison — The Complete Decision GuideSorting — Complete Introduction to Sorting AlgorithmsBinary Search — Complete Guide with All Variants and Proof of CorrectnessInterpolation Search — O(log log n) Search for Uniformly Distributed DataLinear Search — Complete Guide with All Variants and ApplicationsSearch Algorithm Comparison — Choosing the Right Search for Every SituationSearching Interview Problems — 10 Classic Problems with Complete SolutionsTernary Search — Finding Maximum/Minimum of Unimodal FunctionsBacktracking Introduction — The Recursive Exploration with UndoRecursion Basics — The Complete BeginnerRecursion Problems — 12 Classic Problems from Basic to AdvancedRecursion Tree — Visualizing Recursion for Complexity AnalysisRecursion vs Iteration — When to Use Each and How to ConvertTail Recursion — Definition, Optimization, and Converting to IterationDP Interview Problems — 12 Classic Problems with Pattern Recognition GuideDynamic Programming — Complete Introduction with Properties and Problem IdentificationFibonacci DP — From Exponential to Linear with Memoization and Matrix ExponentiationKnapsack Problem — 0/1, Unbounded, and Fractional with Complete AnalysisLongest Common Subsequence — Complete Guide with DP Table and String VariantsLongest Increasing Subsequence — O(n log n) with Patience SortingMatrix Chain Multiplication — Interval DP with Complete AnalysisMemoization — Top-Down Dynamic Programming with CachingTabulation — Bottom-Up Dynamic Programming with Complete Table BuildingActivity Selection Problem — Greedy Scheduling with Proof of CorrectnessFractional Knapsack — Greedy by Value Density with ProofGreedy Interview Problems — 10 Classic Problems with Complete SolutionsGreedy Algorithms — Complete Introduction with Proof TechniquesHuffman Coding — Optimal Prefix-Free Data CompressionJob Sequencing Problem — Greedy Scheduling with DeadlinesBacktracking — The Complete Guide to Recursive Exploration with UndoBacktracking Problems — 12 Classic Interview Problems with Complete SolutionsN-Queens Problem — Complete Solution with Backtracking and OptimizationRat in a Maze — Backtracking Path Finding with All SolutionsSubset Generation — All Subsets, Combinations, and Partitions with BacktrackingSudoku Solver — Backtracking with Constraint PropagationCodeforces Guide — Complete Strategy to Reach 1800+ RatingCommon CP Techniques — Essential Algorithms Every Competitive Programmer Must KnowContest Strategies — How to Perform Your Best in Competitive Programming ContestsCompetitive Programming — Complete Introduction for BeginnersFast Input/Output — Why I/O Speed Matters and Complete Templates for C++ and PythonLeetCode Guide — Complete Strategy to Crack FAANG InterviewsBit Manipulation — Complete Guide with All Tricks and Interview ProblemsBloom Filter — Space-Efficient Probabilistic Membership TestingComputational Geometry — Points, Lines, Convex Hull, and Geometric AlgorithmsDisjoint Set Union (DSU) — Union-Find with Path Compression and Union by RankRandomized Algorithms — Las Vegas, Monte Carlo, and Probabilistic TechniquesSkip List — The Probabilistic Data Structure that Competes with Balanced BSTsSuffix Array — Construction, LCP Array, and String Search ApplicationsTrie Data Structure — Complete Guide with Implementation and ApplicationsAutocomplete System Using TrieLibrary Management System Using DSARoute Finder Using GraphsMini Search Engine ProjectSocial Network Analysis Using GraphsEssential Coding Patterns for InterviewsDSA Cheatsheet: Quick ReferenceEssential DSA Interview QuestionsFAANG DSA Sheet: Company-Specific Patterns and ProblemsProblem Solving Strategies for Coding InterviewsComplexity CheatsheetImportant Algorithms SummaryBest Practice Platforms for DSARecommended Books for DSA
Solve 10 classic stack interview problems with full solutions — valid parentheses, evaluate reverse polish notation, daily temperatures, next greater element, asteroid collision, largest rectangle in histogram, remove k digits, decode string, and more.
Introduction
Stack problems appear in every major technical interview. The fundamental insight that makes stacks powerful for interviews: they naturally handle "the most recent item that satisfies a condition" type of problems. Whenever you need to track context that grows and shrinks in LIFO order, a stack is likely the right tool.
Problem 2 — Evaluate Reverse Polish Notation
Problem: Evaluate the value of an arithmetic expression in Reverse Polish Notation (postfix).
Example
["2","1","+","3","*"] → ((2+1)*3) = 9
["4","13","5","/","+"] → (4+(13/5)) = 6
Example
def eval_rpn(tokens):
"""
Push numbers. When operator found, pop two operands and apply.
Time: O(n), Space: O(n)
"""
stack = []
operators = {
'+': lambda a, b: a + b,
'-': lambda a, b: a - b,
'*': lambda a, b: a * b,
'/': lambda a, b: int(a / b), # Truncate toward zero
}
for token in tokens:
if token in operators:
b = stack.pop() # Second operand (popped first)
a = stack.pop() # First operand
stack.append(operators[token](a, b))
else:
stack.append(int(token))
return stack[0]
print(eval_rpn(["2","1","+","3","*"])) # 9
print(eval_rpn(["4","13","5","/","+"])) # 6
print(eval_rpn(["10","6","9","3","+","-11","*","/","*","17","+","5","+"])) # 22
Problem 3 — Daily Temperatures
Problem: Given array temperatures, return an array answer where answer[i] is the number of days you have to wait after day i to get a warmer temperature. If no such day exists, set answer[i] = 0.
Example
[73,74,75,71,69,72,76,73] → [1,1,4,2,1,1,0,0]
Example
def daily_temperatures(temperatures):
"""
Monotonic decreasing stack: stores indices of unresolved days.
When a warmer day is found, pop and compute the gap.
Time: O(n), Space: O(n)
"""
n = len(temperatures)
result = [0] * n
stack = [] # Indices of days waiting for warmer temperature
for i, temp in enumerate(temperatures):
# Pop all days that are colder than current day
while stack and temperatures[stack[-1]] < temp:
prev_day = stack.pop()
result[prev_day] = i - prev_day # Days waited
stack.append(i) # Current day is still unresolved
return result
print(daily_temperatures([73,74,75,71,69,72,76,73]))
# [1, 1, 4, 2, 1, 1, 0, 0]
Trace:
| i=0, T=73 | stack=[0] |
| i=1, T=74: 73<74 | pop 0, result[0]=1. stack=[1] |
| i=2, T=75: 74<75 | pop 1, result[1]=1. stack=[2] |
| i=3, T=71 | stack=[2,3] |
| i=4, T=69 | stack=[2,3,4] |
| i=5, T=72: 69<72 | pop 4, result[4]=1. 71<72 → pop 3, result[3]=2. stack=[2,5] |
| i=6, T=76: 72<76 | pop 5, result[5]=1. 75<76 → pop 2, result[2]=4. stack=[6] |
| i=7, T=73 | stack=[6,7] |
Problem 4 — Next Greater Element
Problem: For each element in array, find the next element to the right that is greater. Return -1 if none exists.
Example
[2,1,2,4,3] → [4,2,4,-1,-1]
Example
def next_greater_element(nums):
"""
Monotonic stack (decreasing from bottom to top).
When we find an element greater than top, pop and assign.
Time: O(n), Space: O(n)
"""
result = [-1] * len(nums)
stack = [] # Indices
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
stack.append(i)
return result
# For circular array (NGE I variation):
def next_greater_circular(nums):
"""Next greater element in a circular array."""
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n): # Iterate twice to simulate circular
actual_i = i % n
while stack and nums[stack[-1]] < nums[actual_i]:
idx = stack.pop()
result[idx] = nums[actual_i]
if i < n:
stack.append(actual_i)
return result
print(next_greater_element([2,1,2,4,3])) # [4,2,4,-1,-1]
print(next_greater_circular([1,2,1])) # [2,-1,2]
Problem 5 — Asteroid Collision
Problem: Array of asteroids moving right (positive) or left (negative). Find the state after all collisions. Collision rule: smaller magnitude asteroid is destroyed; equal magnitudes both destroyed.
| [5,10,-5] | [5,10] (5 and 10 go right, -5 goes left, hits 10 but 10>5) |
| [8,-8] | [] (8 right, -8 left, equal — both destroyed) |
| [10,2,-5] | [10] (2 hit by -5, 2<5 dies; -5 hits 10, 10>5, -5 dies) |
Example
def asteroid_collision(asteroids):
"""
Stack holds asteroids that haven't collided yet.
Right-moving asteroids are pushed.
Left-moving asteroids may destroy top of stack (right-moving).
Time: O(n), Space: O(n)
"""
stack = []
for asteroid in asteroids:
alive = True # Current asteroid is still alive
# Collision: current is left-moving (-), stack top is right-moving (+)
while alive and asteroid < 0 and stack and stack[-1] > 0:
if stack[-1] < -asteroid:
stack.pop() # Stack asteroid smaller — it dies
elif stack[-1] == -asteroid:
stack.pop() # Equal — both die
alive = False
else:
alive = False # Current asteroid smaller — it dies
if alive:
stack.append(asteroid)
return stack
print(asteroid_collision([5,10,-5])) # [5,10]
print(asteroid_collision([8,-8])) # []
print(asteroid_collision([10,2,-5])) # [10]
print(asteroid_collision([-2,-1,1,2])) # [-2,-1,1,2] (no collisions)
Problem 6 — Largest Rectangle in Histogram
Problem: Given an array of bar heights, find the largest rectangle that can be formed.
Example
heights = [2,1,5,6,2,3]
Largest rectangle area = 10 (using bars at index 2,3 with height 5)
Example
def largest_rectangle(heights):
"""
Monotonic increasing stack.
For each bar, pop taller bars and compute the rectangle they could form.
Time: O(n), Space: O(n)
"""
stack = [] # Indices of bars in increasing height order
max_area = 0
n = len(heights)
for i in range(n + 1):
current_height = heights[i] if i < n else 0 # Sentinel 0 at end
while stack and heights[stack[-1]] > current_height:
height = heights[stack.pop()]
# Width: from stack[-1]+1 (or 0) to i-1
width = i if not stack else i - stack[-1] - 1
max_area = max(max_area, height * width)
stack.append(i)
return max_area
print(largest_rectangle([2,1,5,6,2,3])) # 10
print(largest_rectangle([2,4])) # 4
Why this works: When we pop a bar of height h at index k, the rectangle with height h extends:
- Left boundary: just after the new stack top (or from 0 if stack is empty)
- Right boundary: just before the current index i
- Width = i - stack[-1] - 1
Problem 7 — Remove K Digits
Problem: Remove k digits to make the remaining number as small as possible.
Example
num="1432219", k=3 → "1219"
num="10200", k=1 → "200"
Example
def remove_k_digits(num, k):
"""
Monotonic stack (increasing from bottom).
Remove larger digits that appear before smaller ones.
Time: O(n), Space: O(n)
"""
stack = []
for digit in num:
# Pop digits larger than current if k allows
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# If k > 0, remove from the end (already nearly sorted)
if k > 0:
stack = stack[:-k]
# Remove leading zeros and convert to string
result = ''.join(stack).lstrip('0')
return result if result else '0'
print(remove_k_digits("1432219", 3)) # "1219"
print(remove_k_digits("10200", 1)) # "200"
print(remove_k_digits("10", 2)) # "0"
Problem 8 — Decode String
Problem: Decode string where k[encoded_string] means repeat encoded_string k times.
Example
"3[a]2[bc]" → "aaabcbc"
"3[a2[c]]" → "accaccacc"
Example
def decode_string(s):
"""
Use two stacks: one for counts, one for strings built so far.
Time: O(output length), Space: O(output length)
"""
count_stack = [] # Pending repetition counts
string_stack = [] # Partially built strings
current_string = ""
current_count = 0
for char in s:
if char.isdigit():
current_count = current_count * 10 + int(char) # Multi-digit numbers
elif char == '[':
count_stack.append(current_count)
string_stack.append(current_string)
current_count = 0
current_string = ""
elif char == ']':
count = count_stack.pop()
prev_string = string_stack.pop()
current_string = prev_string + current_string * count
else:
current_string += char
return current_string
print(decode_string("3[a]2[bc]")) # "aaabcbc"
print(decode_string("3[a2[c]]")) # "accaccacc"
print(decode_string("2[abc]3[cd]ef")) # "abcabccdcdcdef"
Problem 9 — Trapping Rain Water (Stack Approach)
Problem: (Previously solved with two pointers — here is the stack-based approach.)
Example
def trap_water_stack(heights):
"""
Horizontal layers approach using a stack.
Stack stores indices of bars that might form left boundaries.
Time: O(n), Space: O(n)
"""
water = 0
stack = []
for i, height in enumerate(heights):
while stack and heights[stack[-1]] < height:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_height = min(heights[left], height) - heights[bottom]
water += width * bounded_height
stack.append(i)
return water
print(trap_water_stack([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
Problem 10 — Maximum Frequency Stack
Problem: Implement a stack that pops the most frequently occurring element. On a tie, pop the most recently pushed among the most frequent.
Example
from collections import defaultdict
class FreqStack:
"""
Track frequency of each element and the stack of elements at each frequency.
push: O(1), pop: O(1)
"""
def __init__(self):
self.freq = defaultdict(int) # element → frequency
self.group = defaultdict(list) # frequency → stack of elements
self.max_freq = 0
def push(self, val: int) -> None:
self.freq[val] += 1
f = self.freq[val]
self.max_freq = max(self.max_freq, f)
self.group[f].append(val)
def pop(self) -> int:
val = self.group[self.max_freq].pop()
self.freq[val] -= 1
if not self.group[self.max_freq]:
self.max_freq -= 1
return val
# Testing:
fs = FreqStack()
fs.push(5); fs.push(7); fs.push(5); fs.push(7); fs.push(4); fs.push(5)
print(fs.pop()) # 5 (most frequent, freq=3)
print(fs.pop()) # 7 (5 and 7 both freq=2, 7 pushed more recently)
print(fs.pop()) # 5
print(fs.pop()) # 4
The Monotonic Stack Pattern
Problems 3, 4, 6, 7 all use a monotonic stack — a stack that maintains a monotonically increasing or decreasing order of its elements.
Monotonic Decreasing: Elements in stack are in decreasing order (top = smallest). Used for "next greater element" problems.
Monotonic Increasing: Elements in stack are in increasing order (top = largest). Used for "next smaller element" and histogram problems.
Template:
Example
def monotonic_stack_template(arr):
stack = [] # Indices
result = [-1] * len(arr) # Default answer
for i in range(len(arr)):
# For monotonic decreasing: pop while top is LESS than arr[i]
while stack and arr[stack[-1]] < arr[i]:
idx = stack.pop()
result[idx] = arr[i] # arr[i] is the answer for idx
stack.append(i)
return result
Summary
| Problem | Stack Type | Key Insight |
|---|---|---|
| Valid Parentheses | Simple | Push opens, match on close |
| Evaluate RPN | Simple | Push numbers, apply on operator |
| Daily Temperatures | Monotonic decreasing | Pop when warmer day found |
| Next Greater Element | Monotonic decreasing | Pop when greater element found |
| Asteroid Collision | Simulation | Pop right-movers when hit |
| Largest Rectangle | Monotonic increasing | Pop taller bars to compute area |
| Remove K Digits | Monotonic increasing | Remove larger digits before smaller |
| Decode String | Two stacks | Count stack + string stack |
| Trap Rain Water | Monotonic | Horizontal layer computation |
| Max Frequency Stack | Multi-stack | Stack per frequency level |
*Stacks section complete. Next: Queues — Introduction*
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Stack Interview Problems — 10 Classic Problems with Complete Solutions.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Data Structures & Algorithms topic.
Search Terms
data-structures-algorithms, data structures & algorithms, data, structures, algorithms, stacks, stack, interview
Related Data Structures & Algorithms Topics
Continue learning this concept
StacksStack Implementation — Three Complete Implementations with Edge CasesComplete implementations of stacks in three ways — dynamic array (Python list), fixed-size array, and singly linked list. Each implementation handles all edge cases with error checking, includes performance analysis, and discusses when to choose each approach.StacksStack — Complete Introduction to LIFO Data StructureA thorough introduction to stacks — the LIFO (Last In, First Out) data structure. Learn the stack model, all operations with complexity, real-world applications, stack implementations using arrays and linked lists, and the fundamental programming constructs that depend on stacks.StacksStack Using Arrays — Memory Layout, Capacity Management, and PerformanceDeep dive into array-based stack implementation — internal memory layout, capacity management strategies, why arrays give better cache performance than linked lists, how to implement a stack with circular buffer optimization, and performance benchmarks.StacksStack Using Linked List — Implementation, Analysis, and When to Use ItComplete linked list stack implementation with all operations, memory analysis, comparison with array-based stack, understanding the true O(1) guarantee vs amortized O(1), and the practical scenarios where linked list stacks are preferred over array stacks.StacksBalanced Parentheses — Stack-Based Validation with All VariantsMaster the balanced parentheses problem — validating matching brackets using a stack, all variants (multiple bracket types, minimum additions to balance, longest valid substring), why stacks are the perfect data structure for bracket matching, and interview patterns.StacksInfix, Prefix, and Postfix Expressions — Stack-Based Conversion and EvaluationMaster expression notation conversion using stacks — infix to postfix (Shunting Yard algorithm), infix to prefix, postfix evaluation, prefix evaluation, why postfix and prefix are easier to evaluate than infix, operator precedence handling, and complete traced examples.