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 string interview problems — reverse words in a string, longest substring without repeating characters, minimum window substring, Roman to integer, integer to string, decode ways, word break, wildcard matching, longest common prefix, and string to integer.
Problem 1 — Reverse Words in a String
Example
def reverse_words(s):
"""
Reverse word order, handle multiple spaces.
" hello world " → "world hello"
O(n) time, O(n) space.
"""
return ' '.join(s.split()[::-1])
print(reverse_words(" hello world ")) # "world hello"
print(reverse_words("a good example")) # "example good a"
Problem 3 — Minimum Window Substring
Example
from collections import Counter
def min_window(s, t):
"""
Smallest substring of s containing all characters of t.
O(|s| + |t|) time, O(|t|) space.
"""
need = Counter(t)
missing = len(t)
best_start = best_end = 0
best_len = float('inf')
left = 0
for right, char in enumerate(s, 1):
if need[char] > 0:
missing -= 1
need[char] -= 1
if missing == 0:
while need[s[left]] < 0:
need[s[left]] += 1
left += 1
if right - left < best_len:
best_len = right - left
best_start, best_end = left, right
need[s[left]] += 1
missing += 1
left += 1
return s[best_start:best_end] if best_len < float('inf') else ""
print(min_window("ADOBECODEBANC", "ABC")) # "BANC"
print(min_window("a", "a")) # "a"
print(min_window("a", "aa")) # ""
Problem 4 — Roman to Integer
Example
def roman_to_int(s):
"""
Convert Roman numeral string to integer.
Rule: if current value < next value → subtract, else add.
O(n) time.
"""
values = {'I':1,'V':5,'X':10,'L':50,'C':100,'D':500,'M':1000}
result = 0
for i in range(len(s)):
if i + 1 < len(s) and values[s[i]] < values[s[i+1]]:
result -= values[s[i]] # Subtractive case (IV, IX, etc.)
else:
result += values[s[i]]
return result
print(roman_to_int("III")) # 3
print(roman_to_int("IV")) # 4
print(roman_to_int("IX")) # 9
print(roman_to_int("MCMXCIV")) # 1994
Problem 5 — Decode Ways
Problem: "1" → "A", "26" → "Z". How many ways to decode a digit string?
Example
def num_decodings(s):
"""
Count ways to decode string.
DP: dp[i] = ways to decode s[:i].
O(n) time, O(1) space.
"""
if not s or s[0] == '0':
return 0
prev2 = 1 # dp[i-2]
prev1 = 1 # dp[i-1]
for i in range(1, len(s)):
current = 0
# Single digit decode
if s[i] != '0':
current += prev1
# Two digit decode
two_digit = int(s[i-1:i+1])
if 10 <= two_digit <= 26:
current += prev2
prev2, prev1 = prev1, current
return prev1
print(num_decodings("12")) # 2 — "AB" or "L"
print(num_decodings("226")) # 3 — "BZ","VF","BBF"
print(num_decodings("06")) # 0 — invalid (leading zero)
Problem 6 — Word Break
Example
def word_break(s, word_dict):
"""
Can s be segmented using words from word_dict?
DP: dp[i] = True if s[:i] can be segmented.
O(n² × m) time where m = avg word length.
"""
word_set = set(word_dict)
dp = [False] * (len(s) + 1)
dp[0] = True # Empty string
for i in range(1, len(s) + 1):
for j in range(i):
if dp[j] and s[j:i] in word_set:
dp[i] = True
break
return dp[len(s)]
print(word_break("leetcode", ["leet","code"])) # True
print(word_break("applepenapple", ["apple","pen"])) # True
print(word_break("catsandog", ["cats","dog","sand","and","cat"])) # False
Problem 7 — Wildcard Matching
Example
def is_match_wildcard(s, p):
"""
Wildcard matching: '?' matches any single char, '*' matches any sequence.
DP: dp[i][j] = whether s[:i] matches p[:j].
O(m×n) time.
"""
m, n = len(s), len(p)
dp = [[False] * (n+1) for _ in range(m+1)]
dp[0][0] = True
# '*' can match empty string
for j in range(1, n+1):
if p[j-1] == '*':
dp[0][j] = dp[0][j-1]
for i in range(1, m+1):
for j in range(1, n+1):
if p[j-1] == '*':
dp[i][j] = dp[i-1][j] or dp[i][j-1] # Match char or empty
elif p[j-1] == '?' or s[i-1] == p[j-1]:
dp[i][j] = dp[i-1][j-1]
return dp[m][n]
print(is_match_wildcard("aa", "a")) # False
print(is_match_wildcard("aa", "*")) # True
print(is_match_wildcard("cb", "?a")) # False
print(is_match_wildcard("adceb", "*a*b")) # True
Problem 8 — Longest Common Prefix
Example
def longest_common_prefix(strs):
"""
Find longest prefix common to all strings.
Vertical scanning: O(n × min_length).
"""
if not strs:
return ""
for i, char in enumerate(strs[0]):
for s in strs[1:]:
if i >= len(s) or s[i] != char:
return strs[0][:i]
return strs[0] # strs[0] is the prefix
print(longest_common_prefix(["flower","flow","flight"])) # "fl"
print(longest_common_prefix(["dog","racecar","car"])) # ""
print(longest_common_prefix(["interview","integer","inter"])) # "inter"
Problem 9 — String to Integer (atoi)
Example
def my_atoi(s):
"""
Implement atoi: handle leading whitespace, sign, overflow.
O(n) time.
"""
INT_MAX, INT_MIN = 2**31 - 1, -(2**31)
i = 0
n = len(s)
# Step 1: Skip leading whitespace
while i < n and s[i] == ' ':
i += 1
# Step 2: Read sign
sign = 1
if i < n and s[i] in ('+', '-'):
sign = -1 if s[i] == '-' else 1
i += 1
# Step 3: Read digits
result = 0
while i < n and s[i].isdigit():
digit = int(s[i])
# Check overflow before adding digit
if result > (INT_MAX - digit) // 10:
return INT_MAX if sign == 1 else INT_MIN
result = result * 10 + digit
i += 1
return sign * result
print(my_atoi("42")) # 42
print(my_atoi(" -42")) # -42
print(my_atoi("4193 with words")) # 4193
print(my_atoi("words and 987")) # 0
print(my_atoi("2147483648")) # 2147483647 (overflow)
Problem 10 — Compare Version Numbers
Example
def compare_version(version1, version2):
"""
Compare version strings "1.01" vs "1.001" → equal.
Return: -1, 0, or 1
"""
v1 = version1.split('.')
v2 = version2.split('.')
# Pad shorter version with zeros
max_len = max(len(v1), len(v2))
v1 += ['0'] * (max_len - len(v1))
v2 += ['0'] * (max_len - len(v2))
for n1, n2 in zip(v1, v2):
num1, num2 = int(n1), int(n2)
if num1 < num2: return -1
if num1 > num2: return 1
return 0
print(compare_version("1.01", "1.001")) # 0 (equal)
print(compare_version("1.0", "1.0.0")) # 0
print(compare_version("0.1", "1.1")) # -1
print(compare_version("1.0.1", "1")) # 1
Pattern Summary
| Problem | Technique | Time |
|---|---|---|
| Reverse words | Split + reverse | O(n) |
| Longest no-repeat substr | Sliding window | O(n) |
| Minimum window | Sliding window + Counter | O(n) |
| Roman to int | Linear scan with rules | O(n) |
| Decode ways | 1D DP | O(n) |
| Word break | DP | O(n²) |
| Wildcard matching | 2D DP | O(mn) |
| Longest common prefix | Vertical scan | O(n×m) |
| String to integer | Linear scan | O(n) |
| Compare versions | Split + zip | O(n) |
*Strings section complete. All 155 DSA MDX files are now written with proper content.*
Continue the lesson path
Study next in this module
01StringsPattern Searching — KMP, Rabin-Karp, and Boyer-Moore AlgorithmsMaster string pattern searching algorithms — naive O(nm) approach, KMP algorithm with failure function in O(n+m), Rabin-Karp rolling hash approach, Boyer-Moore bad character rule, and when to use each algorithm. Complete implementations with detailed traces.02StringsString Matching — Longest Common Subsequence, Edit Distance, and Z-AlgorithmMaster string matching and similarity algorithms — Longest Common Subsequence (LCS) with DP, Edit Distance (Levenshtein), Longest Common Substring, Z-algorithm for pattern matching, and their applications in spell checking, DNA analysis, and diff utilities.03StringsPalindrome Problems — Check, Longest, Count, and Expand Around CenterMaster all palindrome problems — basic check with two pointers, Manacher04StringsString Operations — Complete Reference with Complexity and ImplementationComplete reference for all string operations — reversal, rotation, compression, checking palindrome, counting characters, removing duplicates, replacing characters, converting case, splitting and joining — each with implementation, time and space complexity, and edge cases.