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 hashing interview problems — two sum, group anagrams, longest consecutive sequence, subarray sum equals k, top k frequent elements, valid anagram, isomorphic strings, word pattern, 4-sum count, and design a hashmap from scratch.
Problem 1 — Two Sum
Example
def two_sum(nums, target):
"""
Find indices of two numbers that add to target.
Hash map: value → index. O(n) time, O(n) space.
"""
seen = {}
for i, num in enumerate(nums):
complement = target - num
if complement in seen:
return [seen[complement], i]
seen[num] = i
return []
print(two_sum([2,7,11,15], 9)) # [0, 1]
print(two_sum([3,2,4], 6)) # [1, 2]
Problem 3 — Longest Consecutive Sequence
Example
def longest_consecutive(nums):
"""
Find length of longest consecutive sequence.
Hash set for O(1) membership. O(n) total.
Key insight: only start counting from the beginning of each sequence.
"""
num_set = set(nums)
max_length = 0
for n in num_set:
if n - 1 not in num_set: # n is the start of a sequence
length = 1
while n + length in num_set:
length += 1
max_length = max(max_length, length)
return max_length
print(longest_consecutive([100,4,200,1,3,2])) # 4 (1,2,3,4)
print(longest_consecutive([0,3,7,2,5,8,4,6,0,1])) # 9
Problem 4 — Subarray Sum Equals K
Example
def subarray_sum(nums, k):
"""
Count subarrays with sum exactly k.
Prefix sum + hash map. O(n) time, O(n) space.
Key: prefix_sum[j] - prefix_sum[i] = k → looking for prefix_sum[i] = prefix_sum[j] - k
"""
count = 0
prefix_sum = 0
seen = {0: 1} # prefix_sum → count (init: sum=0 seen once)
for num in nums:
prefix_sum += num
count += seen.get(prefix_sum - k, 0)
seen[prefix_sum] = seen.get(prefix_sum, 0) + 1
return count
print(subarray_sum([1,1,1], 2)) # 2 — subarrays [1,1] at [0,1] and [1,2]
print(subarray_sum([1,-1,1], 1)) # 2
Problem 5 — Top K Frequent Elements
Example
import heapq
from collections import Counter
def top_k_frequent(nums, k):
"""
Find k most frequent elements. O(n log k).
"""
freq = Counter(nums)
return heapq.nlargest(k, freq.keys(), key=lambda x: freq[x])
# Bucket sort approach — O(n):
def top_k_frequent_linear(nums, k):
freq = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for num, count in freq.items():
buckets[count].append(num)
result = []
for i in range(len(buckets) - 1, 0, -1):
result.extend(buckets[i])
if len(result) >= k:
return result[:k]
return result
print(top_k_frequent([1,1,1,2,2,3], 2)) # [1, 2]
print(top_k_frequent([1], 1)) # [1]
Problem 6 — Valid Anagram
Example
from collections import Counter
def is_anagram(s, t):
"""Check if t is an anagram of s. O(n)."""
if len(s) != len(t): return False
return Counter(s) == Counter(t)
# Manual counting approach:
def is_anagram_v2(s, t):
if len(s) != len(t): return False
count = {}
for c in s:
count[c] = count.get(c, 0) + 1
for c in t:
count[c] = count.get(c, 0) - 1
if count[c] < 0: return False
return True
print(is_anagram("anagram", "nagaram")) # True
print(is_anagram("rat", "car")) # False
Problem 7 — Isomorphic Strings
Example
def is_isomorphic(s, t):
"""
Check if s and t have the same character-to-character mapping structure.
Each unique char in s maps to exactly one unique char in t.
O(n) time, O(1) space (bounded by alphabet size).
"""
if len(s) != len(t): return False
s_to_t = {}
t_to_s = {}
for cs, ct in zip(s, t):
if cs in s_to_t:
if s_to_t[cs] != ct: return False
else:
if ct in t_to_s: return False # ct already maps to different char
s_to_t[cs] = ct
t_to_s[ct] = cs
return True
print(is_isomorphic("egg", "add")) # True (e→a, g→d)
print(is_isomorphic("foo", "bar")) # False (o can't map to both a and r)
print(is_isomorphic("paper", "title")) # True
Problem 8 — Word Pattern
Example
def word_pattern(pattern, s):
"""
Check if s follows the given pattern.
Similar to isomorphic strings but pattern is chars, s is words.
"""
words = s.split()
if len(pattern) != len(words): return False
char_to_word = {}
word_to_char = {}
for char, word in zip(pattern, words):
if char in char_to_word:
if char_to_word[char] != word: return False
else:
if word in word_to_char: return False
char_to_word[char] = word
word_to_char[word] = char
return True
print(word_pattern("abba", "dog cat cat dog")) # True
print(word_pattern("abba", "dog cat cat fish")) # False
print(word_pattern("aaaa", "dog cat cat dog")) # False
Problem 9 — 4-Sum Count (4-Array Version)
Example
def four_sum_count(nums1, nums2, nums3, nums4):
"""
Count tuples (i,j,k,l) such that nums1[i]+nums2[j]+nums3[k]+nums4[l] == 0.
Split into two pairs, use hash map. O(n²) time and space.
"""
ab_sums = {}
for a in nums1:
for b in nums2:
ab_sums[a + b] = ab_sums.get(a + b, 0) + 1
count = 0
for c in nums3:
for d in nums4:
count += ab_sums.get(-(c + d), 0)
return count
print(four_sum_count([1,2],[-2,-1],[-1,2],[0,2])) # 2
Problem 10 — Design HashMap from Scratch
Example
class MyHashMap:
"""
Implement a hash map without using any built-in hash table libraries.
Uses separate chaining.
"""
def __init__(self):
self.size = 1009 # Prime number for better distribution
self.buckets = [[] for _ in range(self.size)]
def _hash(self, key):
return key % self.size
def put(self, key: int, value: int) -> None:
idx = self._hash(key)
for i, (k, v) in enumerate(self.buckets[idx]):
if k == key:
self.buckets[idx][i] = (key, value)
return
self.buckets[idx].append((key, value))
def get(self, key: int) -> int:
idx = self._hash(key)
for k, v in self.buckets[idx]:
if k == key: return v
return -1
def remove(self, key: int) -> None:
idx = self._hash(key)
self.buckets[idx] = [(k, v) for k, v in self.buckets[idx] if k != key]
hm = MyHashMap()
hm.put(1, 1); hm.put(2, 2)
print(hm.get(1)) # 1
print(hm.get(3)) # -1
hm.put(2, 1)
print(hm.get(2)) # 1 (updated)
hm.remove(2)
print(hm.get(2)) # -1
Pattern Summary
| Problem | Hash Used | Key Insight |
|---|---|---|
| Two Sum | value → index | Complement lookup |
| Group Anagrams | sorted_str → group | Canonical form as key |
| Longest Consecutive | Set membership | Start from sequence beginnings |
| Subarray Sum = K | prefix_sum → count | Difference of prefix sums = k |
| Top K Frequent | freq counter + heap | Count then select |
| Valid Anagram | character counter | Equal frequencies |
| Isomorphic | bidirectional map | Two-way consistency check |
| Word Pattern | bidirectional map | Same as isomorphic |
| 4-Sum Count | pair_sum → count | Split problem in halves |
| Design HashMap | chaining | Prime size, linked list buckets |
The most powerful hashing pattern: Prefix sum + hash map solves a wide class of subarray problems in O(n): subarray sum = k, number of subarrays with equal 0s and 1s, longest subarray with given sum, etc.
*Hashing section complete. Next: Heaps — Heap Introduction*
Continue the lesson path
Study next in this module
01HashingHashing — Complete Introduction to Hash Tables and Hash FunctionsA complete introduction to hashing — what a hash table is, how hash functions work, why hash tables achieve O(1) average operations, the load factor, the difference between hash maps and hash sets, and real-world applications of hashing in databases, security, and caching.02HashingOpen Addressing — Linear Probing, Quadratic Probing, and Double HashingComplete guide to open addressing for hash collision resolution — linear probing with clustering analysis, quadratic probing, double hashing, tombstone deletion, the DELETED sentinel pattern, performance at different load factors, and Python dict03HashingHash Functions — Design, Properties, and Common ImplementationsA complete guide to hash functions — the mathematical properties of a good hash function, common hashing methods (division, multiplication, universal hashing), hash functions for strings and objects, cryptographic vs non-cryptographic hashes, and Python04HashingCollision Handling — Chaining vs Open Addressing Complete ComparisonMaster all collision resolution strategies for hash tables — separate chaining with linked lists, open addressing (linear probing, quadratic probing, double hashing), comparison of all methods, load factor effects, and when to use each approach.