MO's Algorithm

Jul 7, 2025

Updated 1 day ago

6 min read

Mo's Algorithm in C++ with Problems and Solutions

Introduction

Mo’s Algorithm is an advanced query optimization technique used in data structures and algorithms to efficiently answer multiple range queries on arrays. It is especially useful when the array is static and there are many offline queries such as:

Range sum query
Range minimum query
Distinct elements in a range
Frequency-based queries
Maximum frequency problems

Instead of solving each query independently in O(N), Mo’s Algorithm processes queries in a special order to reduce unnecessary computations. The average complexity becomes approximately:

O ((N + Q) N)

where:

N = size of array
Q = number of queries

This makes Mo’s Algorithm extremely useful for competitive programming and coding interviews.

Also explore these

What is Mo’s Algorithm?

Mo’s Algorithm works by dividing the array into blocks of size:

$N$

Queries are sorted based on:

Left block number
Right index

This minimizes movement of the current range pointers and improves efficiency.

Mo's Algorithm Comparator in C++

cpp

int BLOCK_SIZE;
bool compare(const Query &q1, const Query &q2){ 
    int block1 = q1.left / BLOCK_SIZE;
    int block2 = q2.left / BLOCK_SIZE;
    if(block1 != block2){
        return block1 < block2;
    }
    return (block1 & 1) ? (q1.right > q2.right) : (q1.right < q2.right);
}

Problem 1: Range Sum Query

Code:

cpp

#include<bits/stdc++.h>
using namespace std;

int blockSize;
struct Query {
    int left, right, index;
};

bool comparator(const Query &q1, const Query &q2) {
    int block1 = q1.left / blockSize;
    int block2 = q2.left / blockSize;
    if (block1 != block2) return block1 < block2;
    return (block1 & 1) ? (q1.right > q2.right) : (q1.right < q2.right);
}

class Solution{
public:
    vector<long long> rangeSum(vector<int> &nums, vector<Query> &queries) {
        vector<long long> result(queries.size());
        sort(queries.begin(), queries.end(), comparator);

        int currLeft = 0, currRight = -1;
        long long sum = 0;

        for (auto &q : queries) {
            // include
            while (currLeft > q.left) sum += nums[--currLeft];
            while (currRight < q.right) sum += nums[++currRight];

            // exclude
            while (currLeft < q.left) sum -= nums[currLeft++];
            while (currRight > q.right) sum -= nums[currRight--];

            result[q.index] = sum;
        }
        return result;
    }
};

int main() {
    int n, q;
    cin >> n >> q;
    blockSize = sqrt(n);
    vector<int> nums(n);
    vector<Query> queries(q);

    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }

    for (int i = 0; i < q; i++) {
        cin >> queries[i].left >> queries[i].right;
        queries[i].index = i;
    }

    Solution solution;
    vector<long long> result = solution.rangeSum(nums, queries);
    for (auto &res : result) {
        cout << res << " ";
    }
    return 0;
}

Example:

makefile

Input:
10 4
3 6 2 4 5 1 7 8 9 10
0 4
2 6
5 9
0 9

Output:
20 19 35 55

Problem 2: Range Min Query

Code:

cpp

class Solution {
public:
    vector<int> rangeMin(const vector<int> &nums, vector<Query> &queries) {
        vector<int> result(queries.size());
        sort(queries.begin(), queries.end(), comparator);

        int currLeft = 0, currRight = -1;
        multiset<int> mset;
        for (auto &q : queries) {
            // include
            while (currLeft > q.left) mset.insert(nums[--currLeft]);
            while (currRight < q.right) mset.insert(nums[++currRight]);

            // exclude
            while (currLeft < q.left) mset.erase(mset.find(nums[currLeft++]));
            while (currRight > q.right) mset.erase(mset.find(nums[currRight--]));
            
            result[q.index] =  *mset.begin();
            // result[q.index] = *prev(mset.end()); for max
        }
        return result;
    }
};

Example:

makefile

Input:
10 4
3 6 2 4 5 1 7 8 9 10
0 4
2 6
5 9
0 9

Output:
20 19 35 55

Problem 3: Count of distinct elements in a range

Code:

cpp

class Solution
{
    unordered_map<int, int> map;
    void add(int num)
    {
        map[num]++;
    }
    void remove(int num)
    {
        if (--map[num] == 0)
        {
            map.erase(num);
        }
    }

public:
    vector<int> distinctCount(vector<int> nums, vector<Query> queries)
    {
        sort(queries.begin(), queries.end(), compator);
        vector<int> result(queries.size());
        int curr_left = 0, curr_right = -1;

        for (auto &q : queries)
        {
            int l = q.left;
            int r = q.right;

            while (curr_left > l ) add(nums[--curr_left]);
            while (curr_right < r) add(nums[++curr_right]);

            while (curr_left < l) remove(nums[curr_left++]);
            while (curr_left > r) remove(nums[curr_right--]);

            result[q.index] = map.size();
        }
        return result;
    }
};

Example:

makefile

Input:
5 3
1 1 2 1 3
0 2
1 4
2 4

Output:
2 3 3

Problem 4: Frequency of a specific element in a range

Code:

cpp

class Solution{
public:
    vector<int> freqOfK(vector<int> &nums, vector<Query> &queries){
        vector<int> result(queries.size());
        sort(queries.begin(), queries.end(), comparator);

        unordered_map<int, int> freq;
        int currL = 0, currR = -1;

        for(auto &q : queries){
            while(currL > q.left) freq[nums[--currL]]++;
            while(currR < q.right) freq[nums[++currR]]++;

            while(currL < q.left) freq[nums[currL++]]--;
            while(currR > q.right) freq[nums[currR--]]--;

            result[q.index] = freq[q.k]; 
        }

        return result;
    }
};

Example:

makefile

Input:
5 3
1 2 1 3 2
0 4 1
1 3 2
2 4 3

Output:
2 1 1

Problem 5: Count of elements with frequency = K in a range

Code:

cpp

class Solution{
    unordered_map<int, int> freq;                 // frequency of each element
    unordered_map<int, int> freqCount;       // how many elements have this frequency

    void add(int num){
        int prevFreq = freq[num];
        freq[num]++;
        freqCount[prevFreq]--;
        freqCount[prevFreq + 1]++;
    }

    void remove(int num){
        int prevFreq = freq[num];
        freq[num]--;
        freqCount[prevFreq]--;
        freqCount[prevFreq - 1]++;
    }

public:
    vector<int> count_elements_with_k_freq(vector<int> &nums, vector<Query> &queries){
        vector<int> result(queries.size());
        sort(queries.begin(), queries.end(), comparator);

        int currLeft = 0, currRight = -1;
        for(auto &q : queries){
            // include
            while(currLeft > q.left) add(nums[--currLeft]);
            while(currRight < q.right) add(nums[++currRight]);

            // exclude
            while(currLeft < q.left) remove(nums[currLeft++]);
            while(currRight > q.right) remove(nums[currRight--]);

            result[q.index] = freqCount[q.k]; // count of elements with frequency k
        }
        return result;
    }
};

Example:

makefile

Input:
10 4
1 2 2 1 3 2 1 4 3 1
0 9 2
0 5 1
3 7 2
4 9 3

Output:
1 1 1 0

Problem 6: How many elements in the range have the maximum frequency?

Code:

cpp

class Solution {
    unordered_map<int, int> freq;                  // frequency of each element
    unordered_map<int, int> freqCount;       // how many elements have this frequency
    int maxFreq = 0;

    void add(int num) {
        int prevFreq = freq[num];
        freq[num]++;
        freqCount[prevFreq]--;
        freqCount[prevFreq + 1]++;
        maxFreq = max(maxFreq, prevFreq + 1);
    }

    void remove(int num) {
        int prevFreq = freq[num];
        freq[num]--;
        freqCount[prevFreq]--;
        freqCount[prevFreq - 1]++;
        if (freqCount[maxFreq] == 0) maxFreq--;
    }

public:
    vector<int> countMostFreq(vector<int> &nums, vector<Query> &queries) {
        vector<int> result(queries.size());
        sort(queries.begin(), queries.end(), comparator);

        int currL = 0, currR = -1;
        for (auto &q : queries) {
            while (currL > q.left) add(nums[--currL]);
            while (currR < q.right) add(nums[++currR]);
            while (currL < q.left) remove(nums[currL++]);
            while (currR > q.right) remove(nums[currR--]);

            result[q.index] = maxFreq; // ✅ number of elements with maxFreq
        }
        return result;
    }
};

Example:

makefile

Input:
13 5
2 4 2 3 4 1 4 2 3 4 2 1 3
0 12
1 12
8 12
0 5
2 11

Output:
4 4 2 2 3

Problem 7: Print one element with the maximum frequency in a range.

Code:

cpp

class Solution {
public:
    vector<int> rangeMin(const vector<int> &nums, vector<Query> &queries) {
        vector<int> result(queries.size());
        sort(queries.begin(), queries.end(), comparator);

        int currLeft = 0, currRight = -1;
        multiset<int> mset;
        for (auto &q : queries) {
            // include
            while (currLeft > q.left) mset.insert(nums[--currLeft]);
            while (currRight < q.right) mset.insert(nums[++currRight]);

            // exclude
            while (currLeft < q.left) mset.erase(mset.find(nums[currLeft++]));
            while (currRight > q.right) mset.erase(mset.find(nums[currRight--]));
            
            result[q.index] =  *mset.begin();
            // result[q.index] = *prev(mset.end()); for max
        }
        return result;
    }
};

Example:

makefile

Input:
10 4
3 6 2 4 5 1 7 8 9 10
0 4
2 6
5 9
0 9

Output:
20 19 35 55

Problem 8: Print all elements with frequency exactly K in a range.

Code:

cpp

class Solution {
public:
    vector<int> rangeMin(const vector<int> &nums, vector<Query> &queries) {
        vector<int> result(queries.size());
        sort(queries.begin(), queries.end(), comparator);

        int currLeft = 0, currRight = -1;
        multiset<int> mset;
        for (auto &q : queries) {
            // include
            while (currLeft > q.left) mset.insert(nums[--currLeft]);
            while (currRight < q.right) mset.insert(nums[++currRight]);

            // exclude
            while (currLeft < q.left) mset.erase(mset.find(nums[currLeft++]));
            while (currRight > q.right) mset.erase(mset.find(nums[currRight--]));
            
            result[q.index] =  *mset.begin();
            // result[q.index] = *prev(mset.end()); for max
        }
        return result;
    }
};

Example:

makefile

Input:
10 4
3 6 2 4 5 1 7 8 9 10
0 4
2 6
5 9
0 9

Output:
20 19 35 55

Problem 9: Find the number with max/min frequency in a range.

Code:

cpp

class Solution {
public:
    vector<int> rangeMin(const vector<int> &nums, vector<Query> &queries) {
        vector<int> result(queries.size());
        sort(queries.begin(), queries.end(), comparator);

        int currLeft = 0, currRight = -1;
        multiset<int> mset;
        for (auto &q : queries) {
            // include
            while (currLeft > q.left) mset.insert(nums[--currLeft]);
            while (currRight < q.right) mset.insert(nums[++currRight]);

            // exclude
            while (currLeft < q.left) mset.erase(mset.find(nums[currLeft++]));
            while (currRight > q.right) mset.erase(mset.find(nums[currRight--]));
            
            result[q.index] =  *mset.begin();
            // result[q.index] = *prev(mset.end()); for max
        }
        return result;
    }
};

Example:

makefile

Input:
10 4
3 6 2 4 5 1 7 8 9 10
0 4
2 6
5 9
0 9

Output:
20 19 35 55