You have an array and a big batch of range queries — “what’s the answer on [l, r]?” — that you can answer offline (all at once, in any order). Mo’s algorithm keeps a single window with two pointers and slides them from one query’s range to the next, using cheap add and remove steps at the ends. If you processed the queries in their given order, the pointers would thrash back and forth for O(q·n) total movement. The trick is the order: sort queries by the √n-sized block of their left endpoint (then by right endpoint), and the total movement collapses to O((n+q)·√n). Watch reordering slash the pointer movement.
O((n+q)·√n) total · offline queries only · sort by √n block of L, then by R
offline
All queries are known up front and may be answered in any order.
window
One current range [curL, curR] with an incrementally maintained answer.
add / remove
Extend or shrink the window by one element at an end — a cheap O(1) update.
Mo's order
Sort queries by (block of L = ⌊L/√n⌋, then R). This bounds total pointer movement.
mo.js — the same queries, a smarter order
Ready
Eight range queries over a 16-element array. Sorted in Mo’s order, we keep one window and slide its ends to each query in turn. Step to process the next query and count the add/remove moves.
0/8
queries done
0
total moves
99
naive order
How it works
The magic is entirely in the sort key. Group the queries by which √n-sized block their left endpoint falls in. Within a block, sort by the right endpoint. Now two things are bounded. The left pointer only ever moves within a block between consecutive queries, so it travels at most √n per query — O(q·√n) overall. The right pointer, because queries within a block are sorted by R, marches mostly forward within each block and resets at most once per block, for O(n·√n / √n) = O(n·√n)… more precisely O(n·√n) total across all blocks. Add them and the whole batch costs O((n+q)·√n) pointer moves, each a constant-time add/remove — dramatically less than answering each query from scratch.
1
Collect queries offline
Read all q range queries first. Mo’s algorithm needs them up front because it will answer them in a rearranged order.
2
Sort by (block of L, then R)
Choose block size ≈ √n. Sort queries by ⌊L/√n⌋, breaking ties by R. This ordering is what bounds the total pointer travel.
3
Slide the window
Maintain one window [curL, curR] and its answer. For each query, move the two ends to the query’s l and r with add/remove steps, updating the running answer in O(1) each.
✓
O((n+q)·√n) total
The sorted order keeps the left pointer within a block (√n per query) and the right pointer mostly monotic within a block, so all the sliding sums to O((n+q)·√n) — then map answers back to original query order.
1. What does Mo’s algorithm require of the queries?
Mo’s algorithm rearranges the queries to minimize pointer movement, so it must know all of them up front and be free to answer them in a different order — that is, they must be offline.
2. What is the key ordering Mo’s algorithm sorts queries by?
Sort by (⌊L/√n⌋, R). Grouping by the left endpoint’s √n block bounds left-pointer movement to √n per query, and sorting by R within a block keeps the right pointer mostly monotonic — together giving O((n+q)·√n).
3. What is Mo’s algorithm’s total time for q queries on an n-element array?
The clever sort bounds total pointer movement to O((n+q)·√n), each move an O(1) add/remove — far better than the O(q·n) of answering each query by scanning its range.
FAQ
What is Mo's algorithm?
An offline technique for answering many range queries on a static array. It keeps one window with two pointers and a running answer, and processes queries sorted by (√n block of L, then R) so pointer movement between queries is cheap — O((n+q)·√n) total, far better than answering each independently.
Why does the √n block ordering make it fast?
Grouping by the √n block of L keeps the left pointer within a block (≤√n per query → O(q·√n)). Sorting within a block by R keeps the right pointer mostly forward, resetting once per block (→ O(n·√n)). The sum is O((n+q)·√n).
What problems is Mo's algorithm used for?
Range queries whose answer updates incrementally as elements enter/leave the window: distinct count in a range, most-frequent element, sum of squared frequencies, and many frequency/mode questions. It needs O(1)-ish add/remove updates and a static array.
What are the limitations of Mo's algorithm?
It’s offline-only, basic version needs a static array (a harder O(n^(5/3)) variant allows updates), and requires cheap add/remove answer maintenance. When you need online queries or frequent updates, a segment tree or similar is usually better.
SOLVE IT YOURSELF
Solve it: answer the queries out of order
Some range queries have no clean segment-tree merge — "how many distinct values in this range?" is the classic. Mo's trick: you are allowed to answer offline, so reorder the queries into an order where consecutive ones barely differ, then slide two pointers. Python or TypeScript.
YOUR TASK
Implement mos(data, queries) returning the count of distinct values in each inclusive range, in the original query order. Track MOVES: how many single-step pointer moves it took.
HINTS — 8 IDEAS
Keep a window [cur_l, cur_r] and a frequency table. Widening by one element is O(1): bump its count, and if it just became 1 the distinct count rises.
Shrinking is the mirror image: drop the count, and if it just hit 0 the distinct count falls. Every step is O(1) — only the number of steps needs controlling.
Answering in the given order can cost O(n) per query. Since the queries are all known up front, you may answer them in any order and reorder the results afterwards.
Sort by block of the left endpoint (block size ≈ √n), then by the right endpoint. Inside a block the right pointer only moves forward.
That gives O((n+q)√n) total pointer movement: the right pointer sweeps at most n per block over √n blocks, and the left pointer moves at most √n per query.
Alternate the right-endpoint direction per block if you want the constant factor down — same complexity, less zig-zag.
Store each query's original index before sorting, or the answers come back scrambled. This is the single most common way to get Mo's wrong.
It only works offline. If queries arrive one at a time and must be answered immediately, none of this is available to you.