Introduction

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⋅q)O(n \cdot q) to O((n+q)n)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.

Try It

The array below holds 16 numbers. Click Add query to register a range [L,R][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">Array of 16 numbers. Click two cells to select <b>L</b> and <b>R</b>, then <b>Add query</b>. Hit <b>Run Mo’s Algorithm</b> to process all queries in Mo’s optimized order and count distinct values in each range.</p>
<div id="array-display"></div>
<div class="controls">
  <span id="sel-label">Select L then R on the array above</span>
  <button id="add-btn" type="button" disabled>Add query</button>
  <button id="run-btn" type="button" disabled>Run Mo’s Algorithm</button>
  <button id="reset-btn" type="button" class="ghost">Clear all</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; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Mo’s Algorithm for distinct-count range queries.
// Time complexity: O((n+q)*sqrt(n)) vs naive O(n*q).
const ARR = [3,1,4,1,5,9,2,6,5,3,5,8,9,7,9,3];
const N = ARR.length;
const BLOCK = Math.ceil(Math.sqrt(N)); // 4

let selL = -1, selR = -1;
let queries = []; // {l, r, idx}

// --- Render the array ---
function renderArray() {
  const d = document.getElementById('array-display');
  d.innerHTML = '';
  ARR.forEach((v, i) => {
    const el = document.createElement('div');
    el.className = 'cell';
    el.textContent = v;
    el.dataset.i = i;
    if (i === selL) el.classList.add('sel-l');
    else if (i === selR) el.classList.add('sel-r');
    else if (selL !== -1 && selR !== -1 && i > selL && i < selR) el.classList.add('in-range');
    el.addEventListener('click', () => onCellClick(i));
    d.appendChild(el);
  });
}

function onCellClick(i) {
  if (selL === -1 || (selL !== -1 && selR !== -1)) {
    selL = i; selR = -1;
    document.getElementById('sel-label').textContent = fmt('Now click R (must be ≥ L = %i%)', { i: i });
    document.getElementById('add-btn').disabled = true;
  } else {
    if (i < selL) { selL = i; selR = -1;
      document.getElementById('sel-label').textContent = fmt('Now click R (must be ≥ L = %i%)', { i: i });
      return;
    }
    selR = i;
    document.getElementById('sel-label').textContent = fmt('Range [%selL%, %selR%] selected', { selL: selL, selR: selR });
    document.getElementById('add-btn').disabled = false;
  }
  renderArray();
}

// --- Queries list ---
function renderQueries() {
  const d = document.getElementById('queries-area');
  d.innerHTML = queries.length ? '<div style="font-size:.8rem;font-weight:600;margin-bottom:.2rem">Queries (in order added):</div>' : '';
  queries.forEach((q, i) => {
    const row = document.createElement('div');
    row.className = 'q-row';
    row.innerHTML = 'Q' + (i+1) + ': [' + q.l + ', ' + q.r + ']<span class="rm" data-i="' + i + '">✕</span>';
    d.appendChild(row);
  });
  d.querySelectorAll('.rm').forEach(el => el.addEventListener('click', e => {
    const idx = +e.target.dataset.i;
    queries.splice(idx, 1);
    queries.forEach((q, j) => q.idx = j);
    renderQueries();
    document.getElementById('run-btn').disabled = queries.length === 0;
    document.getElementById('result-area').innerHTML = '';
  }));
}

document.getElementById('add-btn').addEventListener('click', () => {
  if (selL < 0 || selR < 0) return;
  queries.push({ l: selL, r: selR, idx: queries.length });
  selL = -1; selR = -1;
  document.getElementById('sel-label').textContent = 'Select L then R on the array above';
  document.getElementById('add-btn').disabled = true;
  document.getElementById('run-btn').disabled = false;
  renderArray();
  renderQueries();
  document.getElementById('result-area').innerHTML = '';
});

document.getElementById('reset-btn').addEventListener('click', () => {
  queries = []; selL = -1; selR = -1;
  document.getElementById('sel-label').textContent = 'Select L then R on the array above';
  document.getElementById('add-btn').disabled = true;
  document.getElementById('run-btn').disabled = true;
  renderArray(); renderQueries();
  document.getElementById('result-area').innerHTML = '';
});

// --- Mo’s Algorithm core ---
function moSort(qs) {
  return [...qs].sort((a, b) => {
    const ba = Math.floor(a.l / BLOCK), bb = Math.floor(b.l / BLOCK);
    if (ba !== bb) return ba - bb;
    // Within same block: sort by r ascending if block is even, descending if odd (optimization)
    return ba % 2 === 0 ? a.r - b.r : b.r - a.r;
  });
}

function moRun(qs) {
  const freq = new Int32Array(10 + 1); // values 1-9, index by value
  let distinct = 0, curL = 0, curR = -1;
  let totalMoves = 0;
  const answers = new Array(qs.length);

  const add = (i) => {
    const v = ARR[i];
    if (freq[v] === 0) distinct++;
    freq[v]++;
  };
  const remove = (i) => {
    const v = ARR[i];
    freq[v]--;
    if (freq[v] === 0) distinct--;
  };

  const sorted = moSort(qs);
  sorted.forEach(q => {
    while (curR < q.r) { curR++; add(curR); totalMoves++; }
    while (curL > q.l) { curL--; add(curL); totalMoves++; }
    while (curR > q.r) { remove(curR); curR--; totalMoves++; }
    while (curL < q.l) { remove(curL); curL++; totalMoves++; }
    answers[q.idx] = { distinct, moOrder: sorted.indexOf(q) + 1 };
  });
  return { answers, totalMoves, sorted };
}

function naiveMoves(qs) {
  let total = 0;
  qs.forEach(q => total += (q.r - q.l + 1));
  return total;
}

document.getElementById('run-btn').addEventListener('click', () => {
  if (queries.length === 0) return;
  const { answers, totalMoves, sorted } = moRun(queries);
  const naive = naiveMoves(queries);

  let html = '<div class="res-header">Results (answered in Mo’s order, reported in original order):</div>';
  queries.forEach((q, i) => {
    const a = answers[i];
    // naive distinct count for verification
    const s = new Set();
    for (let j = q.l; j <= q.r; j++) s.add(ARR[j]);
    html += fmt('<div class="res-row"><span class="badge badge-blue">Q%i%%v% [%l%,%r%]</span><span class="badge badge-green">distinct = %distinct%</span><span class="badge badge-mo">Mo order #%moOrder%</span></div>', { i: i, v: 1, l: q.l, r: q.r, distinct: a.distinct, moOrder: a.moOrder });
  });
  html += fmt('<div style="margin-top:.5rem;font-size:.82rem;">📊 Mo pointer moves: <b>%totalMoves%</b> &nbsp;|&nbsp; Naive (rescan each): <b>%naive%</b>%v%</div>', { totalMoves: totalMoves, naive: naive, v: naive > totalMoves ? ' &nbsp;<span style="color:#0a7d33">' + fmt('Mo saved %v% moves', { v: naive - totalMoves }) + '</span>' : '' });
  html += fmt('<div style="font-size:.78rem;color:#666;margin-top:.2rem">Mo order: %map%</div>', { map: sorted.map((q, i) => 'Q' + (q.idx+1) + '[' + q.l + ',' + q.r + ']').join(' → ') });
  document.getElementById('result-area').innerHTML = html;
  console.log('Mo answers:', answers.map((a,i) => 'Q'+(i+1)+'='+a.distinct).join(', '), '| Mo moves:', totalMoves, '| Naive:', naive);
});

renderArray();
Result
Console

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)n)O((n + q)\sqrt{n}) rather than O(n⋅q)O(n \cdot q).

The Real Complexity

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)O(n) moves per block, and there are n\sqrt{n} blocks, giving O(nn)O(n\sqrt{n}) total right-pointer moves.
  • Left pointer movement. Between consecutive queries in the same block the left pointer moves at most n\sqrt{n} steps (the block width). With qq queries that is O(qn)O(q\sqrt{n}) total left-pointer moves. Between blocks the left pointer can jump up to nn steps, but there are only n\sqrt{n} block transitions, adding another O(nn)O(n\sqrt{n}) term.
  • Grand total: O((n+q)n)O((n + q)\sqrt{n}), achieved by setting the block size to n\sqrt{n}.

For comparison:

  • Naive (rescan each query): O(n⋅q)O(n \cdot q) — catastrophic for q=nq = n.
  • Segment tree / BIT: O((n+q)log⁡n)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)O(\log n) per step.
  • Mo's Algorithm: O((n+q)n)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.

Where It Matters

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)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.

Conclusion

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.

Share this article

Pick a channel — or use your device's native share sheet.

Comments

Loading comments...

https://www.kipuhub.com/en/article/mos-algorithm/Content licensed under CC BY-NC 4.0.