Log inSign up
hardGeeksforGeeksNot Started

Mo's Algorithm

A curated StudyFlow practice problem with comprehensive editorial and multi-language solutions.

Advanced DSA
Solve on GeeksforGeeks
Lesson

Problem Statement

Given an array of integers nums of size n and an array of queries where each query is given as [L, R] (0-indexed), calculate the sum (or answer) for each range query efficiently using Mo's Algorithm (Square Root Decomposition for offline queries).

Mo's Algorithm allows answering all q queries in O((n + q) \sqrt{n}) time by sorting queries in a special order and maintaining the current window [curL, curR] by adding and removing elements incrementally.

Example 1 · Example 1:

Input: nums = [1, 1, 2, 1, 3, 4, 5, 2, 8], queries = [[0, 4], [1, 3], [2, 4]]
Output: [8, 4, 6]
Explanation: Sum of subarray nums[0..4] = 1+1+2+1+3 = 8. Sum of nums[1..3] = 1+2+1 = 4. Sum of nums[2..4] = 2+1+3 = 6.

Example 2 · Example 2:

Input: nums = [2, 4, 1, 5, 3], queries = [[1, 3], [0, 2]]
Output: [10, 7]
Explanation: Sum of nums[1..3] = 4+1+5 = 10. Sum of nums[0..2] = 2+4+1 = 7.

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= queries.length <= 105
  • 0 <= L <= R < nums.length
  • -104 <= nums[i] <= 104

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Master the 3 distinct approaches for Mo's Algorithm.
  • Implement fully runnable solutions in C++, Java, Python, and JavaScript.
  • Analyze algorithmic trade-offs across data structure designs.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Mo's Algorithm
  • Advanced Data Structures & Algorithmic Paradigm
  • Fast Range Queries or Amortized Dynamic Operations

Algorithmic Decision Tree:

  • BRUTE_FORCE: Feasible only when the number of queries is tiny or array sizes are very small.
  • BETTER: Use for static arrays with invertible operations like range sum or range XOR.
  • OPTIMAL: Essential for offline range queries with complex functions (e.g. distinct elements, frequency counts, mode) where prefix sums or standard segment trees cannot be easily maintained.

Connected Patterns:

Segment TreeFenwick TreeDisjoint Set UnionDesign Data Structures

1. Direct Query Processing

Intuition

For every query [L, R], run a standard loop from index L to R summing elements. While simple, processing each query takes O(n) time in the worst case, leading to O(q \cdot n) overall time complexity which times out for large query counts.

When to apply: Feasible only when the number of queries is tiny or array sizes are very small.

Algorithm

  1. Step 1: Allocate an answer list of size equal to the number of queries.
  2. Step 2: For each query [L, R], iterate i from L to R adding nums[i] to a local sum.
  3. Step 3: Store the computed sum at the query's index in the answer array.
  4. Step 4: Return the answers list after all queries are evaluated.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4std::vector<long long> solveBruteForce(const std::vector<int>& nums, const std::vector<std::pair<int, int>>& queries) {
5 std::vector<long long> results;
6 results.reserve(queries.size());
7 for (const auto& q : queries) {
8 long long sum = 0;
9 for (int i = q.first; i <= q.second; ++i) {
10 sum += nums[i];
11 }
12 results.push_back(sum);
13 }
14 return results;
15}
16
17int main() {
18 std::vector<int> nums = {1, 1, 2, 1, 3, 4, 5, 2, 8};
19 std::vector<std::pair<int, int>> queries = {{0, 4}, {1, 3}, {2, 4}};
20 auto ans = solveBruteForce(nums, queries);
21 for (size_t i = 0; i < ans.size(); ++i) {
22 std::cout << ans[i] << (i + 1 == ans.size() ? "" : " ");
23 }
24 std::cout << std::endl;
25 return 0;
26}

Time & Space Complexity

  • Time complexity: O(q * n) where q is the number of queries and n is the array length
  • Space complexity: O(1) auxiliary space (excluding result storage)

2. Prefix Sum Array

Intuition

For pure range sum queries on static arrays, a prefix sum array pref[i] = nums[0] + ... + nums[i-1] allows answering any range query [L, R] in O(1) time as pref[R + 1] - pref[L]. However, for non-invertible aggregate queries (e.g., number of distinct elements, mode, frequent items), prefix sums do not apply, motivating Mo's Algorithm.

When to apply: Use for static arrays with invertible operations like range sum or range XOR.

Algorithm

  1. Step 1: Construct a prefix sum array pref of size n + 1 where pref[0] = 0.
  2. Step 2: Populate pref[i + 1] = pref[i] + nums[i] for each index i.
  3. Step 3: For each query [L, R], evaluate query answer in O(1) as pref[R + 1] - pref[L].
  4. Step 4: Return the precomputed query answers.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4std::vector<long long> solvePrefixSum(const std::vector<int>& nums, const std::vector<std::pair<int, int>>& queries) {
5 int n = nums.size();
6 std::vector<long long> pref(n + 1, 0);
7 for (int i = 0; i < n; ++i) {
8 pref[i + 1] = pref[i] + nums[i];
9 }
10 std::vector<long long> results;
11 results.reserve(queries.size());
12 for (const auto& q : queries) {
13 results.push_back(pref[q.second + 1] - pref[q.first]);
14 }
15 return results;
16}
17
18int main() {
19 std::vector<int> nums = {1, 1, 2, 1, 3, 4, 5, 2, 8};
20 std::vector<std::pair<int, int>> queries = {{0, 4}, {1, 3}, {2, 4}};
21 auto ans = solvePrefixSum(nums, queries);
22 for (size_t i = 0; i < ans.size(); ++i) {
23 std::cout << ans[i] << (i + 1 == ans.size() ? "" : " ");
24 }
25 std::cout << std::endl;
26 return 0;
27}

Time & Space Complexity

  • Time complexity: O(n + q) total time with O(1) per query
  • Space complexity: O(n) auxiliary space for the prefix sums

3. Mo's Algorithm (Offline Sqrt Decomposition)

Intuition

Mo's Algorithm handles offline range queries where updating the state by adding or removing one element takes O(1) time: 1. Divide the array into blocks of size B = \lceil \sqrt{n} \rceil. 2. Sort queries primarily by their block index L / B, and secondarily by R. Using Hilbert curve or alternating parity sorting (sort R ascending on even blocks and descending on odd blocks) reduces pointer movement by a factor of 2. 3. Maintain two pointers curL and curR representing the current range [curL, curR] and an accumulated sum or frequency table. 4. Shift curL and curR by calling add() and remove() functions. 5. Pointer curL moves at most O(B) per query -> O(q \sqrt{n}) total. Pointer curR moves monotonically through each block -> O(n \sqrt{n}) total. Overall time: O((n + q) \sqrt{n}).

When to apply: Essential for offline range queries with complex functions (e.g. distinct elements, frequency counts, mode) where prefix sums or standard segment trees cannot be easily maintained.

Algorithm

  1. Step 1: Set block size B = ceil(sqrt(n)) and attach original query indices to each query [L, R, idx].
  2. Step 2: Sort queries by floor(L / B). If block numbers are identical, sort by R (alternating direction by block for optimization).
  3. Step 3: Initialize window pointers curL = 0, curR = -1, and current window sum = 0.
  4. Step 4: For each sorted query [L, R, idx], expand or shrink curL and curR to match [L, R] by invoking add/remove operations.
  5. Step 5: Record the current window answer into ans[idx].
  6. Step 6: Return the accumulated answers array.

Interactive trace

2 of 2 questions left today
Step 1 / 3
Trace timeline33% explored
Current operationSTEP 1 OF 3
Process Query 0 [0, 4]: Window expands from curL=0, curR=-1 to curR=4
Visual state
Values and pointers at this exact step
pointers
S
1
1
2
1
3
4
5
2
8
0
↑ curL
1
2
3
4
↑ curR
5
6
7
8
Check / comparison
curL=0, curR=4 covers range [0, 4]
Decision / next transition
Current window sum is 1 + 1 + 2 + 1 + 3 = 8. Store ans[0] = 8.
Why this step matters

Process Query 0 [0, 4]: Window expands from curL=0, curR=-1 to curR=4. Elements nums[0..4] = [1, 1, 2, 1, 3] added.

Step 1 / 3
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <cmath>
4#include <algorithm>
5
6struct Query {
7 int l, r, id;
8};
9
10std::vector<long long> mosAlgorithm(const std::vector<int>& nums, const std::vector<std::pair<int, int>>& queries) {
11 int n = nums.size();
12 int q = queries.size();
13 int blockSize = std::max(1, (int)std::sqrt(n));
14
15 std::vector<Query> qList(q);
16 for (int i = 0; i < q; ++i) {
17 qList[i] = {queries[i].first, queries[i].second, i};
18 }
19
20 std::sort(qList.begin(), qList.end(), [blockSize](const Query& a, const Query& b) {
21 int b1 = a.l / blockSize;
22 int b2 = b.l / blockSize;
23 if (b1 != b2) return b1 < b2;
24 return (b1 & 1) ? (a.r < b.r) : (a.r > b.r);
25 });
26
27 std::vector<long long> ans(q);
28 long long currentSum = 0;
29 int curL = 0, curR = -1;
30
31 auto add = [&](int idx) { currentSum += nums[idx]; };
32 auto remove = [&](int idx) { currentSum -= nums[idx]; };
33
34 for (const auto& query : qList) {
35 while (curL > query.l) add(--curL);
36 while (curR < query.r) add(++curR);
37 while (curL < query.l) remove(curL++);
38 while (curR > query.r) remove(curR--);
39 ans[query.id] = currentSum;
40 }
41
42 return ans;
43}
44
45int main() {
46 std::vector<int> nums = {1, 1, 2, 1, 3, 4, 5, 2, 8};
47 std::vector<std::pair<int, int>> queries = {{0, 4}, {1, 3}, {2, 4}};
48 auto ans = mosAlgorithm(nums, queries);
49 for (size_t i = 0; i < ans.size(); ++i) {
50 std::cout << ans[i] << (i + 1 == ans.size() ? "" : " ");
51 }
52 std::cout << std::endl;
53 return 0;
54}

Time & Space Complexity

  • Time complexity: O((n + q) * sqrt(n)) total time
  • Space complexity: O(q) auxiliary space for sorted queries and answer array

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Direct Query ProcessingO(q * n) where q is the number of queries and n is the array lengthO(1) auxiliary space (excluding result storage)Iterate across the range [L, R] for each query independently and accumulate the sum.O(q * n) where q is the number of queries and n is the array length
2.Prefix Sum ArrayO(n + q) total time with O(1) per queryO(n) auxiliary space for the prefix sumsPrecompute prefix sums in O(n) time so each range sum query resolves in O(1) time.O(n + q) total time with O(1) per query
3.Mo's Algorithm (Offline Sqrt Decomposition)OptimalO((n + q) * sqrt(n)) total timeO(q) auxiliary space for sorted queries and answer arraySort queries into blocks of size B = sqrt(N). Shift the window pointers curL and curR between adjacent queries to answer all queries in O((N + Q) sqrt(N)) time.O((n + q) * sqrt(n)) total time

Common Pitfalls & Crucial Edge Cases

Processing queries online

Mo's algorithm CANNOT be used when queries are interleaved with updates (online).

Order of pointer movements

Must expand the window (add) before shrinking (remove) to avoid invalid states where curL > curR + 1.

Forgetting to restore original query order

Answers must be written into an output array at query.originalIndex before returning.

Crucial Edge Cases to Validate:

  • Queries with L == R (single element range) — Window width is 1; add and remove operations must handle identical endpoints.
  • Q = 1 (Single query) — Mo's behaves like standard two-pointer sweep.
  • All queries share the same L or R — Pointers move minimally.
  • Large input (N = 2 * 10^5, Q = 2 * 10^5) — Optimal block size B = max(1, (int)(N / sqrt(Q))) maximizes throughput.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Prove the time complexity formally: Left pointer moves at most Q * B times. Right pointer moves at most (N / B) * N times. Setting B = N / sqrt(Q) equates both to O(N * sqrt(Q)).
  2. State the prerequisite clearly: offline queries + O(1) add/remove transitions.
  3. Mention extensions: Mo's with updates (3D Mo's in O(N^{5/3})) and Mo's on trees (using Euler tour flattening).

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.What is the core idea of Mo's Algorithm for offline range queries?

2.What condition must a problem satisfy to be solvable by Mo's Algorithm?

3.How does Hilbert curve sorting or alternating R-direction optimize Mo's Algorithm in practice?

Back to DSA Sheet