Learn it properly.
Most tutorials teach you to copy code. Here you'll understand why things work — with real proofs, every variation, and the depth that actually makes knowledge stick.
51 topics
DSA Patterns
51Arrays & Two Pointers
Two Pointers — Opposite Ends
Your very first algorithm pattern, explained from zero. We build the idea from a real-life story, prove it can never fail, and learn to spot it in five different problems.
Two Pointers — Same Direction
The slow-fast pointer trick that cleans up an array in a single pass with no extra memory. We build the intuition from a real-life story, prove why overwriting is always safe, and learn to spot the skeleton across five different problems.
Dutch National Flag — Three-Way Partition
Sort an array of three distinct values in a single pass and O(1) space using three pointers. We build the idea from a sorting-laundry story, prove the invariant, and apply it to five real problems.
Sliding Window — Fixed Size
How to answer 'what is the best K-element stretch of this array?' in O(n) instead of O(n·K). We build the idea from a train window, prove why reuse beats recompute, and see the skeleton in four different problems.
Sliding Window — Variable Size
How to find the shortest or longest subarray satisfying a condition in O(n) by expanding and shrinking a window on demand. Built from a rubber-band story, proven correct, applied to five classic problems.
Prefix Sum
Precompute a running total once, then answer any range-sum question in O(1). We build the idea from a phone bill story, prove the formula, and apply it to six problems including the classic subarray-sum-equals-K.
Suffix Sum — Product of Array Except Self
Precompute from the right end, then combine with a left pass to answer each position's question in O(1). We build the idea from a recipe story, derive the classic no-division product trick, and master the two-pass framework.
Kadane's Algorithm
Find the maximum sum subarray in a single O(n) pass by tracking just one number: the best sum ending right here. We derive the idea from first principles, prove why a fresh start is sometimes the right move, and apply it to the circular variant.
Moore's Voting Algorithm
Find the majority element in O(n) time and O(1) space. We build the idea from a surprisingly simple political metaphor, prove it can never miss, and extend it to the n/3 variant.
Merge Intervals
How to collapse a messy list of overlapping time slots into the smallest clean set. One sorting step plus one left-to-right sweep is all it takes — and once you see why, you'll never forget it.
Interval Scheduling
How to fit the maximum number of non-overlapping events into a calendar. One surprising sorting choice turns a hard selection problem into a trivially simple greedy sweep.
Cyclic Sort
When numbers live in the range 1 to N, every number already knows its home. We exploit that to sort in O(n) with no extra memory — and then find missing or duplicate numbers as a free bonus.
Matrix Spiral Traversal
Traverse every cell of a 2D matrix in spiral order by peeling it one layer at a time — like unwrapping an onion. Understand why the boundary-shrinking trick always terminates and how to extend it to rotate or generate matrices.
Matrix Diagonal Traversal
Every cell on the same anti-diagonal shares the same row+col sum. That one insight turns a confusing 2D problem into a clean 1D sweep — and it's the key to diagonal sort, anti-diagonal grouping, and the Diagonal Traverse problem.
Matrix Search — Sorted Matrix
When every row and column of a matrix is sorted, a single corner gives you a powerful elimination strategy: each comparison permanently removes an entire row or column. Find any value in O(m + n) — no binary search needed.
In-Place Array Manipulation — Negation Marking
When you need O(1) extra space but must remember which values you've visited, the array itself is your notebook. Flip a cell negative to mark it — and the original value is still recoverable with abs(). A single elegant trick unlocks three classic interview problems.
Subarray Counting — Prefix Sum + Hash Map
Counting subarrays with a given sum looks like an O(n²) problem — until you see that two running totals differing by the target define a valid subarray between them. A hash map turns that into a single O(n) pass.
Hashing
Two Sum Pattern — Value to Index Map
The hash map turns a brute-force O(n²) pair search into a single O(n) pass. We build the idea from a cloakroom story, prove it with a frame-by-frame trace, and extend it to three-sum, four-sum, and complement-pairing problems.
Frequency Counting
A hash map that counts occurrences transforms 'who appears most?' or 'which character is missing?' from an O(n²) scan into a single O(n) pass. Learn to tally, query, and combine frequency maps across classic interview problems.
Grouping by Key
When elements that look different are secretly equivalent, compute a canonical signature for each one and group them in a hash map. The signature is the key — not the element. This one idea solves Group Anagrams, Group Shifted Strings, and any equivalence-class problem.
Hashing for Subarray Problems
A hash map that stores prefix aggregates (sums, XORs, remainders) turns any 'count subarrays satisfying a condition' problem into a single O(n) pass. This chapter deepens pattern 1.17 with the XOR, mod-k, and longest-subarray variants — and explains the design decision of *what exactly to hash*.
Rolling Hash / Rabin-Karp
A rolling hash turns an O(k) rehash into an O(1) slide. Subtract the leaving character's contribution, add the entering character's — and you get a new hash for each window without scanning it. Rabin-Karp uses this idea to find all pattern matches in O(n) time.
HashSet for Duplicate / Existence Check
A HashSet answers one question — 'have I seen this before?' — in O(1) time. Mastering this simple structure unlocks a surprising range of problems: duplicate detection, existence lookup, the elegant Longest Consecutive Sequence, and cycle detection via the Floyd variant.
Custom Hash Design
Some problems hand you a composite key — a pair, a tuple, a sorted string — and expect O(1) lookups. This chapter teaches you to design hash keys for any structure, avoid accidental collisions, and build full hash-map systems like TinyURL or a from-scratch HashSet.
Strings
Two Pointers on Strings
The same opposite-direction and same-direction two-pointer techniques from arrays apply directly to strings. This chapter covers palindrome checking, subsequence testing, and comparing two strings character by character — with the exact same skeleton as Chapter 1.1 and 1.2, just on characters instead of numbers.
Sliding Window on Strings
A sliding window with a character frequency map finds substrings satisfying frequency constraints in O(n) time. This chapter covers the variable-size window (minimum window substring), the fixed-size window (find all anagrams / permutation match), and the 'at most k distinct characters' family.
KMP Algorithm (Pattern Matching)
KMP finds all occurrences of a pattern inside a text in O(n + m) time by never going backwards in the text. The secret is the failure function — a pre-computed array that tells the matcher where to resume in the pattern after a mismatch, using the pattern's own overlap structure.
Z-Algorithm
The Z-array tells you, for every position i in a string, how many characters starting at i match the very beginning of the string. Building this array in O(n) enables pattern matching, finding repeated prefixes, and counting pattern occurrences — often with simpler code than KMP.
Palindrome — Expand Around Center
Every palindrome has a center — a single character (odd length) or a gap between two characters (even length). Expanding outward from every possible center in O(n) total gives the longest palindromic substring in O(n²) time, O(1) space — far simpler than Manacher's but powerful enough for almost all interviews.
Manacher's Algorithm
Manacher's algorithm finds the radius of the longest palindrome centered at every position in O(n) total — by reusing palindrome radii already computed within a known enclosing palindrome. It is the O(n) upgrade to the O(n²) expand-around-center approach.
String Reversal Tricks
Reversing a string (or parts of it) in-place solves a surprising range of problems: rotating a string, reversing word order, and cycling a sequence — all in O(n) time and O(1) extra space. The core trick is that two or three targeted reverse operations can rearrange any contiguous segment without allocating a new array.
Character Frequency + Sorting
Count how often each character appears, then use that count to drive rearrangement — sorting characters by frequency, reorganising a string so no two adjacent characters are the same, or building the lexicographically smallest result. One frequency map, three fundamentally different problems.
Parentheses Problems
A stack (or a single counter) processes bracket sequences left to right, matching each closing bracket against the most recent unmatched opener. This one idea — 'most recent unmatched opener' — solves validity checking, longest valid subsequence, minimum removals, and score counting.
String Building / Simulation
Some string problems ask you to follow a set of rules step-by-step and produce a result — decode a compressed string, evaluate a nested expression, simulate a text editor. A stack that holds (current_string, pending_count) state is the clean O(n) solution for all nested-structure decoding.
Anagram Pattern
Two strings are anagrams if they contain the same characters in the same quantities — regardless of order. Checking anagram equality costs O(n); finding all anagram windows in a longer string costs O(n) using a sliding frequency map. This one idea powers valid-anagram, find-all-anagrams, and grouped-anagrams problems.
Trie-based String Problems
A trie (prefix tree) stores a collection of strings as a tree of single characters. Inserting a word costs O(L); prefix searching costs O(L); and any of the N words in the dictionary is reachable in at most O(L) steps — making tries the fastest structure for prefix queries, autocomplete, and word search problems.
Linked Lists
Fast & Slow Pointers — Floyd's Cycle Detection
Two pointers moving at different speeds through a linked list will meet inside a cycle if one exists — and never meet if there is none. This one idea detects cycles, finds their entry point, and with a small twist, solves Happy Number and Duplicate in Array problems too.
Find Middle of Linked List
Move fast two steps and slow one step — when fast reaches the end, slow is at the middle. This single trick finds the midpoint in one pass with no length calculation, and is the essential first step in palindrome checking, merge sort on lists, and reordering problems.
Reverse a Linked List
Reversing a linked list means redirecting every 'next' pointer to point backward. Three pointers — prev, curr, next — perform this in a single O(n) pass with O(1) space. The partial-reverse variant (reverse only positions m to n) extends this skeleton with a precise four-step wiring pattern.
Merge Two Sorted Lists
Compare the heads of two sorted lists, pick the smaller one, advance that list's pointer — repeat until one list is exhausted, then attach the remainder. This simple O(n + m) merge is the heart of merge sort and the building block for merging K sorted lists with a heap.
Remove Nth Node from End
Move the fast pointer N steps ahead, then walk both fast and slow together until fast reaches the end — slow is then exactly at the node just before the one to delete. This N-gap two-pointer trick removes the Nth-from-end node in a single O(n) pass with no length calculation.
Intersection of Two Linked Lists
Two pointers walk their own lists, then switch to the other list when they hit the end. After at most (lenA + lenB) steps both pointers have covered equal total distance — they meet at the intersection node, or both arrive at null if no intersection exists. O(n + m) time, O(1) space, zero length calculation.
Reorder List
Reorder a linked list so that nodes interleave from the front and back: first, last, second, second-last, … Three steps in sequence — find the middle, reverse the second half, merge the two halves alternately — each step using patterns you already know from Chapters 4.2 and 4.3.
Flatten a Linked List
Flatten a multilevel doubly linked list where nodes may have a child pointer branching to another sublist. Learn the stack-based DFS approach and the elegant iterative insert-child-inline method — plus the sorted vertical list variant.
Add Two Numbers as a Linked List
Two linked lists store digits of large integers (one digit per node). Add them just like grade-school column addition — carry included — using a dummy head and a carry variable. Handle different lengths and a final carry cleanly.
Clone a List with Random Pointers
Deep-copy a linked list where each node has a next pointer and a random pointer to any node (or None). Master the O(n) hashmap approach, then learn the brilliant O(1)-space interleave trick — copy nodes woven between originals — used in top-tier interviews.
Stacks
Monotonic Stack — Next Greater / Smaller Element
A monotonic stack is a stack kept in strictly increasing or decreasing order by popping elements that violate the order before pushing. This single idea solves 'next greater element', 'daily temperatures', 'previous smaller element', and a dozen interview variants in O(n) — instead of the O(n²) brute-force.
Stack for Parentheses Matching
Push opening brackets onto a stack; pop on each closing bracket and verify the pair matches. This one rule validates arbitrarily nested bracket expressions in O(n) and extends naturally to minimum removal, score computation, and longest valid substring.
Min / Max Stack
Design a stack that supports push, pop, top, and getMin (or getMax) — all in O(1) time. The trick: maintain a second auxiliary stack that tracks the current minimum (or maximum) at every level of the main stack, so the answer is always sitting at the top of the auxiliary stack.
Largest Rectangle in Histogram
Find the area of the largest rectangle that fits inside a histogram. The O(n) stack solution treats each bar as the height of a maximal rectangle, using a monotonic increasing stack to find the left and right boundaries in a single pass. Extends directly to 'Maximal Rectangle in Binary Matrix'.
Stack-based Expression Evaluation
Stacks solve arithmetic expression evaluation by handling operator precedence and parentheses in O(n). Two canonical forms: Reverse Polish Notation (postfix) — straightforward operand stack; and infix expressions (Basic Calculator) — two stacks for numbers and operators, with precedence rules. Both reduce to the same push/pop rhythm.