Dinesh/ Blog

Subject / Published lessons

algorithms

Explore the ideas, work through an example, and save a lesson to return to.

Filters · 1 active

85 articles

Recently updated first
  1. Updated ·algorithms

    Arrays & Strings — Indexing, Slicing, Two-Pointer

    Apply indexing, slicing, compaction and two-pointer methods with explicit ordering, mutation, Unicode and complexity contracts.

    26 min read
  2. Updated ·algorithms

    Hashmaps & Sets — Hash Functions, Collisions

    Derive hash-table lookup and collision behavior, stable hash/equality contracts, ordering limits and explicit expected versus worst-case costs.

    25 min read
  3. Updated ·algorithms

    Stacks & Queues — LIFO/FIFO in Practice

    Apply LIFO and FIFO invariants to traversal, monotonic structures and bounded queues; distinguish local ordering from distributed guarantees.

    25 min read
  4. Updated ·algorithms

    Recursion — Call Stack, Base Case, Worked Examples

    Trace recursive calls and base cases, account for memo and stack resources, and compare equivalent iterative implementations.

    25 min read
  5. Updated ·algorithms

    Trees & BSTs — Traversal (BFS/DFS)

    Trace tree traversal and BST invariants with explicit height, ordering, duplicate, node-identity and range-output contracts.

    26 min read
  6. Updated ·algorithms

    Heaps & Priority Queues

    Apply heap invariants to top-K, merging, medians and weighted paths while accounting for ties, storage and update costs.

    26 min read
  7. Updated ·algorithms

    Graphs — Representation, BFS, DFS, Shortest Path

    Represent graphs and derive traversal, connectivity and shortest-path algorithms under explicit vertex, ordering and edge-weight contracts.

    27 min read
  8. Updated ·algorithms

    Sorting — Merge, Quick, and When to Trust the Built-in

    Compare merge, quick and heap sorting with explicit stability, comparator, storage and worst-case contracts, including when to use Python built-ins.

    27 min read
  9. Updated ·algorithms

    Dynamic Programming — Memoisation & Tabulation

    Define states, transitions, base cases and evaluation order; derive time and storage from the actual state space rather than assuming polynomial complexity.

    28 min read
  10. Updated ·algorithms

    Greedy & Backtracking — When to Use Each

    Prove greedy choices for the precise objective, and build complete backtracking searches with correct undo, sound pruning and explicit output costs.

    27 min read
  11. Updated ·algorithms

    Variant contracts: bounded budgets, interval cuts and subset routes

    Extend the restored problem-family series with bounded knapsack, two resource budgets, interval reconstruction and Held–Karp routes, using independent tiny oracles.

    30 min read
  12. Updated ·algorithms

    02 · Count work, then remember what matters

    Derive hash counting and prefix sums from repeated work, with brute-force oracles and honest complexity assumptions.

    13 min read
  13. Updated ·algorithms

    The LeetCode Game — How to Read a Problem

    Read input, output and value bounds together; derive work and storage costs, then justify algorithm preconditions rather than guessing a universal time limit.

    19 min read
  14. Updated ·algorithms

    Big-O in Practice — Counting, Not Vibes

    How to derive the cost of a Python data structure operation from how it is built, instead of memorising a table you half-remember under pressure.

    16 min read
  15. Updated ·algorithms

    Python for Speed — The 20 Idioms That Matter

    The small set of standard-library tools that turn a fifteen-line design review solution into a five-line one, and the syntax you must be able to type without thinking.

    15 min read
  16. Updated ·algorithms

    Arrays & Strings — In-Place Discipline

    Derive read/write-pointer compaction and partitioning from loop invariants, then test the boundary cases that make in-place mutation safe.

    17 min read
  17. Updated ·algorithms

    Hashing — Your Default Weapon

    The complement-lookup skeleton and the general move of trading memory for time, which is the first thing to try whenever a problem looks quadratic.

    16 min read
  18. Updated ·algorithms

    UMPIRE — The Problem-Solving Framework

    A six-step practice checklist for clarifying contracts, comparing approaches, planning, implementing, testing and analyzing costs—without a fixed completion-time promise.

    18 min read
  19. Updated ·algorithms

    Two Pointers I — Opposite Ends

    Two indices converging from the ends of a sorted array, and the monotonicity argument that proves you can discard a whole row of candidates with one comparison.

    24 min read
  20. Updated ·algorithms

    Two Pointers II — Same Direction & Fast-Slow

    Two pointers moving the same way at different speeds: the read/write compaction you already know, and Floyd's cycle detection, which finds a loop in O(1) memory.

    18 min read
  21. Updated ·algorithms

    Sliding Window I — Fixed Size

    Maintaining a window aggregate incrementally so that sliding costs O(1) instead of O(k), which turns the obvious O(n*k) scan into a single pass.

    14 min read
  22. Updated ·algorithms

    Sliding Window II — Variable Size

    Expand right unconditionally, shrink left while the invariant is broken, record at the right moment — and the amortisation argument that keeps it linear.

    15 min read
  23. Updated ·algorithms

    Sliding Window III — With Counts

    Windows whose validity depends on a frequency map, and the single integer counter that lets you test that condition in O(1) instead of rescanning the map.

    17 min read
  24. Updated ·algorithms

    Prefix Sums & Difference Arrays

    Precomputing cumulative sums to answer range queries in O(1), and the prefix-plus-hashmap combination that counts subarrays where sliding windows are unsound.

    16 min read
  25. Updated ·algorithms

    Binary Search I — The Template

    One binary search template with a half-open invariant that never loops forever and never goes off by one, and the discipline of owning exactly one version of it.

    16 min read
  26. Updated ·algorithms

    Binary Search II — Rotated & 2D

    Binary search when the array is no longer sorted end-to-end: decide which half is still sorted, then discard the other. Same trick flattens a 2D matrix into one index space.

    17 min read
  27. Updated ·algorithms

    Binary Search III — On the Answer

    Stop searching the array and start searching the answer range: define a monotonic feasibility predicate, then binary search the smallest x for which it holds.

    17 min read
  28. Updated ·algorithms

    Stacks — LIFO & Matching

    Nesting, matching, undo and expression evaluation are one idea: push what you expect, pop when it arrives, and carry auxiliary state alongside for O(1) queries like min.

    19 min read
  29. Updated ·algorithms

    Monotonic Stack

    Next greater and next smaller element in O(n): keep a stack whose order never breaks, and pop everything the current element resolves.

    23 min read
  30. Updated ·algorithms

    Queues & Monotonic Deques

    The queue as BFS substrate, and the monotonic deque that answers sliding-window maximum in O(n) by discarding candidates that can never win again.

    25 min read
  31. Updated ·algorithms

    Linked Lists I — Traversal & Reversal

    The dummy head that deletes most linked-list edge cases, and the prev/cur/next three-step reversal you should be able to write without thinking.

    20 min read
  32. Updated ·algorithms

    Linked Lists II — Cycles, Middle, Reorder

    Floyd's tortoise and hare for cycle detection and entry point, finding the middle in one pass, and composing split-reverse-merge to reorder a list in O(1) space.

    20 min read
  33. Updated ·algorithms

    Recursion & the Call Stack

    Base case discipline, hand-tracing a call stack, and knowing when recursion is the wrong tool — the substrate under trees, backtracking and dynamic programming.

    18 min read
  34. Updated ·algorithms

    Trees I — DFS Traversals

    Preorder, inorder and postorder as one recursive skeleton with the work line moved, plus the iterative forms and when they are worth writing.

    19 min read
  35. Updated ·algorithms

    Trees II — BFS / Level Order

    Snapshot the queue length at the top of each iteration and you have level-order traversal — the one trick behind right side view, zigzag, and minimum depth.

    19 min read
  36. Updated ·algorithms

    Trees III — BST Properties

    Two views of a binary search tree: inorder traversal yields sorted order, and validation requires passing bounds down rather than comparing parent to child.

    21 min read
  37. Updated ·algorithms

    Trees IV — Paths & Accumulators

    The return-one-thing-track-another pattern: a recursion whose return value serves the parent while a separate accumulator records the global best.

    21 min read
  38. Updated ·algorithms

    Heaps & Top-K

    When a problem asks for the K largest, K smallest, or K most frequent of anything, you almost never need to sort. A size-K heap answers it in O(n log k).

    20 min read
  39. Updated ·algorithms

    Graphs I — Representation & DFS

    Build the adjacency list, carry a visited set, and recognise that a grid is already a graph — then count connected components with a depth-first sweep.

    23 min read
  40. Updated ·algorithms

    Graphs II — BFS & Shortest Path

    Breadth-first search level by level, why it gives shortest paths in unweighted graphs, and the multi-source variant that solves nearest-X grid problems in one sweep.

    19 min read
  41. Updated ·algorithms

    Graphs III — Topological Sort

    Kahn's in-degree algorithm for ordering tasks with dependencies, and why a queue that empties early is exactly a cycle detector.

    18 min read
  42. Updated ·algorithms

    Graphs IV — Union-Find (DSU)

    Fifteen lines of disjoint-set union with path compression and union by rank, and the family of connectivity problems it collapses into near-constant time.

    18 min read
  43. Updated ·algorithms

    Backtracking I — Subsets & Combinations

    One choose-explore-unchoose template that generates subsets, combinations and permutations, plus the two ways to skip duplicates without producing duplicate output.

    19 min read
  44. Updated ·algorithms

    Backtracking II — Constraint Grids

    Prune partial assignments, maintain column and diagonal constraints, and restore search state in N-Queens, Word Search and Sudoku.

    21 min read
  45. Updated ·algorithms

    DP I — Recognising Overlapping Subproblems

    DP is recursion plus a cache. Write the recursion, add lru_cache, convert to a table — mechanically, in that order, every time.

    25 min read
  46. Updated ·algorithms

    DP II — 1D Linear

    Define dp[i] in English before you write code. The House Robber family, and why most DP bugs are undefined state rather than a wrong transition.

    20 min read
  47. Updated ·algorithms

    DP III — Take / Skip Decisions

    The binary-decision DP shape: at each index you either act or you don't. State machines for cooldown, reachability for Jump Game, and split points for Word Break.

    21 min read
  48. Updated ·algorithms

    DP IV — Subsequences (LIS / LCS)

    Longest Increasing Subsequence and Longest Common Subsequence are the two parent problems behind a huge family. Know both cold and most subsequence DP becomes recognition.

    20 min read
  49. Updated ·algorithms

    DP VI — Unbounded Knapsack

    The knapsack where each item is available in unlimited supply. One character changes from 0/1 — the capacity loop direction — and Coin Change, Rod Cutting, and Combination Sum IV all fall out of it.

    16 min read
  50. Updated ·algorithms

    DP VII — 2D Grid

    Grid DP is the friendliest dynamic programming: each cell is built from the one above and the one to its left. Use it to make DP feel mechanical before string DP.

    19 min read
  51. Updated ·algorithms

    DP VIII — String DP / Edit Distance

    The two-string DP table: dp[i][j] over prefixes, the three-way insert/delete/replace recurrence, and how Distinct Subsequences and Interleaving String are the same table with different transitions.

    21 min read
  52. Updated ·algorithms

    DP IX — Palindromes

    Expand-around-centre versus the 2D palindrome table: two O(n^2) approaches with very different failure rates, and when partitioning forces you back to explicit DP.

    21 min read
  53. Updated ·algorithms

    DP X — Interval DP

    dp[i][j] over ranges with an inner split point k: why Burst Balloons only works when you think about the LAST balloon, and how sentinel padding removes the boundary cases.

    23 min read
  54. Updated ·algorithms

    DP XI — State Machine

    Naming your DP states explicitly: hold and free arrays for the stock problems, why drawing the transition diagram first collapses the difficulty, and how the k-transaction version generalises.

    24 min read
  55. Updated ·algorithms

    DP XII — Bitmask DP

    Encoding a subset as an integer: when n is at most 20 the exponential state is affordable, the standard submask and popcount idioms, and why the constraint tells you before the problem does.

    20 min read
  56. Updated ·algorithms

    Tries — Prefix Trees

    Children dict plus terminal flag: building a trie in ten lines, and why Word Search II is trie-plus-backtracking rather than a dictionary scan.

    20 min read
  57. Updated ·algorithms

    Bit Manipulation

    XOR cancels itself, n & (n-1) clears the lowest set bit, and how to add two integers without the plus operator. The handful of bit tricks that actually recur in practice.

    23 min read
  58. Updated ·algorithms

    Math & Number Theory

    Fast exponentiation by squaring, the sieve of Eratosthenes, Euclid's GCD, and binary search on integers — the four math routines worth memorising outright.

    26 min read
  59. Updated ·algorithms

    Intervals

    Sort by start, merge on overlap: the four-problem interval family, and why Meeting Rooms II needs a heap on top of the sort.

    23 min read
  60. Updated ·algorithms

    Greedy — And Proving It Works

    Greedy feels right and is often wrong. The exchange argument, the counter-example hunt you should run first, and four problems where greedy genuinely is optimal.

    27 min read
  61. Updated ·algorithms

    Matrix Manipulation

    Transpose then reverse to rotate in place, four-boundary control for spiral traversal, and using the first row and column as O(1) marker storage.

    19 min read
  62. Updated ·algorithms

    Design I — Composing for O(1)

    Hashmap plus doubly-linked list for LRU, array plus index map for GetRandom, and the general move of combining two structures so each covers the other's weakness.

    20 min read
  63. Updated ·algorithms

    Design II — Streams & Time

    Two balanced heaps for a running median, binary search over versioned timestamps, and merging k sorted feeds — the design patterns for data that arrives over time.

    27 min read
  64. Updated ·algorithms

    Sorting & Custom Comparators

    Partition-based selection and comparator design: Dutch national flag, quickselect for Kth largest in O(n) average, and cmp_to_key for orderings that are not a simple key.

    23 min read
  65. Updated ·algorithms

    Segment Trees & Fenwick (BIT)

    Range query with point update in O(log n): the recursive segment tree skeleton, the Fenwick tree's low-bit trick, and how to recognise the rare problem that actually needs one.

    20 min read
  66. Updated ·algorithms

    String Algorithms

    KMP's failure function, rolling hashes, and the Z-function — the three ways to avoid re-comparing characters you have already matched.

    19 min read
  67. Updated ·algorithms

    Advanced Graphs

    Dijkstra as BFS with a priority queue, Bellman-Ford for negative weights and bounded hops, and the two minimum spanning tree algorithms — with the cue for choosing between them.

    19 min read
  68. Updated ·algorithms

    Mock Set 1 — Mixed Easy/Medium, 45 min

    The first cold pressure test: two unseen Easy and two unseen Medium in 45 minutes, no hints, timer visible — run as an experiment that produces data about your classifier.

    24 min read
  69. Updated ·algorithms

    Mock Set 2 — Narrated & Recorded

    Two unseen Mediums with screen/audio recording and evidence-based playback review.

    24 min read
  70. Updated ·algorithms

    Blind 75 Sweep — Gap Audit

    Attempt-classify all 75 problems in one structured sweep, mark each cold, warm, hint or failed, and produce the personalised weak list that drives the rest of the track.

    25 min read
  71. Updated ·algorithms

    Weak-Pattern Intensive

    Take the bottom three patterns from the L59 audit and repair them with the rebuild loop: blind template, three costumes, interleaved re-test.

    24 min read
  72. Updated ·algorithms

    Mock Set 3 — One Hard, 45 min

    A timed unfamiliar-hard session: investigate decompositions, state invariants, and record partial progress and assistance.

    25 min read
  73. Updated ·algorithms

    Senior-Flavour Coding

    Coding and design exercises for LRU caches, hit counters, logging limits, queues, and ring-based key routing.

    18 min read
  74. Updated ·algorithms

    Contest Simulation

    A timed contest simulation with explicit triage, scoring, recovery, and post-session review rules.

    24 min read
  75. Updated ·algorithms

    Final Audit + Maintenance Plan

    Re-audit patterns against an earlier baseline and schedule bounded maintenance, repair, and follow-up checks.

    28 min read
  76. Updated ·algorithms

    Linked Lists — Singly, Doubly, When They Win

    The data structure reviewers still love — plus the three real-world situations where a linked list actually beats an array.

    25 min read
  77. Updated ·algorithms

    Binary Search — the Pattern Behind 100 Problems

    Derive exact search, insertion boundaries and binary search on a monotone answer predicate, with shrinking-interval proofs, shipping-capacity witnesses and explicit cost assumptions.

    27 min read
  78. Updated ·algorithms

    01 · Programs as contracts: values, state and tests

    Build a small event normalizer, expose aliasing, and distinguish a test from a proof. Python foundations without a catalogue of syntax.

    14 min read
  79. Updated ·algorithms

    03 · Discarding possibilities: search and windows

    Prove which candidates can be discarded, derive lower bound, and see exactly why negative numbers break a common window.

    14 min read
  80. Updated ·algorithms

    04 · Unfinished work: stacks, queues and heaps

    Choose a removal policy, prove a next-greater stack, and maintain a bounded top-k heap without confusing partial order with sorting.

    13 min read
  81. Updated ·algorithms

    05 · Graphs: reachable is not ready

    Derive unweighted shortest paths and dependency ordering, with explicit edge direction, cycle rejection and bounded exhaustive tests.

    16 min read
  82. Updated ·algorithms

    06 · Dynamic programming: choose a sufficient state

    Derive take-or-skip recurrence, explain backward capacity updates, and distinguish exact amounts, capacity bounds and counting order.

    16 min read
  83. Updated ·algorithms

    DP V — 0/1 Knapsack

    Derive the 0/1 knapsack recurrence, prove why compressed capacity updates descend, and adapt the state to partition, sign assignments and reconstruction.

    17 min read
  84. Updated ·algorithms

    Company-Tagged — Microsoft & Amazon

    Two transferable coding mocks: extend a pair-sum problem and reason through a grid traversal, then assess your explanations and failure cases without claiming current employer question-frequency data.

    21 min read
  85. Updated ·algorithms

    Algorithm practice · From recognition to a defensible solution

    A broad problem-family route alongside the runnable Foundations Lab: derive invariants, study variants, test with oracles and track specific gaps.

    22 min read