Vibe Engines
YouTube

Vibe Engines is free, interactive AI engineering & system design — runs in your browser. Pick a learning path

Algorithms · Ranges

Reorder to Win.

Watch the explainer

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.

Total time
O((n+q)·√n)
Naive
O(q·n)
Requirement
offline
Block size
√n

The code

# Mo's algorithm: answer q offline range queries block = int(n ** 0.5) queries.sort(key=lambda q: (q.l // block, q.r)) # the crucial order curL, curR, answer = 0, -1, 0 for q in queries: while curR < q.r: curR += 1; add(a[curR]) # extend right while curL > q.l: curL -= 1; add(a[curL]) # extend left while curR > q.r: remove(a[curR]); curR -= 1 # shrink right while curL < q.l: remove(a[curL]); curL += 1 # shrink left ans[q.id] = answer # O(1) running answer

Quick check

1. What does Mo’s algorithm require of the queries?

2. What is the key ordering Mo’s algorithm sorts queries by?

3. What is Mo’s algorithm’s total time for q queries on an n-element array?

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

L in 0–3L in 4–7L in 8–11L in 12–15 1. [1,5]2. [0,7]3. [3,11]4. [2,14]5. [4,8]6. [6,10]7. [9,15]8. [12,15] pointer moves: 99 in the given order, 44 in Mo’s order
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.

QueryPointer moveValuesWindowDistinct
#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

CaseTimeSpaceWhy
Mo’s algorithmO((n + q)·√n)O(n + q)Block size about √n; each pointer move is an O(1) add or remove.
Recount every queryO(q·n)O(n)Scan the range into a set or table, once per query. No ordering needed.
Slide in the given orderno better than O(q·n)O(n)The window travels the full distance between consecutive random queries.
Mo’s with alternating directionsame bound, smaller constantO(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
  1. 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.
  2. 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.
  3. 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.
  4. Sort by block of the left endpoint (block size ≈ √n), then by the right endpoint. Inside a block the right pointer only moves forward.
  5. 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.
  6. Alternate the right-endpoint direction per block if you want the constant factor down — same complexity, less zig-zag.
  7. 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.
  8. It only works offline. If queries arrive one at a time and must be answered immediately, none of this is available to you.
CPython · WebAssembly

Keep going

▶  Watch it explained

Mo's Algorithm: Time and Space Complexity, From First Principles

Finished this one? 0 / 99 Algorithms done
NextSix Degrees: Union-Find Closest algorithm to this one

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms