Grokking Advanced Coding Patterns for Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Introduction to MO’s Algorithm Pattern
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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 (O(N \times Q)). 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 (O((N + Q) \times \sqrt{N})), 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 (\sqrt{N}), 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?"

  1. Divide the Array into Blocks:
    • First, determine the size of each block. If (N = 8), then the block size (B) would be (\sqrt{N} = \sqrt{8} \approx 2.83). We can round this up to 3, so each block will contain 3 elements.
Image
  1. Precompute Information for Each Block:
    • Compute the sum of each block and store it in an auxiliary array:
Image
  1. 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])).
Image
  • 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

  1. Preprocessing:

    • Calculate the block size as \text{blockSize} = \lceil \sqrt{N} \rceil.
    • Initialize a block array of size \text{blockSize} to store sums.
    • Iterate through the original array, adding each element to its corresponding block in the block array.

  2. 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.

  3. Return sum:

    • Return the value of sum.

Code

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  • Preprocessing: The time complexity for the preprocessing step, where we calculate the sum of elements for each block, is (O(N)). This involves iterating through the entire array once.

  • Query: The time complexity for each query is (\sqrt{N}). This comes from:

    • Processing up to (\sqrt{N}) 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 (\sqrt{N}) 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

  1. Preprocessing:
    • Block Size Calculation: Determine the block size as \text{blockSize} = \sqrt{N}, where (N) is the length of the array.

  1. Sorting Queries:

    • Block-based Sorting: The array is divided into approximately \sqrt{N} blocks, each of size \sqrt{N}.
    • 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 \sqrt{N}-1 as one group, then from \sqrt{N} to (2\cdot\sqrt{N}-1) 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.

  2. 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.

  3. 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.

  4. 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

  1. Block Size Calculation:
    • The block size is calculated as \sqrt{8} \approx 2.83, so we round it to 3.
Image
  1. 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<sup>th</sup> block.
      • Query 1: range [0, 4] belongs 0/sqrt(8) = 0<sup>th</sup> block.
      • Query 2: range [3, 5] belongs 3/sqrt(8) = 1<sup>st</sup> block.
    • range [2, 6], and [0, 4] belongs to the 0<sup>th</sup> 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).
Image
  • 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

Image
  • 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

Image
  • 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

Python3
Python3
. . . .

Complexity Analysis

Time Complexity

  1. Sorting the Queries:

    • The queries are sorted based on their block index and right index. Sorting Q queries takes O(Q \log Q) time.
    • This sorting step is essential because Mo's algorithm benefits from processing queries in a specific order, minimizing the movement of the pointers.

  2. 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 \sqrt{N} times, where N is the length of the array. This results in a time complexity of O((N + Q) \times \sqrt{N}) for processing all queries.

    • Why (N + Q) \times \sqrt{N}?

      • The \sqrt{N} 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 O(\sqrt{N}) times, this results in O(N \times \sqrt{N}).
      • Additionally, since there are Q queries and each might involve adjusting the range (i.e., moving the pointers), the processing of queries also contributes O(Q \times \sqrt{N}) to the overall complexity.

Combining these, the overall time complexity is O(Q \log Q + (N + Q) \times \sqrt{N})) \approx ((N + Q) \times \sqrt{N})).

Space Complexity

  • Space for Results: Storing the results for each query takes (Q) space.
  • Auxiliary Space: The array and auxiliary data structures require O(N) space.

Overall Space Complexity: O(N + Q)

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.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible