Given a matrix mat[][] of size N*M, the task is to find the minimum value in a submatrix of the array, defined by the top-left and bottom-right indices of the submatrix for the given queries.
Example:
Input: N = 4, M = 4, mat[][] = { { 5, 8, 2, 4 }, { 7, 2, 9, 1 }, { 1, 4, 7, 3 }, { 3, 5, 6, 8 } }
queries[][] = {{0, 0, 3, 3}, {1, 1, 2, 2}}
Output:
1
2
Explanation:
For first query, top-left corner at (0, 0) and bottom-right corner at (2, 2), which is the entire input matrix. The minimum value in this submatrix is 1.
For second call, the top-left corner at (1, 1) and bottom-right corner at (2, 2). The minimum value in this submatrix is 2.
One solution to this problem is to use a data structure called a sparse table. A sparse table is a data structure that allows you to perform RMQ in O(1) time after O(nmlogn*logm) preprocessing time.
To build a sparse table for a 2D array, you can follow these steps:
- Preprocess the array to calculate the minimum value for each cell and for each submatrix with a size of 2k * 2l, where k and l are non-negative integers.
- Store the minimum values in a 2D array called the sparse table. The size of the sparse table should be n*m*log(n)*log(m).
- Firstly find the largest value of k such that 2k is less than or equal to the width of the submatrix.
- Then, find the largest value of l such that 2l is less than or equal to the height of the submatrix.
- Using these values, you can look up the minimum value in the sparse table and return it as the result.
Here is a brief example of how to implement a 2D range minimum query using a sparse table in Python:
C++
// C++ code to implement the sparse table#include <bits/stdc++.h>using namespace std;const int N = 100;int matrix[N][N];int table[N][N][(int)(log2(N) + 1)][(int)(log2(N) + 1)];// Function to build the sparse tablevoid build_sparse_table(int n, int m){ // Copy the values of the original matrix // to the first element of the table for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[i][j][0][0] = matrix[i][j]; } } // Building the table for (int k = 1; k <= (int)(log2(n)); k++) { for (int i = 0; i + (1 << k) - 1 < n; i++) { for (int j = 0; j + (1 << k) - 1 < m; j++) { table[i][j][k][0] = min( table[i][j][k - 1][0], table[i + (1 << (k - 1))][j][k - 1][0]); } } } for (int k = 1; k <= (int)(log2(m)); k++) { for (int i = 0; i < n; i++) { for (int j = 0; j + (1 << k) - 1 < m; j++) { table[i][j][0][k] = min( table[i][j][0][k - 1], table[i][j + (1 << (k - 1))][0][k - 1]); } } } for (int k = 1; k <= (int)(log2(n)); k++) { for (int l = 1; l <= (int)(log2(m)); l++) { for (int i = 0; i + (1 << k) - 1 < n; i++) { for (int j = 0; j + (1 << l) - 1 < m; j++) { table[i][j][k][l] = min( min(table[i][j][k - 1][l - 1], table[i + (1 << (k - 1))][j] [k - 1][l - 1]), min(table[i][j + (1 << (l - 1))] [k - 1][l - 1], table[i + (1 << (k - 1))] [j + (1 << (l - 1))][k - 1] [l - 1])); } } } }}// Function to find the maximum value in a submatrixint rmq(int x1, int y1, int x2, int y2){ // log2(x2-x1+1) gives the power of 2 // which is just less than or equal to x2-x1+1 int k = log2(x2 - x1 + 1); int l = log2(y2 - y1 + 1); // Lookup the value from the table which is // the maximum among the 4 submatrices return max(max(table[x1][y1][k][l], table[x2 - (1 << k) + 1][y1][k][l]), max(table[x1][y2 - (1 << l) + 1][k][l], table[x2 - (1 << k) + 1] [y2 - (1 << l) + 1][k][l]));}// Function to solve the queriesvoid solve(int n, int m, vector<vector<int> >& matrix1, int q, vector<int> queries[]){ int i = 0; while (i < n) { int j = 0; while (j < m) { matrix[i][j] = matrix1[i][j]; j++; } i++; } build_sparse_table(n, m); i = 0; while (i < q) { int x1, y1, x2, y2; x1 = queries[i][0]; y1 = queries[i][1]; x2 = queries[i][2]; y2 = queries[i][3]; cout << rmq(x1, y1, x2, y2) << endl; i++; }}// Driver codeint main(){ int N = 4, M = 4; vector<vector<int> > matrix1 = { { 5, 8, 2, 4 }, { 7, 2, 9, 1 }, { 1, 4, 7, 3 }, { 3, 5, 6, 8 } }; int Q = 2; vector<int> queries[] = { { 0, 0, 3, 3 }, { 1, 1, 2, 2 } }; // Function call solve(N, M, matrix1, Q, queries); return 0;} |
Java
// Java code to implement the sparse tableimport java.util.Scanner;class GFG { static final int N = 100; static int[][] matrix = new int[N][N]; static int[][][][] table = new int[N][N] [(int)(Math.log(N) / Math.log(2) + 1)] [(int)(Math.log(N) / Math.log(2) + 1)]; // Function to build the sparse table static void buildSparseTable(int n, int m) { // Copy the values of the original matrix // to the first element of the table for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[i][j][0][0] = matrix[i][j]; } } // Building the table for (int k = 1; k <= (int)(Math.log(n) / Math.log(2)); k++) { for (int i = 0; i + (1 << k) - 1 < n; i++) { for (int j = 0; j + (1 << k) - 1 < m; j++) { table[i][j][k][0] = Math.min(table[i][j][k - 1][0], table[i + (1 << (k - 1))] [j][k - 1][0]); } } } for (int k = 1; k <= (int)(Math.log(m) / Math.log(2)); k++) { for (int i = 0; i < n; i++) { for (int j = 0; j + (1 << k) - 1 < m; j++) { table[i][j][0][k] = Math.min( table[i][j][0][k - 1], table[i][j + (1 << (k - 1))][0] [k - 1]); } } } for (int k = 1; k <= (int)(Math.log(n) / Math.log(2)); k++) { for (int l = 1; l <= (int)(Math.log(m) / Math.log(2)); l++) { for (int i = 0; i + (1 << k) - 1 < n; i++) { for (int j = 0; j + (1 << l) - 1 < m; j++) { table[i][j][k][l] = Math.min( Math.min( table[i][j][k - 1][l - 1], table[i + (1 << (k - 1))][j] [k - 1][l - 1]), Math.min( table[i][j + (1 << (l - 1))] [k - 1][l - 1], table[i + (1 << (k - 1))] [j + (1 << (l - 1))] [k - 1][l - 1])); } } } } } // Function to find the maximum value in a submatrix static int rmq(int x1, int y1, int x2, int y2) { // log2(x2-x1+1) gives the power of 2 // which is just less than or equal to x2-x1+1 int k = (int)(Math.log(x2 - x1 + 1) / Math.log(2)); int l = (int)(Math.log(y2 - y1 + 1) / Math.log(2)); // Lookup the value from the table which is // the maximum among the 4 submatrices return Math.max( Math.max(table[x1][y1][k][l], table[x2 - (1 << k) + 1][y1][k][l]), Math.max(table[x1][y2 - (1 << l) + 1][k][l], table[x2 - (1 << k) + 1] [y2 - (1 << l) + 1][k][l])); } // Function to solve the queries static void solve(int n, int m, int[][] matrix1, int q, int[][] queries) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { matrix[i][j] = matrix1[i][j]; } } buildSparseTable(n, m); for (int i = 0; i < q; i++) { int x1, y1, x2, y2; x1 = queries[i][0]; y1 = queries[i][1]; x2 = queries[i][2]; y2 = queries[i][3]; System.out.println(rmq(x1, y1, x2, y2)); } } // Driver code public static void main(String[] args) { int N = 4, M = 4; int[][] matrix1 = { { 5, 8, 2, 4 }, { 7, 2, 9, 1 }, { 1, 4, 7, 3 }, { 3, 5, 6, 8 } }; int Q = 2; int[][] queries = { { 0, 0, 3, 3 }, { 1, 1, 2, 2 } }; // Function call solve(N, M, matrix1, Q, queries); }}// This Code is Contributed by Prasad Kandekar(prasad264) |
Python3
# Python code to implement the sparse tableimport mathN = 100matrix = [[0 for j in range(N)] for i in range(N)]table = [[[[0 for l in range(int(math.log2(N)) + 1)] for k in range( int(math.log2(N)) + 1)] for j in range(N)] for i in range(N)]# Function to build the sparse tabledef build_sparse_table(n, m): # Copy the values of the original matrix # to the first element of the table for i in range(n): for j in range(m): table[i][j][0][0] = matrix[i][j] # Building the table for k in range(1, int(math.log2(n)) + 1): for i in range(n - (1 << k) + 1): for j in range(m - (1 << k) + 1): table[i][j][k][0] = min( table[i][j][k-1][0], table[i+(1 << (k-1))][j][k-1][0]) for k in range(1, int(math.log2(m)) + 1): for i in range(n): for j in range(m - (1 << k) + 1): table[i][j][0][k] = min( table[i][j][0][k-1], table[i][j+(1 << (k-1))][0][k-1]) for k in range(1, int(math.log2(n)) + 1): for l in range(1, int(math.log2(m)) + 1): for i in range(n - (1 << k) + 1): for j in range(m - (1 << l) + 1): table[i][j][k][l] = min( table[i][j][k-1][l-1], table[i+(1 << (k-1))][j][k-1][l-1], table[i][j+(1 << (l-1))][k-1][l-1], table[i+(1 << (k-1))][j+(1 << (l-1))][k-1][l-1] )# Function to find the maximum value in a submatrixdef rmq(x1, y1, x2, y2): # log2(x2-x1+1) gives the power of 2 which is just less than or equal to x2-x1+1 k = int(math.log2(x2-x1+1)) l = int(math.log2(y2-y1+1)) # Lookup the value from the table which is the maximum among the 4 submatrices return max( table[x1][y1][k][l], table[x2-(1 << k)+1][y1][k][l], table[x1][y2-(1 << l)+1][k][l], table[x2-(1 << k)+1][y2-(1 << l)+1][k][l] )# Function to solve the queriesdef solve(n, m, matrix1, q, queries): for i in range(n): for j in range(m): matrix[i][j] = matrix1[i][j] build_sparse_table(n, m) for i in range(q): x1, y1, x2, y2 = queries[i] print(rmq(x1, y1, x2, y2))N = 4M = 4matrix1 = [[5, 8, 2, 4], [7, 2, 9, 1], [1, 4, 7, 3], [3, 5, 6, 8]]Q = 2queries = [[0, 0, 3, 3], [1, 1, 2, 2]]# Function callsolve(N, M, matrix1, Q, queries)# This Code is Contributed by sankar. |
C#
// C# code to implement the sparse tableusing System;public class GFG { const int N = 100; static int[, ] matrix = new int[N, N]; static int[, , , ] table = new int[N, N, (int)(Math.Log(N) / Math.Log(2) + 1), (int)(Math.Log(N) / Math.Log(2) + 1)]; // Function to build the sparse table static void buildSparseTable(int n, int m) { // Copy the values of the original matrix // to the first element of the table for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { table[i, j, 0, 0] = matrix[i, j]; } } // Building the table for (int k = 1; k <= (int)(Math.Log(n) / Math.Log(2)); k++) { for (int i = 0; i + (1 << k) - 1 < n; i++) { for (int j = 0; j + (1 << k) - 1 < m; j++) { table[i, j, k, 0] = Math.Min(table[i, j, k - 1, 0], table[i + (1 << (k - 1)), j, k - 1, 0]); } } } for (int k = 1; k <= (int)(Math.Log(m) / Math.Log(2)); k++) { for (int i = 0; i < n; i++) { for (int j = 0; j + (1 << k) - 1 < m; j++) { table[i, j, 0, k] = Math.Min( table[i, j, 0, k - 1], table[i, j + (1 << (k - 1)), 0, k - 1]); } } } for (int k = 1; k <= (int)(Math.Log(n) / Math.Log(2)); k++) { for (int l = 1; l <= (int)(Math.Log(m) / Math.Log(2)); l++) { for (int i = 0; i + (1 << k) - 1 < n; i++) { for (int j = 0; j + (1 << l) - 1 < m; j++) { table[i, j, k, l] = Math.Min( Math.Min( table[i, j, k - 1, l - 1], table[i + (1 << (k - 1)), j, k - 1, l - 1]), Math.Min( table[i, j + (1 << (l - 1)), k - 1, l - 1], table[i + (1 << (k - 1)), j + (1 << (l - 1)), k - 1, l - 1])); } } } } } // Function to find the maximum value in a submatrix static int rmq(int x1, int y1, int x2, int y2) { // log2(x2-x1+1) gives the power of 2 // which is just less than or equal to x2-x1+1 int k = (int)(Math.Log(x2 - x1 + 1) / Math.Log(2)); int l = (int)(Math.Log(y2 - y1 + 1) / Math.Log(2)); // Lookup the value from the table which is // the maximum among the 4 submatrices return Math.Max( Math.Max(table[x1, y1, k, l], table[x2 - (1 << k) + 1, y1, k, l]), Math.Max(table[x1, y2 - (1 << l) + 1, k, l], table[x2 - (1 << k) + 1, y2 - (1 << l) + 1, k, l])); } // Function to solve the queries static void solve(int n, int m, int[, ] matrix1, int q, int[, ] queries) { for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { matrix[i, j] = matrix1[i, j]; } } buildSparseTable(n, m); for (int i = 0; i < q; i++) { int x1, y1, x2, y2; x1 = queries[i, 0]; y1 = queries[i, 1]; x2 = queries[i, 2]; y2 = queries[i, 3]; Console.WriteLine(rmq(x1, y1, x2, y2)); } } static public void Main() { // Code int N = 4, M = 4; int[, ] matrix1 = { { 5, 8, 2, 4 }, { 7, 2, 9, 1 }, { 1, 4, 7, 3 }, { 3, 5, 6, 8 } }; int Q = 2; int[, ] queries = { { 0, 0, 3, 3 }, { 1, 1, 2, 2 } }; // Function call solve(N, M, matrix1, Q, queries); }}// This code is contributed by karthik. |
Javascript
// Javascript code to implement the sparse tableconst N = 100;const matrix = new Array(N).fill(null).map(() => new Array(N).fill(0));const table = new Array(N).fill(null).map(() => new Array(N).fill(null).map(() => new Array(Math.ceil(Math.log2(N) + 1)).fill(null).map(() => new Array(Math.ceil(Math.log2(N) + 1)).fill(0))));// Function to build the sparse tablefunction build_sparse_table(n, m) { // Copy the values of the original matrix // to the first element of the table for (let i = 0; i < n; i++) {for (let j = 0; j < m; j++) { table[i][j][0][0] = matrix[i][j];} } // Building the table for (let k = 1; k <= Math.log2(n); k++) {for (let i = 0; i + (1 << k) - 1 < n; i++) { for (let j = 0; j + (1 << k) - 1 < m; j++) { table[i][j][k][0] = Math.min( table[i][j][k - 1][0], table[i + (1 << (k - 1))][j][k - 1][0] ); }} } for (let k = 1; k <= Math.log2(m); k++) {for (let i = 0; i < n; i++) { for (let j = 0; j + (1 << k) - 1 < m; j++) { table[i][j][0][k] = Math.min( table[i][j][0][k - 1], table[i][j + (1 << (k - 1))][0][k - 1] ); }} } for (let k = 1; k <= Math.log2(n); k++) {for (let l = 1; l <= Math.log2(m); l++) { for (let i = 0; i + (1 << k) - 1 < n; i++) { for (let j = 0; j + (1 << l) - 1 < m; j++) { table[i][j][k][l] = Math.min( Math.min( table[i][j][k - 1][l - 1], table[i + (1 << (k - 1))][j][k - 1][l - 1] ), Math.min( table[i][j + (1 << (l - 1))][k - 1][l - 1], table[i + (1 << (k - 1))][j + (1 << (l - 1))][k - 1][l - 1] ) ); } }} }}// Function to find the maximum value in a submatrixfunction rmq(x1, y1, x2, y2){// log2(x2-x1+1) gives the power of 2// which is just less than or equal to x2-x1+1let k = Math.ceil(Math.log2(x2 - x1 + 1));let l = Math.ceil(Math.log2(y2 - y1 + 1)); // Lookup the value from the table which is// the maximum among the 4 submatricesreturn Math.max(Math.max(table[x1][y1][k][l], table[x2 - (1 << k) + 1][y1][k][l]), Math.max(table[x1][y2 - (1 << l) + 1][k][l], table[x2 - (1 << k) + 1] [y2 - (1 << l) + 1][k][l]));}// Function to solve the queriesfunction solve(n, m, matrix1,q, queries){let i = 0;while (i < n) { let j = 0; while (j < m) { matrix[i][j] = matrix1[i][j]; j++; } i++;}build_sparse_table(n, m);i = 0;while (i < q) { let x1, y1, x2, y2; x1 = queries[i][0]; y1 = queries[i][1]; x2 = queries[i][2]; y2 = queries[i][3]; console.log(rmq(x1, y1, x2, y2)+"<br>") i++;}}// Driver codeconst n= 4, m = 4;const matrix1 = [[5, 8, 2, 4], [7, 2, 9, 1], [1, 4, 7, 3], [3, 5, 6, 8]];const Q = 2;const queries = [[0, 0, 3, 3], [1, 1, 2, 2]];// Function callsolve(n, m, matrix1, Q, queries);// This code is contributed by Vaibhav. |
Output
1 2
Time complexity:
- O(N * M * log(N) * log(M)) (To build sparse table)
- O(1) (For Each Query)
Auxiliary Space: O(N * M * log(N) * log(M))
Related Articles:
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
