Pattern Guide
Mo's Algorithm
"Sort offline queries to minimize total movement. O((n+q)√n) for range queries."
Mo's algorithm answers offline range queries in O((n+q)√n) by sorting queries cleverly. Divide array into blocks of size √n. Sort queries: first by block of left endpoint, then by right endpoint (alternating direction for even/odd blocks). Maintain a running answer as you expand/contract the window by one element at a time. Each element is added/removed O(√n) times total.
Problems you can solve with this pattern
4 problems · click any to start solving
function moAlgorithm(n, queries, add, remove, getAnswer) {
// queries: [{l, r, idx}]
const block = Math.ceil(Math.sqrt(n));
// Sort: by block of l, then by r (alternating for cache efficiency)
queries.sort((a, b) => {
const ba = Math.floor(a.l / block), bb = Math.floor(b.l / block);
if (ba !== bb) return ba - bb;
return ba % 2 === 0 ? a.r - b.r : b.r - a.r; // alternating
});
const answers = new Array(queries.length);
let curL = 0, curR = -1;
for (const {l, r, idx} of queries) {
// Expand/contract to [l, r]
while (curR < r) add(++curR);
while (curL > l) add(--curL);
while (curR > r) remove(curR--);
while (curL < l) remove(curL++);
answers[idx] = getAnswer();
}
return answers;
}
// Example: count distinct elements in range [l, r]
// add(i): freq[arr[i]]++; if freq[arr[i]] === 1: distinctCount++
// remove(i): freq[arr[i]]--; if freq[arr[i]] === 0: distinctCount--
// getAnswer(): return distinctCountMo's algorithm works when: (1) queries are offline (all known beforehand), (2) you can maintain an answer incrementally as the window expands/contracts by one element. The key insight: sort queries so the total movement of L and R pointers is minimized. With block size √n, R moves O(n) per block (O(n√n) total), and L moves O(√n) per query (O(q√n) total). Total: O((n+q)√n).
function moAlgorithm(n, queries, add, remove, getAnswer) {
// queries: [{l, r, idx}]
const block = Math.ceil(Math.sqrt(n));
// Sort: by block of l, then by r (alternating for cache efficiency)
queries.sort((a, b) => {
const ba = Math.floor(a.l / block), bb = Math.floor(b.l / block);
if (ba !== bb) return ba - bb;
return ba % 2 === 0 ? a.r - b.r : b.r - a.r; // alternating
});
const answers = new Array(queries.length);
let curL = 0, curR = -1;
for (const {l, r, idx} of queries) {
// Expand/contract to [l, r]
while (curR < r) add(++curR);
while (curL > l) add(--curL);
while (curR > r) remove(curR--);
while (curL < l) remove(curL++);
answers[idx] = getAnswer();
}
return answers;
}
// Example: count distinct elements in range [l, r]
// add(i): freq[arr[i]]++; if freq[arr[i]] === 1: distinctCount++
// remove(i): freq[arr[i]]--; if freq[arr[i]] === 0: distinctCount--
// getAnswer(): return distinctCount- Offline: all queries known upfront
- Incremental: can add/remove one element and update answer in O(1) or O(log n)
- Works for: distinct count, sum, XOR, frequency queries
Block size selection:
- Typical: √n ≈ 300-350 for n = 100,000
- Optimal: n/√q if q queries
- Alternating sort (even blocks right→left, odd blocks left→right) reduces constant by ~2x
Mo's on trees: Euler tour the tree to flatten, then apply Mo's on the flattened array. Handles path queries offline.
Time complexity: O((n + q) · √n). For n = q = 10^5: ~3 × 10^7 operations — fits in 2-3 seconds.