MO's Algorithm

Abhijeet Singh Rajput

@abhijeetsingh

Created

Jul 7, 2025

Last Modified

9 months ago

Mo's Algorithm

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