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.
The picture: sort so the window barely moves
The eight queries from the page’s simulator (16 elements, block size 4), listed in the order Mo’s algorithm answers them. Bars that start in the same block of left endpoints sit together and run in increasing order of right endpoint. Answering them in the order they were asked takes 99 single-step pointer moves; this order takes 44.
Worked example, step by step
Take the page’s array [1, 1, 2, 1, 3, 3, 2, 4] and four queries asking for the number of distinct values: #0 [0,3], #1 [2,5], #2 [0,7], #3 [4,4]. With n = 8 the block size is 2, so the sort key is (⌊l/2⌋, r) and the order is #0, #2, #1, #3. One window is kept; +v adds a value, −v removes one.
Query
Pointer move
Values
Window
Distinct
#0 [0,3]
extend right
+1, +1, +2, +1
[0,3]
2
#2 [0,7]
extend right
+3, +3, +2, +4
[0,7]
4
#1 [2,5]
shrink right
−4, −2
[0,5]
3
shrink left
−1, −1
[2,5]
3
#3 [4,4]
shrink right
−3
[2,4]
3
shrink left
−2, −1
[4,4]
1
Each query costs only the distance the window has to travel: 4, 4, 4 and 3 steps, 15 in total, where answering in the given order would take 19. The row for #1 shows both ends moving at once (the right end shrinks from 7 to 5 and the left end from 0 to 2), and the removals keep the counts honest: the 4 disappears, so distinct drops from 4 to 3. The answers come out in sorted order as 2, 4, 3, 1, so each is stored under its query’s original number, and only then does the output read 2, 3, 4, 1.
Complexity and trade-offs
Case
Time
Space
Why
Mo’s algorithm
O((n + q)·√n)
O(n + q)
Block size about √n; each pointer move is an O(1) add or remove.
Recount every query
O(q·n)
O(n)
Scan the range into a set or table, once per query. No ordering needed.
Slide in the given order
no better than O(q·n)
O(n)
The window travels the full distance between consecutive random queries.
Mo’s with alternating direction
same bound, smaller constant
O(n + q)
Sort the right endpoint downward in every other block so it does not have to run back.
Offline Fenwick tree (distinct count only)
O((n + q) log n)
O(n + q)
Sort queries by right end and keep a marker at each value’s last position. Faster for this query, but only works for this kind of question.
Measured with a seeded array of 1,000 values from 0 to 99 and 1,000 random ranges (block size 31): Mo’s order made 40,350 pointer moves, the odd-even variant 27,006, answering in the given order 540,322, and recounting each range read 344,432 elements. Every Mo’s answer matched the direct count. So the sort is the whole algorithm, and the price is that it is offline: every query must be known before the first answer, and the aggregate must support constant-time add and remove.
Common mistakes
Returning answers in sorted order
The sorted order is #0, #2, #1, #3, so the answers are produced as 2, 4, 3, 1. Printing them as they come out gives [2, 4, 3, 1] instead of [2, 3, 4, 1]. Keep each query’s original index through the sort and write ans[original] = value.
Starting with the window at [0, 0]
The empty window is cur_l = 0, cur_r = −1. Starting at cur_r = 0 without adding a[0] means the first element is never counted: on the page’s array the query [0, 0] returned 0 instead of 1.
A block size of 1 or n
With 1,000 elements and 1,000 queries, block 1 (sort by left end) made 213,888 moves and block n (sort by right end only) made 223,968, against 40,350 for the 31-element block. Block 10 made 84,016 and block 300 made 95,224. The √n choice balances left-pointer wandering inside a block against right-pointer sweeps across blocks.
Doing real work in add and remove
If add or remove costs time proportional to the window, for example by recomputing len(set(a[l:r+1])), the algorithm degrades to the plain recount. That read 344,432 elements in the test above against 40,350 constant-time moves. The aggregate must update in O(1) per element.
Not sorting, or sorting by one key
Sliding a window across the queries in the order they arrive is worse than recounting: 540,322 moves against 344,432 element reads in the same test. The pair (block of l, then r) is what bounds the travel.
Where this shows up
Range queries with no inverse
Distinct count, most frequent value and “how many pairs of equal values” cannot be answered with prefix sums, because you cannot subtract one prefix from another. They can be maintained under single-element add and remove, which is exactly what Mo’s algorithm needs.
Offline batches
Whenever all queries are known up front, such as a report that runs a batch of range questions over a fixed array, reordering them before answering is allowed. The same idea of reordering work so a cursor travels less is why disk schedulers sort requests by position.
Tree and 2-D variants
Flattening a tree with an Euler tour turns path and subtree questions into range questions, so the same sort applies to trees. An added time dimension handles array updates between queries, at a higher cost.
Programming contests
It is a standard tool for range problems with a limit of a few hundred thousand elements, where an O(q·n) recount is too slow and a segment tree cannot merge the answers.
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.