You have an array of 100,000 elements and 100,000 queries, each asking "how many distinct values are in the range [L, R]?" A brute force scan per query gives O(n) each, totaling O(n q) which is roughly 10^10 operations. That is far too slow. A segment tree could help for some query types, but maintaining distinct counts across arbitrary ranges is awkward to merge. Mo's Algorithm solves this class of problems in O((n + q) sqrt(n)) using a beautifully simple idea: sort the queries in a clever order, then slide a window across the array, adding and removing one element at a time.

If you are comfortable with basic sorting and square root decomposition concepts, you are ready for this chapter. By the end, you will understand how Mo's Algorithm works, why its complexity is what it is, and how to implement it for a variety of offline range query problems.

Mo's Algorithm occupies a unique niche in the algorithmic toolkit. It is not the fastest approach for any single problem, but it is one of the most versatile techniques for offline range queries, problems where you receive all queries upfront and can answer them in any order.

The Problem

Consider an array arr of n elements and q queries, each of the form "compute some aggregate over the subarray arr[L..R]." The aggregate could be the count of distinct elements, the sum of element frequencies squared, the mode, or any decomposable statistic.

The naive approach processes each query independently by iterating from L to R, giving O(n) per query and O(n * q) total. For n = q = 100,000, that is 10^10 operations, which is far too slow.

You might think about prefix sums, but they only work for simple additive aggregates. For something like "count of distinct elements," prefix sums fall apart because the distinct count of [L, R] is not simply prefix[R] - prefix[L-1].

The Key Insight

Here is the core observation: if you already know the answer for the range [L, R], you can compute the answer for [L, R+1] by just adding one element (arr[R+1]). Similarly, you can go from [L, R] to [L+1, R] by removing one element (arr[L]). Each transition costs O(1) if your add and remove operations are O(1).

The question becomes: in what order should you process the queries so that the total pointer movement is minimized?

Mo's answer is to divide the array into blocks of size sqrt(n), then sort queries by (block number of L, R). Within the same block, queries are sorted by R. This guarantees that:

The result is O((n + q) * sqrt(n)) total pointer movement across all queries.

The Analogy

Imagine you are a librarian cataloging books on a long shelf. A patron gives you a list of requests: "count the unique titles between positions 10 and 50," "between positions 12 and 48," and so on. If you handle requests in the order they arrive, you might jump from one end of the shelf to the other for every request.

But if you group the requests by which section of the shelf the left endpoint falls in, and within each section sort by the right endpoint, you minimize your walking. Within a section, your left hand barely moves (it stays within a small zone), and your right hand sweeps steadily in one direction. That is Mo's Algorithm: organizing work to minimize total movement.

Visual Overview

Step 1: Choose the Block Size

Set the block size B = floor(sqrt(n)). Each index i in the array belongs to block i / B. For an array of size 16, the block size is 4, and indices 0-3 are in block 0, indices 4-7 are in block 1, and so on.

Step 2: Sort the Queries

Each query is a triple (L, R, original_index). Sort the queries using a comparator:

The alternating sort direction for R is a well-known optimization. Without it, when you transition from one block to the next, R might jump from a high value back to a low value, wasting O(n) movement. Alternating the direction means R sweeps forward in one block and backward in the next, keeping the transition smooth.

Step 3: Process Queries with a Sliding Window

Maintain a current window [curL, curR] that starts empty (for instance, curL = 0 and curR = -1). For each query (L, R) in sorted order:

The order matters here. It is generally safer to expand the window before shrinking it, which avoids the window temporarily becoming invalid (where curL > curR).

Step 4: The add and remove Functions

These are problem-specific. For counting distinct elements in a range:

Both operations are O(1), which is critical. Mo's Algorithm only works efficiently when add and remove are fast.

Let us trace through a concrete example. Consider the array:

Block size B = floor(sqrt(8)) = 2.

We have 5 queries asking for the count of distinct elements in each range:

Sorting the Queries

Block assignments: Q0 is in block 0, Q1 is in block 0, Q3 is in block 1, Q4 is in block 1, Q2 is in block 2.

Within block 0 (even), sort by R ascending: Q0(R=3), then Q1(R=5). Within block 1 (odd), sort by R descending: Q4(R=7), then Q3(R=5). Block 2 has only Q2.

Sorted order: Q0, Q1, Q4, Q3, Q2.

Processing Query by Query

We start with curL = 0, curR = -1, distinctCount = 0, and an empty frequency array.

Processing Q0: [0, 3]

Processing Q1: [1, 5]

Processing Q4: [3, 7]

Processing Q3: [2, 5]

Processing Q2: [4, 7]

Final Answers

Notice how the pointers moved relatively small distances between consecutive queries in sorted order. That is the whole point.

Here is a complete implementation of Mo's Algorithm for counting distinct elements in a range. The queries are sorted by the block of their left endpoint with an alternating sort direction on the right endpoint, then answered with a two-pointer window that adds and removes elements while maintaining a running count of distinct values.

Let us walk through the key parts of the implementation.

Query sorting. The comparator is the heart of the algorithm. It first groups queries by the block their left endpoint falls in (L / blockSize). Within the same block, it sorts by R, with even-numbered blocks sorting R ascending and odd-numbered blocks sorting R descending. This alternating pattern prevents the right pointer from jumping back to the start when transitioning between blocks.

The main loop. For each query in sorted order, four while-loops adjust the current window [curL, curR] to match the query's [L, R]. The order of these loops (expand right, shrink right, expand left, shrink left) ensures the window is always valid. After adjustment, the current answer is stored at the query's original index.

add and remove functions. These maintain a frequency array and a running distinct count. When adding an element, if its frequency increases from 0 to 1, it is a new distinct element. When removing, if its frequency drops from 1 to 0, we lose a distinct element. Both are O(1).

Common Mistakes:

Time Complexity

Overall: O((n + q) * sqrt(n))

This is the key claim. Let us break it down carefully.

Right pointer analysis. Within a single block of left endpoints, all queries have their L values in the same block of size sqrt(n). Since queries within a block are sorted by R (ascending or descending), the right pointer moves monotonically within each block. In the worst case, R sweeps across all n elements, so the right pointer moves at most O(n) per block. There are sqrt(n) blocks, giving O(n * sqrt(n)) total movement for the right pointer.

Left pointer analysis. When moving from one query to the next within the same block, the left endpoints differ by at most sqrt(n) (since they are all in the same block). So the left pointer moves at most O(sqrt(n)) per query. Across all q queries, that is O(q * sqrt(n)).

Combined: O(n sqrt(n)) for the right pointer + O(q sqrt(n)) for the left pointer = *O((n + q) sqrt(n))**.

For the typical case where n and q are roughly equal (both around 10^5), this gives approximately 10^5 316 = 3.16 10^7, which is very comfortable within a 1-2 second time limit.

Space Complexity

Overall: O(n + q + max_val)

In practice, if array values can be large, you should coordinate-compress them to the range [0, n) before running Mo's Algorithm. This keeps the frequency array at O(n).

Mo's Algorithm with Updates (Mo's with Modifications)

Standard Mo's is an offline algorithm for static arrays. But what if the array is modified between queries? Mo's with modifications (sometimes called "Mo's Algorithm with time") handles this.

The idea is to add a third dimension: time. Each query becomes (L, R, T), where T is the number of updates applied before this query. You sort queries by (block of L, block of R, T), using a block size of approximately n^(2/3) instead of sqrt(n).

When processing queries, you move three pointers: left, right, and time. Moving the time pointer forward applies an update, and moving it backward undoes the update. The total complexity becomes O(n^(5/3)) for n queries and n updates.

Mo's Algorithm on Trees

Mo's Algorithm is designed for arrays, but many tree problems can be reduced to array problems using an Euler tour. The Euler tour flattens the tree into an array, and paths or subtrees become ranges in that array. Once flattened, you apply standard Mo's on the resulting array.

The main subtlety is handling LCA queries. For a path from node u to node v, the Euler tour range might not directly correspond to the path. You need to handle the LCA node specially, sometimes adding it separately.

Block Size Optimization

The standard block size is sqrt(n), but the optimal block size depends on the ratio of n to q. If you have many more queries than array elements, a smaller block size helps. The theoretically optimal block size is:

For the common case where n is roughly equal to q, this simplifies back to sqrt(n).

Comparison Table

When should you choose Mo's Algorithm over other approaches? Here is how it stacks up.

When to Choose Mo's Algorithm

When NOT to Use Mo's Algorithm

Pattern 1: Distinct Elements in a Range

Problem type: Given an array and multiple queries [L, R], count the number of distinct elements in each range.

How Mo's helps: Maintain a frequency array. When adding an element, if its frequency goes from 0 to 1, increment the distinct count. When removing, if it drops to 0, decrement. This is the classic Mo's application.

Pattern 2: Sum of Squares of Frequencies

Problem type: For each query [L, R], compute the sum of f(x)^2 for all values x, where f(x) is the frequency of x in the range.

How Mo's helps: Maintain a running sum. When adding element x with current frequency f, subtract f^2, increment f, and add (f+1)^2. The net change is +2f+1. Similarly for removal. Both are O(1).

Pattern 3: XOR of Distinct Elements

Problem type: For each query [L, R], compute the XOR of all distinct elements in the range.

How Mo's helps: Maintain a frequency array and a running XOR. When an element's frequency goes from 0 to 1, XOR it into the result. When it drops from 1 to 0, XOR it out (XOR is its own inverse). O(1) add and remove.

Pattern 4: Powerful Array (Codeforces 86D)

Problem type: For each query, compute the sum of count(x)^2 * x over all values x in the range.

How Mo's helps: When adding element x with current count c, the contribution changes from c^2 x to (c+1)^2 x. The delta is (2c + 1) x. When removing, the delta is -(2c - 1) x. Both are O(1) updates to a running sum.

Interview Tips

Key Takeaways

Quick Reference