Mo's Algorithm: Answering Offline Range Queries by Reordering Them

Some range-query problems have no neat segment-tree merge: "how many distinct values are in a[l..r]?" is the classic. If all queries are known up front, Mo's algorithm answers them with nothing more than a window that can add and remove one element.

The core idea

Keep a current window [L, R] and a running answer. Moving an edge by one position costs O(1) (add or remove one element). Answering queries in input order could make the edges zig-zag across the array every time. Mo's trick is to reorder the queries so the total edge movement stays small.

The ordering

Split indices into blocks of size B ≈ √n. Sort queries by (l // B, r). Within one block, R only moves rightward (O(n) per block), and L moves at most B per query. Total: O(n·n/B + q·B) = O((n + q)√n) when B = √n.

def mos(a, queries):
    B = max(1, int(len(a) ** 0.5))
    order = sorted(range(len(queries)),
                   key=lambda i: (queries[i][0] // B, queries[i][1]))
    cnt, distinct = {}, 0
    L, R = 0, -1
    ans = [0] * len(queries)
    def add(x):
        nonlocal distinct
        cnt[x] = cnt.get(x, 0) + 1
        if cnt[x] == 1: distinct += 1
    def remove(x):
        nonlocal distinct
        cnt[x] -= 1
        if cnt[x] == 0: distinct -= 1
    for i in order:
        l, r = queries[i]
        while R < r: R += 1; add(a[R])
        while L > l: L -= 1; add(a[L])
        while R > r: remove(a[R]); R -= 1
        while L < l: remove(a[L]); L += 1
        ans[i] = distinct
    return ans

Details interviewers probe

• Expand before shrinking. Extending the window first avoids a temporarily inverted window (L > R+1) that corrupts counts.
• Odd-even trick. Sort R ascending in even blocks and descending in odd blocks; R then snakes back instead of resetting, often halving runtime.
• Offline only. If queries arrive online or the array is updated, you need Mo's with updates (O(n^(5/3))) or a different structure.

When to reach for it

Distinct counts, frequency-of-mode questions, "number of pairs with equal values in a range", XOR-of-range-pairs problems: anywhere add/remove is easy but merging two halves is hard. Say: "Queries are offline and the window update is O(1), so Mo's gives O((n+q)√n)."

Disclosure: from the team at Linkjob AI (real-time interview help). Free to use for practice.