Home › DSA › Advanced Patterns

Introduction to MO’s Algorithm Pattern

Mo's Algorithm is designed to efficiently handle query-based problems, particularly those involving range queries on arrays. In such problems, you are often asked to answer multiple queries about different segments of an array. For example, you might need to find the sum, minimum, maximum, or some other property of elements within a specific range of indices.

The Challenge with Query-Based Problems

Without any optimization, solving each query individually can be quite slow. Imagine having an array of size (N) and (Q) queries. A naive approach, where you process each query independently, would result in a time complexity of . This means that for each query, you might end up scanning large portions of the array, leading to slow performance, especially when both (N) and (Q) are large.

The Role of Mo's Algorithm

Mo's Algorithm comes into the picture to solve this efficiency. By cleverly reordering the queries and using a technique called Square Root Decomposition, Mo's Algorithm significantly reduces the number of operations required to answer all queries. This brings down the time complexity to approximately , making it much more feasible to handle a large number of queries on a large array.

Mo's Algorithm is particularly useful when dealing with problems where you need to answer many range queries on static arrays. It optimizes the query processing time and is especially beneficial in competitive programming, where efficiency is crucial. Mo's Algorithm is a go-to solution when you need to handle hundreds of thousands of queries on large datasets.

Understanding Square Root Decomposition

Before we learn Mo's Algorithm, it's important to understand Square Root Decomposition, a key technique that forms the foundation of Mo's Algorithm. Square Root Decomposition is a method used to break down a problem into smaller, more manageable pieces, allowing us to solve certain types of queries more efficiently.

The Idea Behind Square Root Decomposition

The main idea is to divide an array into blocks of approximately equal size. Each block has a length of , where (N) is the size of the array. By doing this, we can process queries over these blocks more quickly, avoiding the need to repeatedly scan the entire array.

Step-by-Step Explanation with Example

Let’s consider an example to see how Square Root Decomposition works.

Suppose you have an array A = [1, 3, 5, 7, 9, 11, 13, 15] and you want to efficiently answer multiple range sum queries, such as "What is the sum of elements from index 2 to 6?"

Divide the Array into Blocks:
- First, determine the size of each block. If (N = 8), then the block size (B) would be . We can round this up to 3, so each block will contain 3 elements.

Precompute Information for Each Block:
- Compute the sum of each block and store it in an auxiliary array:

Answer Queries Efficiently:
- Now, let's answer the query: "What is the sum of elements from index 2 to 6?"
- Break the query into three parts:
  1. Partial block before the first complete block: Sum the elements from index 2 to the end of the first block (i.e., sum (A[2])).
  2. Complete blocks within the query range: Sum the complete blocks that fall within the query range (i.e., sum of Block 2).
  3. Partial block after the last complete block: Sum the elements from the start of the last block to index 6 (i.e., sum (A[6])).

For our query:
- Sum (A[2]) = 5 (partial block)
- Sum of Block 2 = 27 (complete block)
- Sum (A[6]) = 13 (partial block)
Add these sums together to get the total sum: (5 + 27 + 11 = 45).

Step-by-Step Algorithm

Preprocessing:
- Calculate the block size as .
- Initialize a block array of size to store sums.
- Iterate through the original array, adding each element to its corresponding block in the block array.
Query:
- Initialize sum to 0.
- Traverse the range [left, right]:
  - Case 1: If the current index i is at the start of a block and the block lies completely within the query range, add the precomputed sum of the block to sum and skip to the next block.
  - Case 2: Otherwise, add the value of arr[i] to sum and move to the next index.
- Return the computed sum as the result of the query.
Return sum:
- Return the value of sum.

Code

java

class Solution {

  int[] arr; // original array
  int[] block; // stores the sum of each block
  int blockSize; // size of each block

  // Constructor to initialize and preprocess the array
  public Solution(int[] input) {
    this.arr = input;
    int n = arr.length;

    // Calculate the size of each block
    blockSize = (int) Math.ceil(Math.sqrt(n));
    block = new int[blockSize];

    // Precompute the sum of elements for each block
    for (int i = 0; i < n; i++) {
      block[i / blockSize] += arr[i]; // Add element to the corresponding block
    }
  }

  // Function to perform range sum query using square root decomposition
  public int query(int left, int right) {
    int sum = 0;

    // Traverse the range [left, right] efficiently
    for (int i = left; i <= right; ) {
      // Case 1: If i is at the start of a block and the entire block lies within [left, right]
      if (i % blockSize == 0 && i + blockSize - 1 <= right) {
        sum += block[i / blockSize]; // Add the precomputed block sum
        i += blockSize; // Move i to the next block
      }
      // Case 2: Else, sum the element at index i directly
      else {
        sum += arr[i];
        i++;
      }
    }

    return sum; // Return the total sum for the query range
  }

  public static void main(String[] args) {
    int[] input = { 1, 3, 5, 7, 9, 11, 13, 15 };
    Solution sqd = new Solution(input);

    // Query: Sum from index 2 to 6
    System.out.println("Sum from index 2 to 6: " + sqd.query(2, 6)); // Output: 45
  }
}

Complexity Analysis

Time Complexity

Preprocessing: The time complexity for the preprocessing step, where we calculate the sum of elements for each block, is . This involves iterating through the entire array once.
Query: The time complexity for each query is . This comes from:
- Processing up to elements in the partial blocks (at the start and end of the query range).
- Summing the precomputed block sums for the complete blocks within the query range.

Space Complexity

The space complexity is for the block array.

Mo's Algorithm

We have already covered Square Root Decomposition, which is a fundamental concept for optimizing certain types of range queries. Building on that, let's explore Mo's Algorithm, a more advanced technique that efficiently handles multiple queries on a static array. Mo's Algorithm is particularly useful when you need to process a large number of queries involving subarrays, such as finding the sum, minimum, maximum, or other properties of elements within a given range.

Step-by-Step Algorithm

Preprocessing:
- Block Size Calculation: Determine the block size as , where (N) is the length of the array.

Sorting Queries:
- Block-based Sorting: The array is divided into approximately blocks, each of size .
- Sorting by Left Endpoint: First, sort the queries based on their left endpoint (L). Queries are grouped by the block that their left endpoint falls into. For instance, sort queries with L values from 0 to as one group, then from to as another group, and so on.
- Sorting by Right Endpoint: Within each block, sort the queries by their right endpoint (R) in ascending order. This two-level sorting helps minimize the movement of the pointers when transitioning from one query to the next, making the algorithm more efficient.
Initialize Variables:
- Set currentLeft and currentRight pointers to the beginning of the array (0).
- Initialize currentSum (or the necessary accumulator) to manage the range starting from the beginning.
Process Each Query:
- For each query, adjust the currentLeft and currentRight pointers to match the query’s range [L, R]:
  - Expand Right: If currentRight is less than R, move currentRight to the right and add the element at arr[currentRight] to currentSum.
  - Shrink Right: If currentRight is greater than R, move currentRight to the left and subtract the element at arr[currentRight] from currentSum.
  - Expand Left: If currentLeft is less than L, move currentLeft to the right and subtract the element at arr[currentLeft] from currentSum.
  - Shrink Left: If currentLeft is greater than L, move currentLeft to the left and add the element at arr[currentLeft] to currentSum.
- Store Result: After adjusting the range to match the query, store the result (e.g., currentSum) for the current query.
Output Results:
- Once all queries have been processed, output the stored results for each query in the order they were originally given.

Algorithm Walkthrough

Input and Queries

Array: input = {1, 3, 5, 7, 9, 11, 13, 15}
Queries:
1. Query 0: Sum from index 2 to 6.
2. Query 1: Sum from index 0 to 4.
3. Query 2: Sum from index 3 to 5.

Initial Setup

Block Size Calculation:
- The block size is calculated as , so we round it to 3.

Sorting Queries:
- Queries are sorted first by their left index (L) in blocks, and then by their right index (R). After sorting:
  - Query 0: range [2, 6] belongs 2/sqrt(8) = 0^th block.
  - Query 1: range [0, 4] belongs 0/sqrt(8) = 0^th block.
  - Query 2: range [3, 5] belongs 3/sqrt(8) = 1^st block.
- range [2, 6], and [0, 4] belongs to the 0^th block. So, sort them by r value. Sorted order of them will be [[0, 4], [2, 6]].
- Sorted order: Queries: [[0, 4], [2, 6], [3, 5]].

Processing Queries

Let’s process the queries in the sorted order.

Processing Query 1: Sum from index 0 to 4

Initial Pointers: currentLeft = 0, currentRight = 0, currentSum = 1 (since arr[0] = 1).

Expand Right:
- Move currentRight from 0 to 4, updating currentSum:
  - Add arr[1] = 3 → currentSum = 4
  - Add arr[2] = 5 → currentSum = 9
  - Add arr[3] = 7 → currentSum = 16
  - Add arr[4] = 9 → currentSum = 25
Store Result:
- Result for Query 1 is 25.

Processing Query 0: Sum from index 2 to 6

Adjust Left:
- Move currentLeft from 0 to 2, updating currentSum:
  - Subtract arr[0] = 1 → currentSum = 24
  - Subtract arr[1] = 3 → currentSum = 21
Expand Right:
- Move currentRight from 4 to 6, updating currentSum:
  - Add arr[5] = 11 → currentSum = 32
  - Add arr[6] = 13 → currentSum = 45
Store Result:
- Result for Query 0 is 45.

Processing Query 2: Sum from index 3 to 5

Adjust Left:
- Move currentLeft from 2 to 3, updating currentSum:
  - Subtract arr[2] = 5 → currentSum = 40
Shrink Right:
- Move currentRight from 6 to 5, updating currentSum:
  - Subtract arr[6] = 13 → currentSum = 27
Store Result:
- Result for Query 2 is 27.

Final Results

Query 0: 45 (Sum from index 2 to 6)
Query 1: 25 (Sum from index 0 to 4)
Query 2: 27 (Sum from index 3 to 5)

The final results in order of the original queries are: 45, 25, 27.

Code

java

import java.util.Arrays;
import java.util.Comparator;

// Structure to represent a query
class Query {

  int left, right, index;

  Query(int left, int right, int index) {
    this.left = left;
    this.right = right;
    this.index = index;
  }
}

class Solution {

  // Function to process all queries using Mo's Algorithm
  public int[] processQueries(int[] arr, Query[] queries) {
    int n = arr.length;
    int q = queries.length;
    int blockSize = (int) Math.sqrt(n);

    // Result array to store the answer of each query
    int[] results = new int[q];

    // Sort queries based on the block, and then by R value within the block
    Arrays.sort(
      queries,
      new Comparator<Query>() {
        public int compare(Query q1, Query q2) {
          if (q1.left / blockSize != q2.left / blockSize) return (
            q1.left / blockSize - q2.left / blockSize
          );
          return q1.right - q2.right;
        }
      }
    );

    int currentLeft = 0,
      currentRight = 0;
    int currentSum = 0;

    // Initialize current range as [0, 0]
    currentSum = arr[0]; // Start with the first element

    // Process each query
    for (Query query : queries) {
      int left = query.left;
      int right = query.right;

      // Expand the range to the right
      while (currentRight < right) {
        currentRight++;
        currentSum += arr[currentRight];
      }

      // Shrink the range from the right
      while (currentRight > right) {
        currentSum -= arr[currentRight];
        currentRight--;
      }

      // Expand the range to the left
      while (currentLeft < left) {
        currentSum -= arr[currentLeft];
        currentLeft++;
      }

      // Shrink the range from the left
      while (currentLeft > left) {
        currentLeft--;
        currentSum += arr[currentLeft];
      }

      // Store the result of this query
      results[query.index] = currentSum;
    }

    return results;
  }

  public static void main(String[] args) {
    int[] input = { 1, 3, 5, 7, 9, 11, 13, 15 };

    // Array of queries, each query asks for the sum of a subarray
    Query[] queries = {
      new Query(2, 6, 0), // Sum from index 2 to 6
      new Query(0, 4, 1), // Sum from index 0 to 4
      new Query(3, 5, 2), // Sum from index 3 to 5
    };

    Solution sol = new Solution();
    int[] results = sol.processQueries(input, queries);

    // Print the results of each query
    for (int i = 0; i < results.length; i++) {
      System.out.println("Sum of Query " + i + " : " + results[i]);
    }
  }
}

Complexity Analysis

Time Complexity

Sorting the Queries:
- The queries are sorted based on their block index and right index. Sorting Q queries takes time.
- This sorting step is essential because Mo's algorithm benefits from processing queries in a specific order, minimizing the movement of the pointers.
Processing Each Query:
- Mo's algorithm processes each query by adjusting the current range of elements using two pointers (currentLeft and currentRight).
- On average, each element is added or removed from the current range about times, where N is the length of the array. This results in a time complexity of for processing all queries.
- Why ?
  - The term comes from the fact that each query typically involves moving the left and right pointers a few times. Since there are N elements in total, and each can be added or removed times, this results in .
  - Additionally, since there are Q queries and each might involve adjusting the range (i.e., moving the pointers), the processing of queries also contributes to the overall complexity.

Combining these, the overall time complexity is .

Space Complexity

Space for Results: Storing the results for each query takes space.
Auxiliary Space: The array and auxiliary data structures require space.

Overall Space Complexity:

When is Mo's Algorithm Applicable?

Mo's Algorithm is applicable in scenarios where:

You have multiple queries that need to be answered on a static array.
Each query involves a range of elements, such as a subarray.
The brute-force approach (processing each query independently) is too slow due to the large size of the array and the number of queries.
The array is static, meaning that there are no updates between queries.

Examples of problems where Mo's Algorithm is applicable include:

Range sum queries.
Finding the frequency of an element in a subarray.
Counting distinct elements within a range.

🤖 Don't fully get this? Learn it with Claude

Stuck on Introduction to MO’s Algorithm Pattern? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Introduction to MO’s Algorithm Pattern** (DSA) and want to truly understand it. Explain Introduction to MO’s Algorithm Pattern from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Introduction to MO’s Algorithm Pattern** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Introduction to MO’s Algorithm Pattern** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Introduction to MO’s Algorithm Pattern** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Introduction to Meet in the Middle Introduction to Serialize and Dese →