DSA lessons
64 pattern lessons.
Python for Interviews
The Python that interview solutions rely on: collections, heapq, sorting keys.
- Core Syntax & FunctionsEasyTypes, operators, conditionals, loops and functions that return values.
- StringsEasyIndexing, slicing, methods, splitting, joining and building strings efficiently.
- Lists, Tuples & ComprehensionsEasySequences: indexing, slicing, mutation, unpacking and comprehensions.
- Dictionaries & SetsEasyHash-based lookups: key-value maps, membership tests and set operations.
- collections: Counter, defaultdict & dequeMediumThe collections helpers interview solutions use for counting, grouping and queues.
- heapq & bisectMediumPriority queues with heapq and binary search on sorted lists with bisect.
- Sorting with Keys & LambdasMediumsorted/sort with key functions, tuple keys and small lambdas.
- Classes & ObjectsMediumClasses with state and methods: nodes, design problems and custom structures.
Core Techniques
Complexity analysis, recursion and divide & conquer: the reasoning behind every pattern.
- Complexity AnalysisEasyReason about time and space cost, including hidden loops in Python built-ins.
- Recursion & MemoisationEasySolve a problem through smaller instances of itself, and cache repeated subproblems.
- Divide & ConquerMediumSplit the input, solve the halves recursively and combine: merge sort, quickselect, counting inversions.
Arrays & Hashing
Lookups, counting, prefix sums, sorting, grids and in-place index tricks.
- Hash Map LookupEasyStore what you have seen so each new element can be answered in O(1).
- Counting & GroupingEasyFrequency maps and canonical keys to count, compare or group items.
- Prefix SumsMediumPrecompute running totals so any range sum is a subtraction.
- Sorting & Custom OrderEasySort first to expose structure, or sort by a custom key.
- Matrix TraversalMediumWalking 2-D grids: rows, columns, diagonals, spirals and in-place transforms.
- In-place Index TricksMediumUse the array itself as a hash map when values are in 1..n: cyclic sort and sign marking.
Two Pointers & Windows
Linear scans with two indices or a moving window.
- Two Pointers (Opposite Ends)EasyMove two indices toward each other on sorted or symmetric data.
- Two Pointers (Read/Write)MediumA slow write pointer and a fast read pointer for in-place filtering and partitioning.
- Sliding Window (Fixed Size)MediumMaintain an aggregate over every window of size k by adding the new element and removing the old one.
- Sliding Window (Variable Size)MediumGrow the window with the right pointer, shrink with the left until it is valid again.
Stacks & Queues
LIFO/FIFO structures and their monotonic variants.
- Stack: Matching & EvaluationEasyUse a stack for nested structure: brackets, expressions, undo.
- Monotonic StackMediumKeep a stack in sorted order to find the next greater/smaller element for all items in O(n).
- Monotonic DequeHardA deque kept in sorted order for the maximum or minimum of every sliding window.
Linked Lists
Pointer manipulation on singly linked lists.
Binary Search
Halving a sorted space or a monotonic answer range.
Trees
Traversals, BST properties, paths and construction.
- Tree DFSEasyRecursive depth-first traversal that combines results from subtrees.
- Tree BFS (Level Order)EasyProcess a tree level by level with a queue.
- Binary Search TreesMediumExploit the BST ordering invariant for search, validation and k-th smallest.
- Tree Paths & LCAHardPath sums, diameters and lowest common ancestors by returning information up the tree.
- Tree Construction & SerializationMediumRebuild a tree from traversals, or encode a tree as a string and decode it back.
Heaps
Priority queues for top-K, medians and merging.
Graphs
Traversal, ordering, connectivity and shortest paths.
- Graph DFS & ComponentsMediumDepth-first search on adjacency lists or grids: reachability, components, flood fill.
- Graph BFS & Shortest PathsMediumBreadth-first search for shortest paths in unweighted graphs and grids.
- Topological SortMediumOrder a DAG so every edge points forward; detect cycles in dependencies.
- Union-FindHardDisjoint sets with path compression to merge groups and query connectivity.
- Dijkstra's AlgorithmHardShortest paths with non-negative weights using a priority queue.
- Minimum Spanning TreeHardConnect all nodes at minimum total cost with Kruskal's or Prim's algorithm.
Backtracking
Exhaustive search with pruning.
Dynamic Programming
Optimal substructure with memoisation or tables.
- 1-D Dynamic ProgrammingMediumState depends on a single index: climbing stairs, house robber, decode ways.
- Grid Dynamic ProgrammingMediumState is a cell: unique paths, minimum path sum, maximal square.
- Knapsack & Coin ChangeHardChoose items under a capacity: 0/1 and unbounded knapsack, coin change, subset sum.
- Subsequence DPHardLIS, LCS and edit distance: state over one or two sequence prefixes.
- State-Machine DPMediumTrack a few named states per step (holding / not holding, cooldown) and transition between them.
- Interval DPHardState is a range [i, j]: palindromic subsequences, burst balloons, matrix chain.
- Bitmask DPHardState includes the set of used items encoded as bits (n ≤ 20).
- DP on TreesHardEach node returns a small tuple of states to its parent (rob/skip, cover/uncovered).
Greedy & Intervals
Locally optimal choices and interval reasoning.
String Algorithms
Palindromes and substring search.
- String Processing & ParsingEasyBuild, parse and transform strings character by character: encodings, digit arithmetic and conversions.
- PalindromesMediumExpand around centres or compare from both ends.
- Substring Search & HashingHardFind patterns efficiently with rolling hashes or prefix functions (KMP).
Advanced Data Structures
Tries, range-query trees and custom designs.
Math & Bits
Bitwise tricks and number theory.