What is Mo's Algorithm?
Learn how Mo's algorithm answers many offline range queries in O((n+q)sqrt(n)) time using a sliding window.
Expected Interview Answer
Mo's algorithm answers many offline range queries on a static array efficiently by sorting queries into blocks of size sqrt(n) and moving a sliding [L, R] window incrementally between queries, achieving O((n + q) sqrt(n)) total time instead of O(n) per query.
All queries must be known in advance (offline) since the technique reorders them for processing efficiency rather than answering them in input order. Queries are sorted by block index of L (dividing the array into sqrt(n)-sized blocks) and, within the same block, by R, which minimizes the total movement of the window's endpoints across all queries. Moving from one query's [L, R] to the next only adds or removes elements at the window's edges — an O(1) add/remove operation per index — rather than recomputing the answer from scratch, so the amortized total pointer movement across all queries is bounded by O((n + q) sqrt(n)). This makes it the standard tool for problems like 'count distinct elements in range' or 'range mode' where no simpler prefix-sum trick applies but all queries are known upfront.
- O((n + q) sqrt(n)) total time for q offline range queries
- Works for queries with no simple prefix-sum decomposition
- Only needs O(1) add/remove operations per window shift
- Handles complex aggregates like distinct counts or mode
AI Mentor Explanation
A groundskeeper must answer many requests to compute pitch wear statistics for different over-ranges of a long tournament, and all the requests arrive before play starts. Instead of re-measuring the whole range for every request, the groundskeeper sorts requests into sqrt(n)-sized over-blocks and processes them so the measuring tape only ever slides slightly left or right between consecutive requests, adding or removing one over's data at a time. This turns a job that would cost a full re-measurement per request into one where the tape's total movement across all requests is bounded, roughly sqrt(n) per request on average. It only works because every request was known in advance, letting the groundskeeper choose the most efficient visiting order rather than answering them as they arrive.
Step-by-Step Explanation
Step 1
Collect all queries offline
Read every [L, R] query in advance since Mo's algorithm requires reordering them.
Step 2
Sort into sqrt(n) blocks
Sort queries by block index of L (block size roughly sqrt(n)), and by R within the same block (alternating direction is a common optimization).
Step 3
Slide the window incrementally
Move current_l and current_r one step at a time between consecutive queries, adding or removing elements with O(1) update functions.
Step 4
Record answers in original order
Store each query’s computed answer, then output results in the original input order.
What Interviewer Expects
- Explain why Mo's algorithm requires offline (precollected) queries
- Justify the sqrt(n) block sizing and sort order for minimizing pointer movement
- Describe the O(1) add/remove functions needed to maintain the running answer
- State the overall O((n + q) sqrt(n)) complexity
Common Mistakes
- Trying to apply Mo's algorithm to online queries that must be answered immediately
- Forgetting the odd/even block alternating trick, which degrades performance without it
- Using an O(log n) or worse add/remove step, which breaks the sqrt(n) complexity bound
- Not restoring answers to the original query order before output
Best Answer (HR Friendly)
“Mo's algorithm answers a big batch of range queries efficiently by reordering them so a sliding window only shifts a little between consecutive queries instead of resetting each time. I would reach for it when I have many offline range queries and no simpler prefix-sum trick works, like counting distinct elements in a range.”
Code Example
import math
def mos_algorithm(arr, queries):
n = len(arr)
block_size = max(1, int(math.sqrt(n)))
def sort_key(q):
idx, l, r = q
block = l // block_size
return (block, r if block % 2 == 0 else -r)
indexed = [(i, l, r) for i, (l, r) in enumerate(queries)]
indexed.sort(key=sort_key)
freq = {}
distinct = 0
def add(x):
nonlocal distinct
freq[x] = freq.get(x, 0) + 1
if freq[x] == 1:
distinct += 1
def remove(x):
nonlocal distinct
freq[x] -= 1
if freq[x] == 0:
distinct -= 1
answers = [0] * len(queries)
cur_l, cur_r = 0, -1
for idx, l, r in indexed:
while cur_r < r:
cur_r += 1
add(arr[cur_r])
while cur_r > r:
remove(arr[cur_r])
cur_r -= 1
while cur_l < l:
remove(arr[cur_l])
cur_l += 1
while cur_l > l:
cur_l -= 1
add(arr[cur_l])
answers[idx] = distinct
return answersFollow-up Questions
- How would you adapt Mo's algorithm to support updates (Mo's algorithm with updates / 3D Mo's)?
- Why does alternating sort direction within a block improve Mo's algorithm's practical speed?
- When would a merge sort tree or wavelet tree be a better choice than Mo's algorithm?
- How would you parallelize Mo's algorithm across multiple threads?
MCQ Practice
1. What is the total time complexity of Mo's algorithm for n elements and q queries?
Sorting queries into sqrt(n)-sized blocks bounds the total pointer movement across all queries to O((n + q) sqrt(n)).
2. What is a required precondition for applying Mo's algorithm?
Mo's algorithm reorders queries for efficiency, which only works when the full query set is known beforehand.
3. What determines the primary sort key when ordering queries for Mo's algorithm?
Queries are primarily sorted by which sqrt(n)-sized block their left endpoint L falls into, then by R within each block.
Flash Cards
What problem type does Mo's algorithm solve? — Many offline range queries on a static array, especially ones without a simple prefix-sum decomposition.
What is the block size used in Mo's algorithm? — Approximately sqrt(n), where n is the array length.
What is the overall time complexity of Mo's algorithm? — O((n + q) sqrt(n)) for n elements and q queries.
Why must add/remove operations be O(1) for Mo's algorithm to work? — Because the algorithm relies on cheap incremental window updates; anything slower breaks the sqrt(n) bound.