Faangprep Logo
Log inStart free
Browse curriculum

Introduction to Mo's Algorithm

Mo's algorithm starts from the problem of offline range queries and the intuition behind square root decomposition.

ARRIVAL ORDER

MOVED 10

0

L

1
2
3
4
5
6
7
8
9
10

R

11

POINTER TRAVEL

10

Queries, in processing order

0–10
8–9
0–2
9–10

 

Query 1 covers [0, 10]. The pointers had to move 10 steps to get here — running total 10.

Next

Query 2 covers [8, 9]. The pointers had to move 9 steps to get here — running total 19.

Order

Intuition

We are given an array and many queries (L, R) asking for the sum (or other property) in that range.

If we answer queries as they come, our pointers might jump wildly from the beginning to the end of the array, wasting time. What if we could re-arrange the queries to "smooth out" the movement?

Concept

Sorting Queries:

  • Divide indices into buckets of size sqrt(N).
  • Sort queries by their Left Bucket Index.
  • If in the same bucket, sort by Right Index.

This simple trick ensures L moves slowly (within a bucket) and R sweeps back and forth efficiently.

How it Works

The visualizer compares Naive Order vs Mo's Order.

  1. Naive: The pointers (blue bars) jump erratically across the array. Total distance is huge.
  2. Mo's: The pointers move in a controlled snake-like pattern. Total distance is minimized.

Step-by-Step Breakdown

1. Identify the block size B = sqrt(N).
2. Assign each query a block_id = L / B.
3. Sort queries: Primary logic block_id, Secondary logic R.
4. Process sequentially.

When to Use

  • Offline Range Queries.
  • You can't use Segment Tree (e.g., computing Mode frequency).

When NOT to Use

  • Online queries (must answer immediately).
  • Updates to array values (Mo's is static usually).

How to Identify

"Range queries", "Static Array", "Offline processing allowed".

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Meeting Rooms II

Next

Mo's Algorithm

Frequently Asked Questions

What is Mo's Algorithm?

An offline query processing technique that optimizes multiple range queries (L, R) by reordering them into blocks using Square Root Decomposition.

Why Square Root Decomposition?

By dividing the array into blocks of size √N and sorting queries by Block(L) and then R, we limit the total movement of the L and R pointers to O((N+Q)√N).

Offline vs Online Queries?

Offline means you know all queries beforehand and can reorder them to be efficient. Online means you must answer each query immediately as it arrives.