What is Mo's Algorithm for offline range queries?
ā Interview Prompt: Explain Mo's Algorithm for offline range queries in O((N+Q)āN), query ordering, and block decomposition.
Mo's Algorithm processes offline range queries in $O((N + Q) \sqrt{N})$ by sorting queries to minimise the total movement of left and right pointers.
Core Idea:
Divide array into blocks of size $\sqrt{N}$.
Sort queries: primary by block of left endpoint, secondary by right endpoint (alternating for better cache performance).
Processing: Expand/shrink the window [l, r] by moving pointers, maintaining a running data structure (frequency map, etc.).
Each right pointer moves $O(N)$ times per block ($Q \cdot \sqrt{N}$ total), each left pointer moves $O(\sqrt{N})$ per query ($Q \cdot \sqrt{N}$ total).
Code Implementation Example
function moAlgorithm(
arr: number[], queries: [number, number, number][] // [l, r, queryIndex]
): number[] {
const n = arr.length, Q = queries.length;
const block = Math.ceil(Math.sqrt(n));
const answers = new Array(Q);
const freq = new Map<number, number>();
let distinct = 0;
queries.sort((a, b) => {
const ba = Math.floor(a[0] / block), bb = Math.floor(b[0] / block);
if (ba !== bb) return ba - bb;
return ba % 2 === 0 ? a[1] - b[1] : b[1] - a[1]; // alternating sort
});
const add = (idx: number) => {
const f = (freq.get(arr[idx]) ?? 0) + 1;
freq.set(arr[idx], f);
if (f === 1) distinct++;
};
const remove = (idx: number) => {
const f = freq.get(arr[idx])! - 1;
freq.set(arr[idx], f);
if (f === 0) distinct--;
};
let l = 0, r = -1;
for (const [ql, qr, qi] of queries) {
while (r < qr) add(++r);
while (l > ql) add(--l);
while (r > qr) remove(r--);
while (l < ql) remove(l++);
answers[qi] = distinct; // answer for this query
}
return answers;
}Mo's Algorithm is a sqrt-decomposition offline range query technique. It is optimal for problems where queries cannot be answered online (e.g., distinct count in range).