DSA Notes
HubAlgorithm vs Data Structure - Key DifferencesReal-World Applications of DSATime and Space Complexity OverviewWhat is DSA? Data Structures and AlgorithmsWhy Learn Data Structures and AlgorithmsAsymptotic Analysis - Understanding Algorithm GrowthBest, Average, and Worst Case AnalysisBig O Notation - Upper Bound AnalysisBig Omega Notation - Lower Bound AnalysisBig Theta Notation - Tight Bound AnalysisSpace Complexity - Memory AnalysisTime Complexity Examples and AnalysisArray Interview Problems and SolutionsArray Operations - Insert, Delete, SearchArray Rotation TechniquesArray Searching TechniquesArrays - Fundamental Data StructureDynamic Arrays - Flexible SizingMultidimensional Arrays - 2D and BeyondSliding Window Technique for ArraysAnagram Problems - Character RearrangementPalindrome Problems and SolutionsPattern Searching in StringsString Interview Problems CollectionString Matching Algorithms - Pattern SearchingString Operations - Concatenation, Substring, ManipulationString Data Structure - FundamentalsCircular Linked List - Ring StructureDoubly Linked List - Bidirectional TraversalLinked List Interview ProblemsLinked List - Data Structure FundamentalsLinked List Operations - Insert, Delete, ReverseReverse Linked List - Iterative and RecursiveSingly Linked List - Implementation and OperationsBalanced Parentheses - Stack ApplicationInfix, Prefix, Postfix Expressions - Stack ApplicationStack Implementation TechniquesStack Interview Problems and SolutionsStack Data Structure - LIFO PrincipleStack using Arrays - Static ImplementationStack using Linked Lists - Dynamic ImplementationCircular Queue - Efficient Space UsageDeque (Double Ended Queue)Priority Queue - Custom OrderingQueue Applications - Real-World Use CasesQueue Implementation - Array and Linked ListQueue Interview Problems and SolutionsQueue Data Structure - FIFO PrincipleAVL 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 Data StructureHeap OperationsHeap Interview ProblemsMax-HeapMin-Heap Implementation and Use CasesPriority Queue using HeapBellman-Ford AlgorithmBreadth-First Search (BFS) AlgorithmDepth-First Search (DFS) AlgorithmDijkstra\Floyd-Warshall AlgorithmGraph Interview ProblemsGraph Data Structure FundamentalsGraph Representation MethodsKruskal\Minimum Spanning Tree (MST)Prim\Shortest Path Algorithms: Complete ComparisonTopological SortingUnion-Find (Disjoint Set Union)Separate ChainingCollision HandlingHash FunctionsHashing FundamentalsHashing Interview ProblemsOpen AddressingBubble Sort - Simple Sorting AlgorithmCounting Sort - Non-Comparison SortingHeap Sort - Heap Based SortingInsertion Sort - Build Sorted ArrayMerge Sort - Divide and ConquerQuick Sort - Partition Based SortingRadix Sort - Digit Based SortingSelection Sort - Selection Based SortingSorting Algorithms Comparison - Choosing the Right AlgorithmSorting Algorithms - Fundamentals and ConceptsBinary Search - Efficient SearchingInterpolation Search - Intelligent SearchingLinear Search - Sequential Search AlgorithmSearch Algorithms ComparisonSearching Algorithm Interview ProblemsTernary Search AlgorithmBacktracking with RecursionRecursion Fundamentals - Base Case and RecurrenceRecursion Problems and SolutionsRecursion Tree - Visualizing Function CallsRecursion vs Iteration - Comparing ApproachesTail Recursion - Optimization TechniqueDynamic Programming Interview ProblemsDynamic Programming FundamentalsFibonacci with Dynamic Programming0/1 Knapsack ProblemLongest Common Subsequence (LCS)Longest Increasing Subsequence (LIS)Matrix Chain MultiplicationMemoization (Top-Down Dynamic Programming)Tabulation (Bottom-Up Dynamic Programming)Activity Selection ProblemFractional KnapsackGreedy Interview ProblemsGreedy Algorithm FundamentalsHuffman Coding — Data Structures & AlgorithmsJob Sequencing with DeadlinesBacktracking FundamentalsBacktracking Practice ProblemsN-Queens ProblemRat in a MazeSubset GenerationSudoku SolverCodeforces Guide for Competitive ProgrammersCommon Competitive Programming TechniquesContest Strategies for Competitive ProgrammingCompetitive Programming IntroductionFast Input/Output for Competitive ProgrammingLeetCode Guide for Interview PreparationBit Manipulation - Advanced TechniquesBloom Filter - Probabilistic Data StructureComputational Geometry - Algorithms and TechniquesDisjoint Set Union (DSU) - Union FindRandomized Algorithms - Probabilistic ComputingSkip List - Probabilistic Balanced StructureSuffix Array - String IndexingTrie - Prefix Tree for Efficient SearchingAutocomplete 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
Master the top-down DP approach using recursion with caching, Python decorators, manual memoization, and understanding stack overflow risks.
What is Memoization?
Memoization is a technique where you write a recursive solution and add a cache (memory) to store results of subproblems. When the function is called with the same arguments again, it returns the cached result instead of recomputing. The name comes from "memo" — you are writing yourself a note: "I already solved this, the answer is X."
The Pattern
| Without memoization | With memoization: |
| def solve(state) | cache = {} |
| if base_case | def solve(state): |
The function structure stays the same — you just wrap it with caching. This is why memoization is often called the "lazy" approach: you only solve subproblems that are actually needed.
Python's Built-in Memoization
Python makes memoization trivial with functools.lru_cache:
python example
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
print(fib(100)) # Instant! Without cache: would take billions of yearsThe @lru_cache(maxsize=None) decorator automatically caches all results. With maxsize=None, it caches unlimited entries (use a number to limit memory).
Manual Memoization
For more control or in languages without decorator support:
Example
def fib_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
# Or with explicit dictionary:
def solve(n):
memo = {}
def dp(i):
if i in memo:
return memo[i]
if i <= 1:
return i
memo[i] = dp(i-1) + dp(i-2)
return memo[i]
return dp(n)
C++ Memoization Pattern
Example
#include <unordered_map>
using namespace std;
unordered_map<int, long long> memo;
long long fib(int n) {
if (n <= 1) return n;
if (memo.count(n)) return memo[n];
return memo[n] = fib(n-1) + fib(n-2);
}
// For 2D state (e.g., knapsack):
map<pair<int,int>, int> memo2d;
int knapsack(vector<int>& wt, vector<int>& val, int i, int W) {
if (i < 0 || W <= 0) return 0;
auto key = make_pair(i, W);
if (memo2d.count(key)) return memo2d[key];
int skip = knapsack(wt, val, i-1, W);
int take = 0;
if (wt[i] <= W)
take = val[i] + knapsack(wt, val, i-1, W - wt[i]);
return memo2d[key] = max(skip, take);
}
Real Example: Minimum Cost Climbing Stairs
Example
from functools import lru_cache
def min_cost_climbing(cost):
n = len(cost)
@lru_cache(maxsize=None)
def dp(i):
if i <= 1:
return cost[i]
return cost[i] + min(dp(i-1), dp(i-2))
return min(dp(n-1), dp(n-2))
# cost[i] = cost to step on stair i
print(min_cost_climbing([10, 15, 20])) # 15 (step on index 1, then jump to top)
Stack Overflow Risk
The biggest danger of top-down DP is stack overflow. Each recursive call adds a frame to the call stack. For problems with deep recursion (n > 1000 in Python, ~10000 in C++), you will crash.
Python Solution: Increase recursion limit
python example
import sys
sys.setrecursionlimit(10**6) # Default is 1000But this is a band-aid. For very deep recursion (n > 10^5), switch to bottom-up tabulation.
Alternative: Iterative DFS with explicit stack
Example
def fib_iterative_memo(n):
"""Simulate recursion with explicit stack to avoid stack overflow."""
memo = {0: 0, 1: 1}
stack = [n]
while stack:
x = stack[-1]
if x in memo:
stack.pop()
continue
if x-1 not in memo:
stack.append(x-1)
continue
if x-2 not in memo:
stack.append(x-2)
continue
memo[x] = memo[x-1] + memo[x-2]
stack.pop()
return memo[n]
When to Use Memoization vs Tabulation
Prefer memoization when:
- Not all subproblems need to be solved (sparse state space)
- Natural recursive structure is clear
- Hard to determine computation order for tabulation
- Problem is easier to think about top-down
Prefer tabulation when:
- All subproblems will be needed
- Deep recursion would cause stack overflow
- Space optimization is desired (rolling array)
- You want iterative code (easier to debug)
Complexity Analysis
For memoized Fibonacci:
- Time: O(n) — each state computed exactly once, n states total
- Space: O(n) — cache stores n results + O(n) recursion stack
Key insight: memoization transforms exponential recursion into polynomial DP by ensuring each unique subproblem is solved only once.
Common Mistakes
- Forgetting base cases: Infinite recursion without proper termination
- Mutable default arguments: In Python,
def f(memo={})shares the dict across calls. UseNonedefault and initialize inside. - Wrong cache key: For 2D DP, cache key must include ALL state variables
- Not clearing cache: Between test cases in competitive programming, clear the memo
- Cache too large: For very large state spaces, consider tabulation with space optimization
Memoization with Multiple Arguments
Example
@lru_cache(maxsize=None)
def lcs(s1, s2, i, j):
"""Longest Common Subsequence with memoization."""
if i < 0 or j < 0:
return 0
if s1[i] == s2[j]:
return 1 + lcs(s1, s2, i-1, j-1)
return max(lcs(s1, s2, i-1, j), lcs(s1, s2, i, j-1))
Note: lru_cache requires hashable arguments. Lists and dicts cannot be used as arguments — convert to tuples.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Memoization (Top-Down Dynamic Programming).
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, dynamic, programming, memoization
Related Data Structures & Algorithms Topics
Continue learning this concept
Dynamic ProgrammingDynamic Programming Interview ProblemsMaster essential DP interview problems: coin change, edit distance, rod cutting, climbing stairs, and house robber with clear approaches and solutions.Dynamic ProgrammingDynamic Programming FundamentalsUnderstand the core principles of dynamic programming: overlapping subproblems, optimal substructure, and how DP differs from divide-and-conquer and greedy approaches.Dynamic ProgrammingFibonacci with Dynamic ProgrammingSee how DP transforms Fibonacci from exponential O(2^n) naive recursion to O(n) memoization, O(n) tabulation, and O(1) space-optimized solution.Dynamic Programming0/1 Knapsack ProblemMaster the classic 0/1 Knapsack problem with 2D DP table construction, include/exclude decisions, solution traceback, and space optimization.Dynamic ProgrammingLongest Common Subsequence (LCS)Master the LCS problem with 2D DP table construction, backtracking for the actual subsequence, and its application in diff utilities.Dynamic ProgrammingLongest Increasing Subsequence (LIS)Solve LIS with O(n\u00b2) DP approach and the optimal O(n log n) patience sorting algorithm, with complete analysis and code.