Mo's Algorithm

Suppose you have an array of numbers and a list of questions, each asking: "How many distinct values appear between index L and index R?" Answer one question and you're done in linear time. Answer a million of them naively and you'll be scanning billions of elements.

Mo's Algorithm — named after the competitive programmer Mo Tao — is a breathtakingly simple idea: instead of answering queries in the order they arrive, sort them first using a two-pointer block trick. By carefully controlling how much the left and right boundaries move between consecutive queries, the total work drops from $O(n \cdot q)$ to $O((n + q)\sqrt{n})$.

No segment tree. No heavy-light decomposition. No persistent structure. Just a clever sort and two pointers that crawl over the array — and for many problems that is all you need.

The array below holds 16 numbers. Click Add query to register a range $[L, R]$, then hit Run Mo's Algorithm to watch the algorithm process them in its optimized order and report the count of distinct values in each range.

<p class="hint">{{hint}}</p>
<div id="array-display"></div>
<div class="controls">
  <span id="sel-label">{{sel_initial}}</span>
  <button id="add-btn" type="button" disabled>{{btn_add}}</button>
  <button id="run-btn" type="button" disabled>{{btn_run}}</button>
  <button id="reset-btn" type="button" class="ghost">{{btn_clear}}</button>
</div>
<div id="queries-area"></div>
<div id="result-area"></div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; font-size: 14px; }
.hint { font-size: .88rem; color: #444; margin: 0 0 .6rem; line-height: 1.45; }
#array-display { display: flex; flex-wrap: wrap; gap: 4px; margin-bottom: .6rem; }
.cell { width: 36px; height: 36px; border-radius: 6px; border: 1.5px solid #cdd9e3;
        background: #e8eef3; display: flex; align-items: center; justify-content: center;
        font: 700 14px ui-monospace, monospace; cursor: pointer; user-select: none;
        transition: background .12s, border-color .12s; }
.cell:hover { background: #d0dce6; }
.cell.sel-l { background: #457b9d; border-color: #1d3557; color: #fff; }
.cell.sel-r { background: #e63946; border-color: #c92f3c; color: #fff; }
.cell.in-range { background: #a8dadc; border-color: #457b9d; }
.controls { display: flex; flex-wrap: wrap; align-items: center; gap: .5rem; margin-bottom: .6rem; }
#sel-label { font-size: .82rem; color: #555; flex: 1 1 120px; }
button { font: 600 13px system-ui; padding: .38rem .8rem; border: 1.5px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 7px; cursor: pointer; }
button:disabled { opacity: .45; cursor: default; }
button.ghost { background: #fff; color: #1d3557; }
#queries-area { margin-bottom: .5rem; }
.q-row { display: inline-flex; align-items: center; gap: .4rem; background: #f0f4f7;
         border: 1px solid #cdd9e3; border-radius: 6px; padding: .25rem .5rem;
         margin: .2rem .2rem 0 0; font-size: .82rem; }
.q-row .rm { cursor: pointer; color: #c92f3c; font-weight: 700; margin-left: .3rem; }
#result-area { min-height: 2em; }
.res-header { font-weight: 700; margin-bottom: .3rem; font-size: .9rem; }
.res-row { display: flex; align-items: center; gap: .5rem; padding: .2rem 0;
           border-bottom: 1px solid #eee; font-size: .85rem; }
.res-row:last-child { border-bottom: none; }
.badge { display: inline-block; padding: .1rem .4rem; border-radius: 4px; font-weight: 700;
         font-size: .78rem; }
.badge-blue { background: #457b9d22; color: #1d3557; }
.badge-green { background: #0a7d3322; color: #0a7d33; }
.badge-mo { background: #e6394622; color: #c92f3c; }
.naive-cost { color: #888; font-size: .78rem; }

// Code not found

Notice two things. First, the naive order (answering each query from scratch) rescans the full range every time. Second, Mo's sorted order keeps the right pointer moving mostly forward within each block, while the left pointer only jumps at block boundaries — keeping total movement to $O((n + q)\sqrt{n})$ rather than $O(n \cdot q)$.

Why does the reordering help? Break the analysis into two pointers:

• Right pointer movement. Queries within the same block are sorted by their right endpoint. The right pointer sweeps left to right across the array and never reverses inside a block — at most $O(n)$ moves per block, and there are $\sqrt{n}$ blocks, giving $O(n\sqrt{n})$ total right-pointer moves.
• Left pointer movement. Between consecutive queries in the same block the left pointer moves at most $\sqrt{n}$ steps (the block width). With $q$ queries that is $O(q\sqrt{n})$ total left-pointer moves. Between blocks the left pointer can jump up to $n$ steps, but there are only $\sqrt{n}$ block transitions, adding another $O(n\sqrt{n})$ term.
• Grand total: $O((n + q)\sqrt{n})$, achieved by setting the block size to $\sqrt{n}$.

For comparison:

• Naive (rescan each query): $O(n \cdot q)$ — catastrophic for $q = n$.
• Segment tree / BIT: $O((n + q)\log n)$ for sum/min/max, but those structures cannot answer arbitrary add/remove queries like distinct count in $O(\log n)$ per step.
• Mo's Algorithm: $O((n + q)\sqrt{n})$ — no data structure overhead, just arithmetic on pointers.

The algorithm was known informally in competitive programming circles. Mo Tao popularised it around 2011 via Codeforces discussions; it is now a standard technique in competitive programming curricula.

Mo's approach is closely related to sqrt decomposition and the broader family of offline query algorithms. Its power is that any range function that supports O(1) element addition and removal can be plugged in unchanged — distinct count, XOR, frequency mode, and many more.

The distinct-count demo is the canonical example, but the same block-sort trick works for any query where adding or removing one element from the window costs $O(1)$:

• Competitive programming: Mo's is a go-to when the problem says "offline" and queries have range structure — frequency statistics, XOR aggregates, color counts in trees (Mo's on trees), inversions in a range.
• Database analytics: offline analytical queries over a fact table often resemble range queries on a sorted key dimension. The same block-sorting intuition underpins some cache-aware scan strategies.
• Bioinformatics: k-mer frequency queries over a DNA sequence window share the sliding-window structure that Mo's Algorithm exploits.
• Teaching algorithm design: Mo's Algorithm is a perfect lesson in problem reduction — the hard part isn't the data structure, it's realizing you can reorder the questions.

For online queries (where each answer must be given before the next query arrives), Mo's Algorithm doesn't apply directly — you need segment trees or Fenwick trees. But for batch workloads, the √n trick is often unbeatable in practice.

Mo's Algorithm carries a lesson that reaches beyond range queries: sometimes the hardest-looking problems become easy when you rearrange the order in which you solve sub-problems.

The naive approach rescans the array for every query. Mo's approach sorts the queries so that consecutive ones differ by only a tiny window shift. The algorithm does the same work — it just packs it into the smallest possible sequence of pointer moves.

The next time a batch of range questions seems to demand a heavy data structure, ask whether answering them offline in a smarter order might be enough. Often, a √n block and a careful sort is all it takes.