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
Deep 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.
Why Arrays for Stacks?
When you push elements onto a stack and pop them off, you always access the most recent element. With an array-based stack:
- All elements sit in contiguous memory
- The top element is always at index
top_index - The CPU loads a cache line (64 bytes) when you access any element, bringing nearby elements into cache automatically
- Subsequent pushes/pops access this already-cached memory
With a linked list stack:
- Each node is a separate heap allocation
- Nodes are scattered in memory
- Every push/pop requires following a pointer to a random memory location
- Cache misses are frequent
For a stack processing thousands of operations per second, this cache difference matters significantly.
Complete Array Stack with Resize
Example
class ResizableArrayStack:
"""
Stack backed by a raw array with manual resize management.
Demonstrates exactly how Python's list.append() works internally.
"""
_INITIAL_CAPACITY = 8
_GROWTH_FACTOR = 2
_SHRINK_THRESHOLD = 4 # Shrink when size < capacity / 4
def __init__(self):
self._capacity = self._INITIAL_CAPACITY
self._data = [None] * self._capacity
self._top = -1
def push(self, item):
"""Push item. Resize if necessary. O(1) amortized."""
if self._top + 1 == self._capacity:
self._resize(self._capacity * self._GROWTH_FACTOR)
self._top += 1
self._data[self._top] = item
def pop(self):
"""Pop top item. Shrink if under-utilized. O(1) amortized."""
if self._top == -1:
raise IndexError("pop from empty stack")
item = self._data[self._top]
self._data[self._top] = None # Help GC, prevent memory leak
self._top -= 1
# Shrink if size dropped below 1/4 capacity
size = self._top + 1
if self._capacity > self._INITIAL_CAPACITY and size <= self._capacity // self._SHRINK_THRESHOLD:
self._resize(max(self._INITIAL_CAPACITY, self._capacity // 2))
return item
def peek(self):
if self._top == -1:
raise IndexError("peek at empty stack")
return self._data[self._top]
def is_empty(self):
return self._top == -1
def size(self):
return self._top + 1
def capacity(self):
return self._capacity
def _resize(self, new_capacity):
"""Allocate new backing array and copy elements. O(n)."""
new_data = [None] * new_capacity
for i in range(self._top + 1):
new_data[i] = self._data[i]
self._data = new_data
self._capacity = new_capacity
# print(f" [Resized: capacity → {new_capacity}]") # Uncomment to trace
def __repr__(self):
if self._top == -1:
return f"ResizableStack(empty, capacity={self._capacity})"
items = [str(self._data[i]) for i in range(self._top, -1, -1)]
return f"ResizableStack(cap={self._capacity}, size={self._top+1}): " + ", ".join(items) + " ← top"
Amortized Cost of Push with Doubling
| Operations | push(1) push(2) push(3) push(4) push(5) push(6) push(7) push(8) push(9) |
| Capacity | 8 8 8 8 8 8 8 8 16 |
| Resize occurred | No No No No No No No No YES(copy 8) |
| Cost of push | 1 1 1 1 1 1 1 1 1+8=9 |
| Cumulative cost | 1 2 3 4 5 6 7 8 17 |
| Average (amortized) | 1 1 1 1 1 1 1 1 17/9 ≈ 1.89 |
Stack Visualization During Operations
Example
def demo_array_stack():
s = ResizableArrayStack()
print("=== Push Operations ===")
for i in [10, 20, 30, 40, 50]:
s.push(i)
print(f"push({i}): {s}")
print("\n=== Peek and Pop ===")
print(f"peek(): {s.peek()}")
while not s.is_empty():
print(f"pop(): {s.pop()} | {s}")
demo_array_stack()
# push(10): ResizableStack(cap=8, size=1): 10 ← top
# push(20): ResizableStack(cap=8, size=2): 20, 10 ← top
# push(30): ResizableStack(cap=8, size=3): 30, 20, 10 ← top
# ...
# peek(): 50
# pop(): 50 | ResizableStack(cap=8, size=4): 40, 30, 20, 10 ← top
# ...
Avoiding Memory Leaks
A subtle issue: when you pop an element, you should set data[top] = None.
Example
# WRONG — potential memory leak
def pop_wrong(self):
item = self._data[self._top]
self._top -= 1 # Decrement index but data[top+1] still holds reference!
return item
# RIGHT — clear the reference
def pop_correct(self):
item = self._data[self._top]
self._data[self._top] = None # Release reference to allow garbage collection
self._top -= 1
return item
In Python, this matters when storing large objects (large arrays, complex objects). The backing array holds a reference, preventing garbage collection even though the element was "popped."
Thread-Safe Stack (Basic)
For concurrent access, use Python's threading primitives:
Example
import threading
class ThreadSafeStack:
"""
Stack safe for concurrent push/pop from multiple threads.
Uses a lock to ensure only one thread modifies the stack at a time.
"""
def __init__(self):
self._data = []
self._lock = threading.Lock()
def push(self, item):
with self._lock:
self._data.append(item)
def pop(self):
with self._lock:
if not self._data:
raise IndexError("pop from empty stack")
return self._data.pop()
def peek(self):
with self._lock:
if not self._data:
raise IndexError("peek at empty stack")
return self._data[-1]
def is_empty(self):
with self._lock:
return len(self._data) == 0
Performance Tips
1. Pre-size if you know the approximate maximum:
python example
# If you expect at most 1000 elements, pre-allocate
stack = []
stack_capacity_hint = 1000
# Not directly in Python, but in Java: new ArrayDeque<>(1000)2. Avoid clearing by recreating — just reset the top index:
python example
# Slow: creates a new list object
stack = []
# Fast: clears without reallocation
stack.clear() # Python list.clear() keeps internal buffer
# Alternative for the fixed array version:
# Just reset _top = -1, no need to overwrite array elements3. Iterating a stack:
Example
stack = [1, 2, 3, 4, 5] # 5 is top
# Iterate from top (most recent) to bottom:
for item in reversed(stack):
print(item) # 5, 4, 3, 2, 1
# Iterate from bottom to top (unusual but valid):
for item in stack:
print(item) # 1, 2, 3, 4, 5
Summary
Array-based stacks are the standard choice because:
- Cache efficiency: Contiguous memory → spatial locality → fast in practice
- Simple implementation: Single index variable (
top) tracks state - Low overhead: No pointer per element (unlike linked list)
- O(1) amortized push: Doubling strategy keeps average cost constant
Key implementation details:
- Use
top_index = -1for empty state - Always save
next = current.nextbefore overwriting (reversal) - Clear popped slots:
data[top] = Noneprevents memory leaks - Shrink when under-utilized to avoid long-term memory waste
*Next Lesson: Stack Using Linked List — Complete linked list based stack implementation, comparison with array version, and when each is appropriate.*
Continue the lesson path
Study next in this module
01StacksStack — 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.02StacksStack 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.03StacksStack Interview Problems — 10 Classic Problems with Complete SolutionsSolve 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.04StacksStack 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.