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
Master all anagram-related problems — checking if two strings are anagrams, grouping anagrams together, finding all anagram substrings in a text (sliding window), minimum characters to form anagram, and the frequency array optimization for fixed alphabets.
What Is an Anagram?
Two strings are anagrams if one is a rearrangement of the other — they contain the same characters with the same frequencies.
| "listen" and "silent" | anagrams |
| "anagram" and "nagaram" | anagrams |
| "hello" and "world" | not anagrams |
2. Group Anagrams Together
Example
from collections import defaultdict
def group_anagrams(strs):
"""
Group strings that are anagrams of each other.
Key: sorted string (canonical form). O(n × m log m)
"""
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # "eat" → ('a','e','t')
groups[key].append(s)
return list(groups.values())
def group_anagrams_fast(strs):
"""
Faster key: char count array. O(n × m)
"""
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s: count[ord(c) - ord('a')] += 1
key = tuple(count) # (1,0,0,...,1,...) for "aet"
groups[key].append(s)
return list(groups.values())
print(group_anagrams(["eat","tea","tan","ate","nat","bat"]))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]
3. Find All Anagrams in a String — Sliding Window
Example
def find_anagrams(s, p):
"""
Return all start indices of anagrams of p in s.
Sliding window with frequency comparison. O(n) time.
"""
result = []
if len(p) > len(s):
return result
p_count = Counter(p)
window = Counter(s[:len(p)]) # Initial window
if window == p_count:
result.append(0)
for i in range(len(p), len(s)):
# Add new right character
window[s[i]] += 1
# Remove leftmost character
left_char = s[i - len(p)]
window[left_char] -= 1
if window[left_char] == 0:
del window[left_char]
if window == p_count:
result.append(i - len(p) + 1)
return result
print(find_anagrams("cbaebabacd", "abc")) # [0, 6]
print(find_anagrams("abab", "ab")) # [0, 1, 2]
Optimized — Track Difference Count
Example
def find_anagrams_v2(s, p):
"""
More efficient: track 'differ' count instead of full comparison.
"""
result = []
n, m = len(s), len(p)
if n < m: return result
p_freq = [0] * 26
w_freq = [0] * 26
for c in p: p_freq[ord(c)-97] += 1
for c in s[:m]: w_freq[ord(c)-97] += 1
differ = sum(1 for i in range(26) if p_freq[i] != w_freq[i])
if differ == 0: result.append(0)
for i in range(m, n):
# Add right character
r = ord(s[i]) - 97
if w_freq[r] == p_freq[r]: differ += 1
w_freq[r] += 1
if w_freq[r] == p_freq[r]: differ -= 1
# Remove left character
l = ord(s[i-m]) - 97
if w_freq[l] == p_freq[l]: differ += 1
w_freq[l] -= 1
if w_freq[l] == p_freq[l]: differ -= 1
if differ == 0: result.append(i - m + 1)
return result
4. Minimum Characters to Make Anagram
Example
def min_steps_to_anagram(s, t):
"""
Minimum characters to change in s to make it an anagram of t.
"""
freq_s = Counter(s)
freq_t = Counter(t)
changes = 0
for char in freq_t:
diff = freq_t[char] - freq_s.get(char, 0)
if diff > 0:
changes += diff
return changes
print(min_steps_to_anagram("leetcode", "practice")) # 5
print(min_steps_to_anagram("anagram", "mangaar")) # 0
5. Palindrome Permutation Check
python example
def can_form_palindrome(s):
"""
Check if any permutation of s can be a palindrome.
At most one character can have odd frequency.
"""
freq = Counter(s)
odd_count = sum(1 for count in freq.values() if count % 2 != 0)
return odd_count <= 1
print(can_form_palindrome("aab")) # True — "aba"
print(can_form_palindrome("code")) # False
print(can_form_palindrome("carerac")) # True — "racecar"Pattern Summary
| Problem | Technique | Time | Space |
|---|---|---|---|
| Is anagram? | Counter comparison | O(n) | O(1)* |
| Group anagrams | Sorted key hash map | O(nm log m) | O(nm) |
| Find anagram substrings | Sliding window | O(n) | O(1)* |
| Min changes for anagram | Counter difference | O(n) | O(1)* |
| Can form palindrome | Count odd frequencies | O(n) | O(1)* |
*O(1) space when alphabet size is fixed (26 lowercase letters)
*Next: String Interview Problems*
Continue the lesson path
Study next in this module
01StringsPalindrome Problems — Check, Longest, Count, and Expand Around CenterMaster all palindrome problems — basic check with two pointers, Manacher02StringsPattern 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.03StringsString Interview Problems — 10 Classic Problems with Complete SolutionsSolve 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.04StringsString 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.