DSA
Category

Patterns

A pattern is a way of deciding the next step when the structure alone does not settle it. These articles cover taking the best local choice, searching by trying a branch and undoing it, storing an answer you will need again, filling a table from smaller subproblems, and a trie that shares prefixes.

  1. When Is a Greedy Choice Safe? Interval Scheduling

    A greedy algorithm commits to a local choice only when a proof shows that choice cannot make the final answer worse. Interval scheduling demonstrates the exchange argument.

  2. What Is Backtracking? Choose, Explore, Then Undo

    Backtracking performs depth-first search over decisions. It chooses, explores, and restores state before trying the next choice.

  3. What Is Dynamic Programming? Overlapping Subproblems

    Dynamic programming defines states, a recurrence, and base cases, then evaluates each overlapping subproblem once.

  4. What Is Memoisation? Caching an Overlapping Answer

    Memoisation is top-down dynamic programming: cache a function's result by its complete state so repeated recursive calls become lookups.

  5. What Is a Trie? A Prefix Tree for Shared Word Paths

    A trie stores one character per edge. Shared prefixes share paths, making exact-word and prefix lookup proportional to query length.

  6. What Is a Half-Open Interval? Why Touching Meetings Do Not Overlap

    A half-open interval includes the start and excludes the end. Two meetings that touch at that endpoint do not overlap, which is the rule interval scheduling relies on.

  7. What Is a Permutation? Orderings from Choose, Explore, Undo

    A permutation is an ordering of values. Backtracking builds it by choosing an unused value, exploring, then undoing, and a copy of the path is what you save.

  8. What Is Tabulation? Filling a Dynamic-Programming Table Upward

    Tabulation writes answers from the base case toward the size you were asked for. Each cell is one sentence: the answer for this size, built from smaller cells.

  9. How Do Trie Node Counts Measure Shared Prefixes?

    A count on each trie node records how many inserted words pass through it. Prefix queries and longest common prefixes then become path walks.