Free lessons
DSA Lessons
Every lesson in the DSA interview prep course, free to read. Each skill has a lesson that starts simple and gets technical, and a quick revise page. Practice and progress tracking need a free account.
Arrays
The array-based patterns that show up constantly in interviews and in everyday backend code: two pointers, sliding windows, prefix sums, and in-place manipulation.
Core Array Techniques
- Array Traversal BasicsIterating an array once to track a running answer (min, max, sum, count) without extra data structures.
- Two PointersUsing two indices that move toward or away from each other to avoid an inner loop, typically on sorted data.
- Sliding WindowMaintaining a running window over a contiguous range so it does not need to be rescanned from scratch on every step.
- Prefix SumsPrecomputing cumulative sums so any range-sum query answers in O(1) instead of rescanning the range.
- Kadane's AlgorithmTracking the best subarray ending at each position to find a maximum-sum contiguous subarray in one pass.
- In-Place ManipulationRearranging array elements using a slow/fast pointer pair instead of allocating a second array.
- Array HashingUsing a hash map to trade O(n) extra space for turning an O(n^2) lookup problem into O(n).
- Sorting-Based TechniquesProblems where sorting first (or a single-pass partitioning scheme like Dutch National Flag) turns a hard problem into a simple one.
- Single-Pass State TrackingCarrying one running "best so far" value forward through a single scan to decide the answer at each step.
- Lexicographic RearrangementFinding the next arrangement of a fixed set of elements in dictionary order, in place, without generating every permutation.
- Cyclic Sequence DetectionTreating an array as a function i -> nums[i] and using Floyd's tortoise-and-hare to find a cycle - and the value where it starts - in O(1) space.
- Counting via Merge SortPiggybacking a count onto the merge step of merge sort so a quantity that looks like it needs an O(n^2) comparison of every pair can be counted in O(n log n).
- Binary ExponentiationComputing x^n in O(log n) multiplications by squaring the base and only multiplying it into the result on the bits of n that are set.
Matrix Techniques
- Matrix In-Place MarkingUsing a grid's own first row and column as marker storage to avoid allocating a second grid.
- Pascal's Triangle ConstructionBuilding each row of a triangular grid from the row before it - the simplest form of bottom-up dynamic programming.
- Matrix Rotation via TransposeRotating a square matrix 90 degrees by transposing it, then reversing each row - two simple O(1)-space passes instead of tracking rotated coordinates…
- Grid Tabulation DPFilling a 2D table left-to-right, top-to-bottom, where each cell's answer is built from the cells directly above and to the left of it.
- Matrix Binary SearchTreating a row-major-sorted 2D grid as a single sorted 1D array via index math, so plain binary search applies without ever materializing that flattened…
Linked Lists
Pointer-based traversal and rewiring — the data structure behind every "reverse", "merge", or "detect a cycle" interview question.
Linked List Fundamentals
- Singly Linked List BasicsRewiring next-pointers in place — the foundational linked-list manipulation.
- Two-Pointer List TraversalWalking a linked list with two references moving at different paces or offsets - fast/slow to find the middle, or a fixed gap to find a position counted…
- Linked List Merge TechniqueBuilding a single sorted list out of two sorted lists by repeatedly taking the smaller of the two current heads, using a dummy node to avoid…
- Linked List ArithmeticSimulating grade-school addition digit by digit down two lists in parallel, carrying the overflow forward and building the result as a new list.
- Linked List IntersectionFinding the shared tail node of two lists of possibly different lengths by walking both with pointers that switch lists on reaching the end - which…
- Linked List Palindrome CheckCombining fast/slow traversal and in-place reversal to check whether a singly linked list reads the same forwards and backwards, in O(1) extra space.
- Linked List Group ReversalReversing a linked list k nodes at a time by first checking a full group exists, then reversing it and recursively wiring its tail to the…
- Linked List FlatteningMerging many independently-sorted linked lists into one sorted list by folding them together two at a time with the ordinary sorted-merge routine.
- Linked List RotationRotating a list by temporarily joining tail to head (making it circular), then breaking the circle at the correct new tail - avoiding any node-by-node…
- Linked List Deep CopyDeep-copying a list whose nodes carry an extra pointer to an arbitrary other node, by first mapping every original node to a new clone, then wiring each…
Trees
Recursive traversal of hierarchical data, the pattern behind file systems, ASTs, and decision structures.
Binary Tree Fundamentals
- Binary Tree TraversalRecursing into left and right subtrees and combining their results.
- Binary Tree DFS Traversal OrdersVisiting every node exactly once via recursion, where only the order of three fixed steps - visit the node, recurse left, recurse right - changes between…
- Morris Threaded TraversalTraversing a tree in O(1) extra space by temporarily rewiring a node's inorder predecessor to point back to it (a "thread"), using that thread to return…
- Single-Pass Triple TraversalProducing preorder, inorder, and postorder simultaneously from one iterative pass, by tracking how many times each node has been returned to on an…
- Binary Tree Height/Balance CheckComputing each subtree's height bottom-up in a single pass, and piggybacking a second computation (an imbalance check, a running diameter) onto that same…
- Binary Tree LCA SearchFinding the deepest node that has both target nodes as descendants by having each recursive call report upward whether it found either target, and letting…
- Binary Tree Boundary TraversalBuilding the outline of a tree from three independently-collected pieces - the left edge (excluding leaves), every leaf left to right, and the right edge…
- Binary Tree Mirror & SymmetryChecking whether a tree is a mirror of itself by comparing left/right subtree pairs outward-in, and separately, physically swapping every node's children…
- Binary Tree ReconstructionRebuilding a binary tree from two of its traversal orders by using preorder (or postorder) to pick off the current root value one at a time, and inorder…
- Flatten Binary Tree to Linked ListRewiring a binary tree in place into a singly linked list (via each node's right pointer, left always null) that visits nodes in preorder, by processing…
- Binary Tree Children Sum PropertyEnforcing, at every node, that its value equals the sum of its immediate children's values (with a lone child treated as contributing its own value) by…
- Binary Tree Serialize and DeserializeEncoding a tree's shape into a flat, unambiguous string by explicitly recording null children (not just present ones), so that decoding can rebuild the…
Binary Tree Views
- Binary Tree Level ViewRunning a level-order (BFS) traversal and picking out one specific piece of information per level - the first node, the last node, or the level's index…
- Binary Tree Vertical OrderingTracking each node's horizontal distance from the root (left child: -1, right child: +1) during a BFS pass, then grouping nodes into columns by that…
- Binary Tree Level LinkingConnecting every node to its next right neighbor on the same level using the previous level's already-established links as a substitute for a queue…
Binary Search Tree Operations
- BST Search and InsertLocating (or creating) a value's correct position in a BST by comparing it against the current node and moving to the left or right child accordingly…
- BST Construct From PreorderRebuilding a BST from a preorder sequence alone (no second traversal needed, unlike a general binary tree) by tracking a shrinking upper bound as…
- LCA in a BSTFinding the lowest common ancestor of two values by walking down from the root and using the ordering invariant directly: if both values are smaller, go…
- BST Inorder Successor and PredecessorFinding the next-smaller and next-larger values around a key (whether or not the key itself is in the tree) in a single root-to-leaf walk, by tracking the…
- BST Floor and CeilWalking down from the root tracking the best candidate seen so far on the correct side - the largest value not exceeding the key for floor, the smallest…
- BST Kth Smallest and LargestProducing a BST's fully sorted order via a single inorder traversal, then reading the kth-from-the-front and kth-from-the-back elements directly by index…
- Two Sum in a BSTFlattening a BST into its sorted inorder sequence, then running the classic two-pointer technique on that sorted array to find a pair summing to a target…
- BST Iterator DesignSimulating a full recursive inorder traversal one step at a time using an explicit stack that only ever holds a root-to-current-node's ancestors' left…
- Largest BST SubtreeDetermining, bottom-up, whether each subtree is itself a valid BST - and if so, its size and value range - so that a parent can decide in O(1) whether…
Graphs
Traversal (BFS/DFS) over arbitrary connections, the pattern behind dependency resolution, network reachability, and routing.
Graph Traversal Fundamentals
- Graph BFS/DFSVisiting every node reachable from a starting point, tracking what's already been visited.
- Flood-Fill TraversalRecursively (or iteratively, via an explicit stack/queue) spreading outward from a starting cell to every 4-directionally connected cell that shares its…
- Graph CloneCloning a graph reachable from a given node by traversing it once (BFS or DFS) while maintaining a map from each original node to its already-created…
- Graph Cycle DetectionDetecting a cycle by tracking, in an undirected graph, whether a visited neighbor is anything other than the edge just arrived from (since a simple…
- Topological SortRepeatedly peeling off nodes with no remaining unprocessed dependencies (in-degree zero), using a fixed tie-breaking rule wherever more than one such node…
- Graph Bipartite CheckTwo-coloring a graph by alternating colors across every edge during a BFS or DFS traversal, and declaring the graph non-bipartite the instant two adjacent…
Advanced Graph Algorithms
- Strongly Connected Components (Kosaraju's)Finding maximal groups of mutually reachable nodes in a directed graph by running DFS twice - once on the original graph to order nodes by finish time…
- Dijkstra's AlgorithmRepeatedly expanding outward from the source to whichever unfinalized node currently has the smallest known distance, using a priority queue to always…
- Bellman-Ford AlgorithmRelaxing every edge in the graph, repeated exactly (V-1) times, so that a shortest path of at most (V-1) edges (the longest a simple path can be) is…
- Floyd-Warshall AlgorithmComputing shortest paths between every pair of nodes at once via dynamic programming: considering, for each candidate "intermediate" node k in turn…
- Minimum Spanning TreeBuilding a spanning tree of minimum total edge weight by greedily adding the cheapest edge that doesn't create a cycle - either growing one tree outward…
Recursion & Backtracking
Solving a problem by branching into smaller versions of itself, the backbone of combinatorial search.
Recursion & Backtracking Fundamentals
- Backtracking: Subsets & ChoicesThe include/exclude recursive branching pattern behind subsets, permutations, and combination problems.
- Backtracking Partition EnumerationBranching over every place a string could be split, keeping only splits whose current piece satisfies a required property - producing every valid full…
- Kth Permutation by Factorial CountingComputing the kth permutation directly by figuring out, digit by digit, which remaining element the target rank must start with - using factorials to…
- Constraint Satisfaction BacktrackingFilling in unknowns one at a time, trying every locally-valid value at each position and backtracking the instant a placement violates a constraint - so…
- Grid Path BacktrackingExploring every route through a grid from a start cell to a destination, trying moves in a fixed priority order and marking cells visited for the current…
- Backtracking Permutation GenerationBuilding every permutation of a fixed set by choosing, at each position, any not-yet-used element - tracked with a simple "used" marker rather than…
Dynamic Programming
Turning exponential recursive branching into linear or polynomial time by reusing overlapping subproblem results.
Dynamic Programming Fundamentals
Classic DP Patterns
- DP: Kadane's VariantsExtending Kadane's running-sum idea to products by tracking both a running maximum AND a running minimum ending at each position, since multiplying by a…
- Longest Increasing SubsequenceComputing, for each index, the best subsequence ending exactly there by checking every earlier index that could legally precede it (a smaller value) and…
- Longest Common SubsequenceBuilding a 2D table where each cell (i, j) answers "what's the LCS length using only the first i characters of one string and the first j of the other,"…
- 0/1 KnapsackBuilding a 2D table where each cell (i, cap) answers "what's the best value achievable using only the first i items and a knapsack of this capacity,"…
- Edit DistanceBuilding a 2D table where each cell (i, j) answers "how many single-character insert/delete/replace operations turn the first i characters of one word…
- Matrix Chain MultiplicationTrying every possible position to make the final split in a chain of matrix multiplications, recursively finding the optimal cost of each side, and…
- Unbounded Knapsack PatternsFilling a 1D table where each item can be reused any number of times, by iterating capacity in increasing order and referencing the CURRENT row's own…
- Subset Sum (Boolean DP)Building a 1D boolean table where dp[cap] answers "is there a subset of the items considered so far that sums to exactly cap," processing capacities in…
- Super Egg DropReformulating "minimum moves to find the critical floor" as its inverse - "the maximum number of floors distinguishable with a given number of moves and…
- Word Break (DP)Building a 1D boolean table where dp[i] answers "can the first i characters of the string be fully segmented into dictionary words," checking every…
- Weighted Job SchedulingSorting jobs by end time, then for each job (processed in that order) deciding whether including it beats skipping it - if included, its value combines…
Searching & Sorting
Exploiting sorted order to search in logarithmic time instead of linear.
Searching & Sorting Fundamentals
- Binary Search BasicsHalving the search space on a sorted array instead of scanning linearly.
- Binary Search on AnswerBinary searching over the space of possible answers (not array indices), using a feasibility check at each candidate to decide which half of the answer…
- Binary Search on Two ArraysBinary searching for the correct split point of one sorted array, with the split point of the other array determined arithmetically from it - locating a…
Bit Manipulation
Solving problems with bitwise operators directly, often turning an O(n) space problem into O(1).
Bit Manipulation Fundamentals
Strings
Character-level array manipulation with its own common gotchas around comparison, mutability, and encoding.
String Fundamentals
- String Manipulation BasicsCharacter-frequency comparison between strings.
- String Symbol MappingConverting between a value and its symbolic representation using a fixed lookup table of symbol/value pairs, ordered from largest to smallest so a greedy…
- String Prefix ComparisonNarrowing a candidate common prefix by comparing it against each string in turn, shrinking it the moment a mismatch is found - so the final surviving…
- String Parsing State MachineManually parsing a string character by character through a sequence of stages (skip whitespace, read an optional sign, read digits) - each stage consuming…
- String Tokenization ReversalSplitting a string into its meaningful tokens (words, ignoring incidental whitespace) and reassembling them in a different order - separating "what counts…
- String Repetition SearchFiguring out the minimum number of repetitions of one string needed before another could possibly appear as a substring, from length alone - then checking…
- Naive Substring SearchChecking every possible starting position for a match, character by character - the direct, unoptimized way to find one string inside another, correct and…
- Run-Length GenerationBuilding the next term of a self-describing sequence by scanning the current term once and emitting each run's length immediately followed by its character.
- String Segment ComparisonSplitting two strings on a common delimiter and comparing them segment by segment as numbers (not as text), so a missing trailing segment or leading zeros…
- KMP Failure Function ApplicationBuilding the LPS (longest-proper-prefix-that-is-also-a-suffix) array for a string in one linear pass, using the array's own already-computed values to…
Hashing & Sets
Trading O(n) extra space for O(1) average-case lookup, the single highest-leverage technique in interview problem solving.
Hashing Fundamentals
Greedy Algorithms
Making the locally-best choice at each step and trusting it to produce a globally optimal result - and learning to recognize the (narrow) conditions under which that trust is actually justified.
Greedy Fundamentals
- Greedy Sorted MatchingSorting both sides of a matching problem so the smallest-fitting pairing can always be made first, without ever needing to reconsider it.
- Activity Selection GreedySorting intervals by end time and always taking the one that finishes soonest among the remaining candidates - the move that leaves the most room for…
- Fractional Knapsack GreedyFilling a fixed-capacity container by value density (value per unit of weight/space) rather than raw value, taking a fraction of the last item that…
- Deadline Scheduling GreedyProcessing tasks from most to least valuable, slotting each into the latest still-open time slot at or before its deadline - preserving earlier slots for…
- Greedy Denomination CoinsAlways using the largest denomination that still fits, for currency systems specifically designed so that this never produces a suboptimal count.
- Interval Overlap Counting GreedySweeping sorted arrival and departure times together to track how many intervals are simultaneously active, without ever comparing every pair of intervals…
Heaps
A tree-shaped structure that keeps the minimum (or maximum) of a changing collection always at the root, in O(log n) per insert or removal - the standard tool for "keep track of the best/worst so far" and "process items in priority order" problems.
Heap Fundamentals
- Heap Kth-Element SelectionMaintaining a fixed-size heap (capped at k elements) while scanning a collection once, so the heap's root always holds exactly the kth-best element seen…
- Heap Frequency RankingCounting occurrences first, then ranking the distinct values by count - a heap (or a direct sort) turns "the k most common values" into a selection…
- Two-Heap Median MaintenanceSplitting a running stream of numbers across a max-heap (the smaller half) and a min-heap (the larger half), kept balanced in size, so the median is…
- Heap Implementation From ScratchImplementing insert and extract-min directly on a plain array using parent/child index arithmetic - the mechanics PriorityQueue normally hides.
- K-Way Merge HeapMerging several already-sorted sequences by keeping one "current smallest candidate" per sequence in a heap, always emitting the global smallest and…
- Heap Frontier Pair SearchFinding the k best combinations from two sorted sets by exploring outward from the single best combination, using a heap to always expand the most…
- Kth Largest Element in a StreamMaintaining a min-heap capped at exactly k elements across a live sequence of incoming values, so that after every insertion the heap's root is always the…
Stacks and Queues
Two of the simplest possible data structures - restricted to adding and removing only at specific ends - and the surprising number of problems (matching, monotonic scans, simulating one structure with the other) that fall out of that restriction.
Stacks and Queues Fundamentals
- Stack Matching ValidationUsing a stack to confirm that every "opener" in a sequence is closed by the correct matching "closer," in the correct nested order, before anything else…
- Array-Backed Stack and QueueImplementing a stack or queue directly on a fixed-size array - a stack via a single moving top index, a queue via two indices (front and rear) that wrap…
- Cross-Structure SimulationImplementing a stack using only queue operations (or a queue using only stack operations) by choosing when to pay a reordering cost - either on every…
- Monotonic Stack TechniqueKeeping a stack whose elements stay in strictly increasing or decreasing order by popping anything that violates it before pushing - so each element is…
- Recursive Stack ManipulationSorting (or otherwise rearranging) a stack using only push/pop/peek/isEmpty and recursion - the call stack itself stands in for the "extra storage" a…
- Auxiliary Stack TrackingMaintaining a second stack alongside the main one, storing at each position the running minimum (or other aggregate) of everything below and including it…
- Multi-Source BFSStarting a breadth-first search from every "already active" cell at once, rather than one at a time - so cells reached simultaneously from different…
- Monotonic Stack Area ComputationUsing previous-smaller and next-smaller boundaries (found via a monotonic stack) to know, for each bar in a histogram, exactly how wide a rectangle at…
- Monotonic Deque WindowMaintaining a deque of candidate indices in decreasing value order as a window slides, so the maximum of the current window is always the front of the…
- Stack Elimination SearchRepeatedly comparing two candidates and discarding the one that's definitely disqualified, using a stack to track who's still in contention - narrowing n…
Tries
A 26-way (or 2-way, for bits) branching tree that stores strings (or numbers' binary form) character by character, so that prefix-based lookups, counts, and maximization queries cost only the length of the string involved - independent of how many strings are stored.
Trie Fundamentals
- Trie ImplementationStoring a set of strings as paths through a 26-way branching tree, one character per edge, so that insert/search/prefix-check all become simple…
- Trie Count and EraseExtending the basic trie with two integer counters per node - how many complete words end exactly here, and how many words pass through here as a prefix…
- Trie Prefix MatchingMarking every complete word in a trie, then walking a candidate word's own path checking that EVERY node along that path (not just the final one) is…
- Trie Distinct SubstringsInserting every suffix of a string into a trie one character at a time, counting a "distinct substring found" every time a brand-new node has to be…
- Binary Trie Max XORStoring each number's fixed-width binary representation as a root-to-leaf path in a 2-way (bit) trie, then for any query number, greedily walking toward…
Start the DSA interview prep course free
No card needed. Upgrade to Pro when you want the full problem bank.
Free plan, no card · 7-day Pro trial · Cancel anytime