Skip to main content

Choosing a Paradigm by Problem Structure

What This Concept Is​

There is no universal algorithm. Paradigm selection is a structured triage on the problem:

  1. What am I asked to produce? Decision (yes/no), optimization (max/min), enumeration (list all), counting (how many), construction (build one).
  2. What is the candidate space size as a function of $n$? $n$, $n^2$, $n \log n$, $n!$, $2^n$?
  3. What is the constraint regime? $n \le 20$ invites bitmask; $n \le 10^5$ demands $O(n \log n)$; $n \le 10^9$ forbids anything linear in $n$; a streaming input forbids storing everything.
  4. Is there optimal substructure? Overlapping subproblems? A provable greedy choice?
  5. Is the input structured? Sorted, graph, intervals, tree, sparse, high-dimensional, low-entropy.
  6. Is there a cheap oracle (brute force) for stress testing?

Each answer routes you toward a paradigm. The output is not just "DP" or "greedy" but why that paradigm, which is what lets you write the code and the proof.

A useful rule of thumb from competitive programming (Halim's Tip 3):

$n$ rangeAcceptable complexity
$n \le 12$$O(n!)$
$n \le 20$$O(2^n \cdot n)$
$n \le 500$$O(n^3)$
$n \le 10^4$$O(n^2)$
$n \le 10^5$ - $10^6$$O(n \log n)$ or $O(n)$
$n \le 10^8$$O(n)$ barely; prefer $O(\sqrt n)$ or $O(\log n)$

This map lets you know within seconds whether brute force, backtracking, DP, greedy, or a data-structure approach is even a candidate.

Why It Matters Here​

The hardest part of a new problem is the first five minutes: naming the right paradigm. After that, the implementation is mostly template work. Engineers who consistently pick the right paradigm look fast; the speed is in the classification, not the typing.

The wrong paradigm usually manifests as either "my greedy gives wrong answers on an adversarial input" (concept 10, 14) or "my brute force does not fit in $n = 10^5$" (concept 8, 17). Both come from misreading the problem, not from a coding bug.

In industry, this is the skill of triaging a design task: "is this a shortest-path problem in disguise? a bipartite-matching problem? a DP on a DAG?" Experienced engineers ask these questions before touching a keyboard.

Concrete Example​

Example 1 (subarray sum with target). Given an array of $n$ integers and a target $T$, find the number of contiguous subarrays with sum exactly $T$.

Triage.

  1. Task. Counting.
  2. Candidate space. $\binom{n}{2} = O(n^2)$ subarrays. Too many if $n \ge 10^5$.
  3. Constraint. Suppose $n \le 10^6$.
  4. Structure. Running-sum identity: $\text{sum}(A[i..j]) = \text{prefix}[j+1] - \text{prefix}[i]$. So subarrays with sum $T$ correspond to pairs $(i, j)$ with $\text{prefix}[i] = \text{prefix}[j+1] - T$.
  5. Paradigm. Running hash map. For each $j+1$, count how many earlier prefix values equal $\text{prefix}[j+1] - T$. Total $O(n)$.

Same problem rephrased - "longest increasing subsequence of the array" - routes to DP with $O(n \log n)$ patience sort, not a hash map. The input shape changes everything.

Example 2 (max weight subset, no two adjacent).

  • $n \le 20$. $2^n \cdot n = 10^7$; brute force or bitmask DP both fit.
  • $n \le 10^4$. DP on the line graph: $f(i) = \max(f(i-1), f(i-2) + w_i)$, $O(n)$.
  • Tree-shaped constraint. Tree DP on children: $f(v, \text{taken}) = $ best sum in subtree rooted at $v$ given $v$ is taken or not.

Same problem, three constraint regimes, three algorithms.

Example 3 (shortest path in a graph with $n = 10^4$, non-negative weights).

Triage. Shortest path + non-negative weights ⇒ Dijkstra's algorithm with a binary heap, $O((n + m) \log n)$. If weights were uniform, BFS in $O(n + m)$. If weights could be negative, Bellman-Ford in $O(nm)$. If we wanted all-pairs, Floyd-Warshall in $O(n^3)$.

Every variation maps to a specific algorithm, and the routing is done by asking the triage questions in order.

Example 4 ($n = 10^9$, find the $k$-th smallest coprime to $n$).

Triage. $n = 10^9$ forbids anything $O(n)$. Structure: coprime-to-$n$ depends only on $n$'s prime factors (small set). Paradigm: inclusion-exclusion over prime subsets; binary search on the answer. Runtime $O(2^{\omega(n)} \cdot \log n)$ where $\omega(n)$ is the number of distinct prime factors (at most ~9 for $n = 10^9$). Sub-second.

Common Confusion / Misconceptions​

  • "I know divide-and-conquer, so every problem should be attacked with D&C." Paradigm knowledge is a menu, not a hammer. Without triage, you apply the most recently learned tool whether it fits or not.
  • "If one paradigm works, it is the only one." Many problems admit several solutions. For learning, write more than one: brute force for the oracle, the intended paradigm for the real answer, and sometimes a second paradigm as a cross-check.
  • "The constraints will guide me without triage." Constraints narrow; they do not decide. An $n \le 10^5$ problem might be $O(n \log n)$ sort-plus-greedy or $O(n \log n)$ segment-tree sweep; those are different algorithms. You still need the structure analysis.
  • "Triage is for interviews." Triage is what happens every morning in a design review. The vocabulary (candidate space, optimal substructure, greedy-choice property) is the shared language of algorithmic engineering.
  • "If there's a named algorithm, use it." Often correct. But the named algorithm assumes a specific input shape; triage is what tells you whether the named algorithm applies.

How To Use It​

Concrete triage checklist to run at the start of any algorithm problem:

  1. Restate the problem in one sentence. What is the input, what is the output?
  2. Compute the naive brute-force complexity. Does it fit in the constraints? If yes, you may be done (concept 8).
  3. Decide the task type. Decision, optimization, counting, construction, enumeration. The task type narrows paradigms.
  4. Scan for structure. Sorted? Graph? Intervals? Tree? Small $n$ inviting bitmask or brute force?
  5. Try greedy first if there is a plausible local rule. Prove by exchange or abandon (concept 10).
  6. Try DP if decisions interact (concept 12): define state, recurrence, base, runtime.
  7. Fall back to D&C when the problem splits cleanly with a cheap combine (concept 9).
  8. Use backtracking when the candidate space is combinatorial but pruning is strong (concept 11).
  9. Consider data structures (union-find, segment tree, priority queue) if the bottleneck is not the algorithm but the operation cost. This is cue to module 2.
  10. Set an oracle. Can you write a brute force for stress testing (concept 15)? If yes, that is free correctness insurance.

If none clearly fits, the problem may require a data structure or a specialty algorithm not in this module. That is a cue to the next module (M2: sorting, data structures), or a textbook lookup, not a sign to push a wrong paradigm harder.

Transfer / Where This Shows Up Later​

  • S1 M5 (problem solving) taught "classify before you commit." Paradigm triage is the algorithmic version.
  • S4 (systems) triages cache-complexity and data layout decisions; same checklist with different axes (working-set size, block size, I/O model).
  • S5 (OS) triages scheduling problems: real-time vs batch vs interactive; the constraint regime picks the algorithm just as it does here.
  • S6 (databases) triages query optimization: nested-loop vs hash vs merge join depending on input size, sortedness, and selectivity - a constraint-driven paradigm choice.
  • S7 (architecture) is triage at the system level: ADRs are triage artifacts, reversibility classifies one-way vs two-way doors, risk drives review depth. The skeleton is the same (classify, commit, document, revisit).
  • S8 (distributed systems) triages consensus protocols by constraints (leader-based vs leaderless, synchronous vs asynchronous, Byzantine vs crash-stop).

This page is the capstone of the module: concepts 1-17 are the tools; this is how you decide which to pick up. Every later module reuses this triage skeleton on its own axes.

Check Yourself​

  1. What triage questions do you ask before picking a paradigm?
  2. Why is the constraint on $n$ a first-class input to the paradigm decision?
  3. Give a problem whose paradigm changes when you change its constraint ($n \le 20$ vs $n \le 10^6$).
  4. Suppose a problem has "shortest path" in its description. Name three different algorithms that might apply and the constraint conditions under which each wins.
  5. A teammate proposes solving a routing problem "with DP." What three questions do you ask before accepting?

Mini Drill or Application​

Triage each problem briefly. State the chosen paradigm and the expected runtime.

  1. Count inversions in an array of $n = 10^6$ integers.
  2. Given $n = 20$ items with (weight, value), maximize value subject to $\sum w \le W$.
  3. On a graph with $n = 10^4$ nodes, find the shortest path from $s$ to $t$ with non-negative weights.
  4. Schedule $n = 10^5$ activities with start/finish times to maximize the count chosen.
  5. Schedule $n = 10^5$ activities with start/finish times and value $v_i$ to maximize total value.
  6. Count the number of ways to partition $n = 30$ into positive integer parts.
  7. Given $n = 10^9$ and $k = 10$, find the $k$-th smallest number coprime to $n$.
  8. Given a string of length $10^5$, find the longest palindromic substring.
  9. Given $10^6$ intervals, count points covered by at least $k$ intervals (for each query point).
  10. Implementation drill. For three problems of your choice above, write a two-line ADR: "We pick paradigm $X$ because triage axes $A, B, C$ rule out alternatives $Y, Z$; expected runtime $R$." This is exactly the discipline S7 M5 expects of architectural decisions, transposed to algorithmic ones.

Read This Only If Stuck​