Smallest element from all square submatrices of size K from a given Matrix
Given a matrix arr[][] and an integer K, the task is to find the smallest element from all possible square submatrices of size K from the given matrix.
Examples:
Input: K = 2, arr[][] ={ {1, 2, 3}, {4, 5, 6}, {7, 8, 9} }
Output:
1 2
4 5
Explanation:
Smallest elements from all possible square submatrices of size 2 are as follows:
{ {1, 2}, {4, 5} } -> 1
{ {2, 3}, {5, 6} } -> 2
{ {4, 5}, {7, 8} } -> 4
{ {5, 6}, {8, 9} } -> 5Input: K = 3,
arr[][] = { {-1, 5, 4, 1, -3},
{4, 3, 1, 1, 6},
{2, -2, 5, 3, 1},
{8, 5, 1, 9, -4},
{12, 3, 5, 8, 1} }
Output:
-2 -2 -3
-2 -2 -4
-2 -2 -4
Naive Approach: The simplest approach to solve the problem is to generate all possible square submatrices of size K from the given matrix and print the smallest element from each such submatrices.
C++
#include <iostream> #include <vector> #include <climits> // for INT_MAX using namespace std; // Function to return the smallest elements of all KxK submatrices of a given NxM matrix void print_smallest_elements( const vector<vector< int >> &arr, int K) { // Get the number of rows and columns in the matrix int rows = arr.size(); int cols = arr[0].size(); // Loop through the matrix, creating submatrices of size KxK for ( int row = 0; row <= rows - K; row++) { for ( int col = 0; col <= cols - K; col++) { // Create a submatrix by extracting elements from the original matrix vector<vector< int >> subarr; for ( int i = row; i < row + K; i++) { vector< int > subcol; for ( int j = col; j < col + K; j++) { subcol.push_back(arr[i][j]); } subarr.push_back(subcol); } // Find the minimum value in the submatrix int minimum = INT_MAX; for ( const auto &x : subarr) { for ( const auto &y : x) { minimum = min(minimum, y); } } // Print the minimum value of the submatrix cout << minimum << " " ; } cout << endl; } } int main() { // Given matrix vector<vector< int >> arr = {{-1, 5, 4, 1, -3}, {4, 3, 1, 1, 6}, {2, -2, 5, 3, 1}, {8, 5, 1, 9, -4}, {12, 3, 5, 8, 1}}; int K = 3; // Call the function to print the smallest elements of all KxK submatrices print_smallest_elements(arr, K); return 0; } |
Java
import java.util.ArrayList; public class Main { // Function to return the smallest // elements of all KxK submatrices of a // given NxM matrix static void printSmallestElements( ArrayList<ArrayList<Integer> > arr, int K) { // Get the number of rows and columns in the matrix int rows = arr.size(); int cols = arr.get( 0 ).size(); // Loop through the matrix, creating submatrices of // size KxK for ( int row = 0 ; row <= rows - K; row++) { for ( int col = 0 ; col <= cols - K; col++) { // Create a submatrix by extracting elements // from the original matrix ArrayList<ArrayList<Integer> > subarr = new ArrayList<ArrayList<Integer> >(); for ( int i = row; i < row + K; i++) { ArrayList<Integer> subcol = new ArrayList<Integer>(); for ( int j = col; j < col + K; j++) { subcol.add(arr.get(i).get(j)); } subarr.add(subcol); } // Find the minimum value in the submatrix int minimum = Integer.MAX_VALUE; for (ArrayList<Integer> x : subarr) { for ( int y : x) { minimum = Math.min(minimum, y); } } // Print the minimum value of the submatrix System.out.print(minimum + " " ); } System.out.println(); } } public static void main(String[] args) { // Given matrix ArrayList<ArrayList<Integer> > arr = new ArrayList<ArrayList<Integer> >(); arr.add( new ArrayList<Integer>() { { add(- 1 ); add( 5 ); add( 4 ); add( 1 ); add(- 3 ); } }); arr.add( new ArrayList<Integer>() { { add( 4 ); add( 3 ); add( 1 ); add( 1 ); add( 6 ); } }); arr.add( new ArrayList<Integer>() { { add( 2 ); add(- 2 ); add( 5 ); add( 3 ); add( 1 ); } }); arr.add( new ArrayList<Integer>() { { add( 8 ); add( 5 ); add( 1 ); add( 9 ); add(- 4 ); } }); arr.add( new ArrayList<Integer>() { { add( 12 ); add( 3 ); add( 5 ); add( 8 ); add( 1 ); } }); int K = 3 ; // Call the function to print the smallest elements // of all KxK submatrices printSmallestElements(arr, K); } } |
Python3
# Python3 program for the above approach # Function to returns a smallest # elements of all KxK submatrices # of a given NxM matrix def print_smallest_elements(arr, K): rows = len (arr) cols = len (arr[ 0 ]) for row in range (rows - K + 1 ): for col in range (cols - K + 1 ): subarr = [row[col:col + K] for row in arr[row:row + K]] print ( min ([ min (x) for x in subarr]), end = " " ) print () # Driver Code # Given matrix arr = [[ - 1 , 5 , 4 , 1 , - 3 ], [ 4 , 3 , 1 , 1 , 6 ], [ 2 , - 2 , 5 , 3 , 1 ], [ 8 , 5 , 1 , 9 , - 4 ], [ 12 , 3 , 5 , 8 , 1 ]] # Given K K = 3 # Function call print_smallest_elements(arr, K) # This code is contributed by Aman Kumar |
C#
using System; using System.Collections.Generic; public class Mainn { // Function to return the smallest elements of all KxK submatrices of a // given NxM matrix static void PrintSmallestElements(List<List< int >> arr, int K) { // Get the number of rows and columns in the matrix int rows = arr.Count; int cols = arr[0].Count; // Loop through the matrix, creating submatrices of size KxK for ( int row = 0; row <= rows - K; row++) { for ( int col = 0; col <= cols - K; col++) { // Create a submatrix by extracting elements from the original matrix List<List< int >> subarr = new List<List< int >>(); for ( int i = row; i < row + K; i++) { List< int > subcol = new List< int >(); for ( int j = col; j < col + K; j++) { subcol.Add(arr[i][j]); } subarr.Add(subcol); } // Find the minimum value in the submatrix int minimum = int .MaxValue; foreach (List< int > x in subarr) { foreach ( int y in x) { minimum = Math.Min(minimum, y); } } // Print the minimum value of the submatrix Console.Write(minimum + " " ); } Console.WriteLine(); } } public static void Main() { // Given matrix List<List< int >> arr = new List<List< int >>() { new List< int >() {-1, 5, 4, 1, -3}, new List< int >() {4, 3, 1, 1, 6}, new List< int >() {2, -2, 5, 3, 1}, new List< int >() {8, 5, 1, 9, -4}, new List< int >() {12, 3, 5, 8, 1} }; int K = 3; // Call the function to print the smallest elements of all KxK submatrices PrintSmallestElements(arr, K); } } |
Javascript
// Function to return the smallest elements of all KxK submatrices of a given NxM matrix function print_smallest_elements(arr, K) { // Get the number of rows and columns in the matrix let rows = arr.length; let cols = arr[0].length; // Loop through the matrix, creating submatrices of size KxK for (let row = 0; row <= rows - K; row++) { for (let col = 0; col <= cols - K; col++) { // Create a submatrix by extracting elements from the original matrix let subarr = []; for (let i = row; i < row + K; i++) { let subcol = []; for (let j = col; j < col + K; j++) { subcol.push(arr[i][j]); } subarr.push(subcol); } // Find the minimum value in the submatrix let minimum = Number.MAX_SAFE_INTEGER; subarr.forEach(x => { x.forEach(y => { minimum = Math.min(minimum, y); }) }) // Print the minimum value of the submatrix process.stdout.write(minimum + " " ); } console.log(); } } // Given matrix let arr = [[-1, 5, 4, 1, -3], [4, 3, 1, 1, 6], [2, -2, 5, 3, 1], [8, 5, 1, 9, -4], [12, 3, 5, 8, 1]]; let K = 3; // Call the function to print the smallest elements of all KxK submatrices print_smallest_elements(arr, K); |
-2 -2 -3 -2 -2 -4 -2 -2 -4
Time Complexity: O(N * M * K2)
Auxiliary Space: O(K*K)
Efficient Approach: Follow the steps below to optimize the above approach:
- Traverse over each row of the matrix and for every arr[i][j], update in-place the smallest element present between indices arr[i][j] to arr[i][j + K – 1] (0 <= j < M – K + 1).
- Similarly, traverse over each column of the matrix and for every arr[i][j], update in-place the smallest element present between indices arr[i][j] to arr[i+K-1][j] (0 <= i < N – K + 1).
- After performing the above operations, the top-left submatrix of size (N – K + 1)*(M – K + 1) of the matrix arr[][] consists of all the smallest elements of all the K x K sub-matrices of the given matrix.
- Therefore, print the submatrix of size (N – K + 1)*(M – K + 1) as the required output.
Below is the implementation of the above approach:
C++
// C++ Program for // the above approach #include <bits/stdc++.h> using namespace std; // Function to returns a smallest // elements of all KxK submatrices // of a given NxM matrix vector<vector< int > > matrixMinimum( vector<vector< int > > nums, int K) { // Stores the dimensions // of the given matrix int N = nums.size(); int M = nums[0].size(); // Stores the required // smallest elements vector<vector< int > > res(N - K + 1, vector< int >(M - K + 1)); // Update the smallest elements row-wise for ( int i = 0; i < N; i++) { for ( int j = 0; j < M - K + 1; j++) { int mini = INT_MAX; for ( int k = j; k < j + K; k++) { mini = min(mini, nums[i][k]); } nums[i][j] = mini; } } // Update the minimum column-wise for ( int j = 0; j < M; j++) { for ( int i = 0; i < N - K + 1; i++) { int mini = INT_MAX; for ( int k = i; k < i + K; k++) { mini = min(mini, nums[k][j]); } nums[i][j] = mini; } } // Store the final submatrix with // required minimum values for ( int i = 0; i < N - K + 1; i++) for ( int j = 0; j < M - K + 1; j++) res[i][j] = nums[i][j]; // Return the resultant matrix return res; } void smallestinKsubmatrices(vector<vector< int > > arr, int K) { // Function Call vector<vector< int > > res = matrixMinimum(arr, K); // Print resultant matrix with the // minimum values of KxK sub-matrix for ( int i = 0; i < res.size(); i++) { for ( int j = 0; j < res[0].size(); j++) { cout << res[i][j] << " " ; } cout << endl; } } // Driver Code int main() { // Given matrix vector<vector< int > > arr = {{-1, 5, 4, 1, -3}, {4, 3, 1, 1, 6}, {2, -2, 5, 3, 1}, {8, 5, 1, 9, -4}, {12, 3, 5, 8, 1}}; // Given K int K = 3; smallestinKsubmatrices(arr, K); } // This code is contributed by Chitranayal |
Java
// Java Program for the above approach import java.util.*; import java.lang.*; class GFG { // Function to returns a smallest // elements of all KxK submatrices // of a given NxM matrix public static int [][] matrixMinimum( int [][] nums, int K) { // Stores the dimensions // of the given matrix int N = nums.length; int M = nums[ 0 ].length; // Stores the required // smallest elements int [][] res = new int [N - K + 1 ][M - K + 1 ]; // Update the smallest elements row-wise for ( int i = 0 ; i < N; i++) { for ( int j = 0 ; j < M - K + 1 ; j++) { int min = Integer.MAX_VALUE; for ( int k = j; k < j + K; k++) { min = Math.min(min, nums[i][k]); } nums[i][j] = min; } } // Update the minimum column-wise for ( int j = 0 ; j < M; j++) { for ( int i = 0 ; i < N - K + 1 ; i++) { int min = Integer.MAX_VALUE; for ( int k = i; k < i + K; k++) { min = Math.min(min, nums[k][j]); } nums[i][j] = min; } } // Store the final submatrix with // required minimum values for ( int i = 0 ; i < N - K + 1 ; i++) for ( int j = 0 ; j < M - K + 1 ; j++) res[i][j] = nums[i][j]; // Return the resultant matrix return res; } public static void smallestinKsubmatrices( int arr[][], int K) { // Function Call int [][] res = matrixMinimum(arr, K); // Print resultant matrix with the // minimum values of KxK sub-matrix for ( int i = 0 ; i < res.length; i++) { for ( int j = 0 ; j < res[ 0 ].length; j++) { System.out.print(res[i][j] + " " ); } System.out.println(); } } // Driver Code public static void main(String[] args) { // Given matrix int [][] arr = { { - 1 , 5 , 4 , 1 , - 3 }, { 4 , 3 , 1 , 1 , 6 }, { 2 , - 2 , 5 , 3 , 1 }, { 8 , 5 , 1 , 9 , - 4 }, { 12 , 3 , 5 , 8 , 1 } }; // Given K int K = 3 ; smallestinKsubmatrices(arr, K); } } |
Python3
# Python3 program for the above approach import sys # Function to returns a smallest # elements of all KxK submatrices # of a given NxM matrix def matrixMinimum(nums, K): # Stores the dimensions # of the given matrix N = len (nums) M = len (nums[ 0 ]) # Stores the required # smallest elements res = [[ 0 for x in range (M - K + 1 )] for y in range (N - K + 1 )] # Update the smallest elements row-wise for i in range (N): for j in range (M - K + 1 ): mn = sys.maxsize for k in range (j, j + K): mn = min (mn, nums[i][k]) nums[i][j] = mn # Update the minimum column-wise for j in range (M): for i in range (N - K + 1 ): mn = sys.maxsize for k in range (i, i + K): mn = min (mn, nums[k][j]) nums[i][j] = mn # Store the final submatrix with # required minimum values for i in range (N - K + 1 ): for j in range (M - K + 1 ): res[i][j] = nums[i][j] # Return the resultant matrix return res def smallestinKsubmatrices(arr, K): # Function call res = matrixMinimum(arr, K) # Print resultant matrix with the # minimum values of KxK sub-matrix for i in range ( len (res)): for j in range ( len (res[ 0 ])): print (res[i][j], end = " " ) print () # Driver Code # Given matrix arr = [ [ - 1 , 5 , 4 , 1 , - 3 ], [ 4 , 3 , 1 , 1 , 6 ], [ 2 , - 2 , 5 , 3 , 1 ], [ 8 , 5 , 1 , 9 , - 4 ], [ 12 , 3 , 5 , 8 , 1 ] ] # Given K K = 3 # Function call smallestinKsubmatrices(arr, K) # This code is contributed by Shivam Singh |
C#
// C# program for the above approach using System; class GFG{ // Function to returns a smallest // elements of all KxK submatrices // of a given NxM matrix public static int [,] matrixMinimum( int [,] nums, int K) { // Stores the dimensions // of the given matrix int N = nums.GetLength(0); int M = nums.GetLength(1); // Stores the required // smallest elements int [,] res = new int [N - K + 1, M - K + 1]; // Update the smallest elements row-wise for ( int i = 0; i < N; i++) { for ( int j = 0; j < M - K + 1; j++) { int min = int .MaxValue; for ( int k = j; k < j + K; k++) { min = Math.Min(min, nums[i, k]); } nums[i, j] = min; } } // Update the minimum column-wise for ( int j = 0; j < M; j++) { for ( int i = 0; i < N - K + 1; i++) { int min = int .MaxValue; for ( int k = i; k < i + K; k++) { min = Math.Min(min, nums[k, j]); } nums[i, j] = min; } } // Store the readonly submatrix with // required minimum values for ( int i = 0; i < N - K + 1; i++) for ( int j = 0; j < M - K + 1; j++) res[i, j] = nums[i, j]; // Return the resultant matrix return res; } public static void smallestinKsubmatrices( int [,]arr, int K) { // Function call int [,] res = matrixMinimum(arr, K); // Print resultant matrix with the // minimum values of KxK sub-matrix for ( int i = 0; i < res.GetLength(0); i++) { for ( int j = 0; j < res.GetLength(1); j++) { Console.Write(res[i, j] + " " ); } Console.WriteLine(); } } // Driver Code public static void Main(String[] args) { // Given matrix int [,] arr = { { -1, 5, 4, 1, -3 }, { 4, 3, 1, 1, 6 }, { 2, -2, 5, 3, 1 }, { 8, 5, 1, 9, -4 }, { 12, 3, 5, 8, 1 } }; // Given K int K = 3; smallestinKsubmatrices(arr, K); } } // This code is contributed by Amit Katiyar |
Javascript
<script> // javascript program for the // above approach // Function to returns a smallest // elements of all KxK submatrices // of a given NxM matrix function matrixMinimum( nums, K) { // Stores the dimensions // of the given matrix let N = nums.length; let M = nums[0].length; // Stores the required // smallest elements let res = new Array(N - K + 1); for ( var i = 0; i < res.length; i++) { res[i] = new Array(2); } // Update the smallest elements row-wise for (let i = 0; i < N; i++) { for (let j = 0; j < M - K + 1; j++) { let min = Number.MAX_VALUE; for (let k = j; k < j + K; k++) { min = Math.min(min, nums[i][k]); } nums[i][j] = min; } } // Update the minimum column-wise for (let j = 0; j < M; j++) { for (let i = 0; i < N - K + 1; i++) { let min = Number.MAX_VALUE; for (let k = i; k < i + K; k++) { min = Math.min(min, nums[k][j]); } nums[i][j] = min; } } // Store the final submatrix with // required minimum values for (let i = 0; i < N - K + 1; i++) for (let j = 0; j < M - K + 1; j++) res[i][j] = nums[i][j]; // Return the resultant matrix return res; } function smallestinKsubmatrices(arr, K) { // Function Call let res = matrixMinimum(arr, K); // Print resultant matrix with the // minimum values of KxK sub-matrix for (let i = 0; i < res.length; i++) { for (let j = 0; j < res[0].length; j++) { document.write(res[i][j] + " " ); } document.write( "<br/>" ); } } // Driver Code // Given matrix let arr = [[ -1, 5, 4, 1, -3 ], [ 4, 3, 1, 1, 6 ], [ 2, -2, 5, 3, 1 ], [ 8, 5, 1, 9, -4 ], [ 12, 3, 5, 8, 1 ]]; // Given K let K = 3; smallestinKsubmatrices(arr, K); </script> |
-2 -2 -3 -2 -2 -4 -2 -2 -4
Time Complexity: O( max(N, M)3 )
Auxiliary Space: O( (N-K+1)*(M-K+1) )
Most efficient approach:
Let the number of rows be n and the number of columns be m in the given matrix. We take m deques where first we store the indexes of a monotonically increasing set from i=0 to k-1 in the jth column. We store this in deque[j].
Then for every row i=k-1 to n-1 we perform the following steps:
- We traverse all the columns j=0 to m-1 and we store the indexes of the monotonically increasing set from rows=i-k+1 to i. So all deque[j] contains set of indexes which is a monotically increasing set. The elements in deque[j]={i-k+1<=row<=i,col=j}.
- We then initialize a deque of pairs dQ[{i,j}]. We traverse j=0 to k-1 and keep the grid indices of a monotonically increasing set in that dQ. basically dQ picks the front element(smallest valued ‘i’) in deque[j] and compares it with the previously stored elements in dQ. All elements that are greater or equal to that element are removed from the back of dQ. Then we add that element in the back of dQ.
- For the last step we iterate j=k-1 to m-1 and filter the dQ from the back in such a way that the front element has a column-index>=j-k+1 and we have already filtered out the row-index that are <i-k+1 in the first step. So all elements in dQ are {i-k+1>=row>=i,j-k+1>=col>=j}. Now we take the front element of dQ and assign it as the minimum element in the submatrix that is formed by {left-up,right-down}={{i-k+1,j-k+1},{i,j}}
C++
#include<bits/stdc++.h> using namespace std; // Function to find the minimum element in each K-sized submatrix of a given matrix vector<vector< int >> min_Ele_In_K_Sized_SubMatrix(vector<vector< int >> matrix, int K){ int n = matrix.size(); // Number of rows in the matrix int m = matrix[0].size(); // Number of columns in the matrix // Result matrix to store the minimum elements in each K-sized submatrix vector<vector< int >> res(n - K + 1, vector< int >(m - K + 1)); // Vector of deques to maintain the indices of elements in each column vector<deque< int >> dequ(m); // Preprocess the first K-1 rows in each column for ( int j = 0; j < m; j++){ for ( int i = 0; i < K - 1; i++){ int x = matrix[i][j]; // Maintain an increasing order deque of indices //we pop all elements from the back of the deque which are greater than current element //hence always maintaining the order that the elements in the deque will be monotonically //increasing while (!dequ[j].empty() && matrix[dequ[j].back()][j] >= x) dequ[j].pop_back(); dequ[j].push_back(i); } } // Process the remaining rows for ( int i = K - 1; i < n; i++){ for ( int j = 0; j < m; j++){ int x = matrix[i][j]; // Maintain an increasing order deque of indices while (!dequ[j].empty() && matrix[dequ[j].back()][j] >= x) dequ[j].pop_back(); dequ[j].push_back(i); // Remove elements that are no longer in the K-sized window if (dequ[j].size() > 1 && dequ[j].front() <= i - K) dequ[j].pop_front(); } // Deque to maintain indices and values of elements in the first K-1 columns deque<pair< int , int >> dQ; for ( int j = 0; j < K - 1; j++){ int row = dequ[j].front(); int x = matrix[row][j]; // Maintain an increasing order deque of indices and values while (!dQ.empty() && matrix[dQ.back().first][dQ.back().second] >= x) dQ.pop_back(); dQ.push_back({row, j}); } // Process the remaining columns for ( int j = K - 1; j < m; j++){ int row = dequ[j].front(); int x = matrix[row][j]; // Maintain an increasing order deque of indices and values while (!dQ.empty() && matrix[dQ.back().first][dQ.back().second] >= x) dQ.pop_back(); dQ.push_back({row, j}); // Remove elements that are no longer in the K-sized window if (dQ.size() > 1 && dQ.front().second <= j - K) dQ.pop_front(); // Store the minimum element in the result matrix res[i - K + 1][j - K + 1] = matrix[dQ.front().first][dQ.front().second]; } } return res; } int main(){ // Example matrix vector<vector< int >> matrix = {{-1, 5, 4, 1, -3}, {4, 3, 1, 1, 6}, {2, -2, 5, 3, 1}, {8, 5, 1, 9, -4}, {12, 3, 5, 8, 1}}; int K = 3; // Call the function to find the minimum element in each K-sized submatrix vector<vector< int >> res = min_Ele_In_K_Sized_SubMatrix(matrix, K); // Print the result matrix for ( int i = 0; i < res.size(); i++){ for ( int j = 0; j < res[i].size(); j++) cout << res[i][j] << " " ; cout << "\n" ; } return 0; } |
Java
import java.util.ArrayDeque; import java.util.Deque; public class MinElementInKSizeSubMatrix { static int [][] minEleInKSizeSubMatrix( int [][] matrix, int K) { int n = matrix.length; int m = matrix[ 0 ].length; int [][] res = new int [n - K + 1 ][m - K + 1 ]; // Array of Deques to maintain the indices of elements in each column Deque<Integer>[] deq = new ArrayDeque[m]; for ( int j = 0 ; j < m; j++) { deq[j] = new ArrayDeque<>(); for ( int i = 0 ; i < K - 1 ; i++) { int x = matrix[i][j]; // Maintain an increasing order deque of indices while (!deq[j].isEmpty() && matrix[deq[j].peekLast()][j] >= x) { deq[j].pollLast(); } deq[j].offerLast(i); } } for ( int i = K - 1 ; i < n; i++) { for ( int j = 0 ; j < m; j++) { int x = matrix[i][j]; // Maintain an increasing order deque of indices while (!deq[j].isEmpty() && matrix[deq[j].peekLast()][j] >= x) { deq[j].pollLast(); } deq[j].offerLast(i); // Remove elements that are no longer in the K-sized window if (deq[j].size() > 1 && deq[j].peekFirst() <= i - K) { deq[j].pollFirst(); } } // Deque to maintain indices and values of elements in the first K-1 columns Deque< int []> dq = new ArrayDeque<>(); for ( int j = 0 ; j < K - 1 ; j++) { int row = deq[j].peekFirst(); int x = matrix[row][j]; // Maintain an increasing order deque of indices and values while (!dq.isEmpty() && matrix[dq.peekLast()[ 0 ]][dq.peekLast()[ 1 ]] >= x) { dq.pollLast(); } dq.offerLast( new int []{row, j}); } for ( int j = K - 1 ; j < m; j++) { int row = deq[j].peekFirst(); int x = matrix[row][j]; // Maintain an increasing order deque of indices and values while (!dq.isEmpty() && matrix[dq.peekLast()[ 0 ]][dq.peekLast()[ 1 ]] >= x) { dq.pollLast(); } dq.offerLast( new int []{row, j}); // Remove elements that are no longer in the K-sized window if (dq.size() > 1 && dq.peekFirst()[ 1 ] <= j - K) { dq.pollFirst(); } // Store the minimum element in the result matrix res[i - K + 1 ][j - K + 1 ] = matrix[dq.peekFirst()[ 0 ]][dq.peekFirst()[ 1 ]]; } } return res; } public static void main(String[] args) { // Example matrix int [][] matrix = { {- 1 , 5 , 4 , 1 , - 3 }, { 4 , 3 , 1 , 1 , 6 }, { 2 , - 2 , 5 , 3 , 1 }, { 8 , 5 , 1 , 9 , - 4 }, { 12 , 3 , 5 , 8 , 1 } }; int K = 3 ; // Call the function to find the minimum element in each K-sized submatrix int [][] result = minEleInKSizeSubMatrix(matrix, K); // Print the result matrix for ( int i = 0 ; i < result.length; i++) { for ( int j = 0 ; j < result[i].length; j++) { System.out.print(result[i][j] + " " ); } System.out.println(); } } } // This code is contributed by akshitaguprzj3 |
Python3
# Python program for the above approach from collections import deque # Function to find the minimum element in each K-sized submatrix of a given matrix def min_ele_in_k_sized_submatrix(matrix, K): n = len (matrix) # Number of rows in the matrix m = len (matrix[ 0 ]) # Number of columns in the matrix # Result matrix to store the minimum elements in each K-sized submatrix res = [[ 0 ] * (m - K + 1 ) for _ in range (n - K + 1 )] # Vector of deques to maintain the indices of elements in each column dequ = [deque() for _ in range (m)] # Preprocess the first K-1 rows in each column for j in range (m): for i in range (K - 1 ): x = matrix[i][j] # Maintain an increasing order deque of indices while dequ[j] and matrix[dequ[j][ - 1 ]][j] > = x: dequ[j].pop() dequ[j].append(i) # Process the remaining rows for i in range (K - 1 , n): for j in range (m): x = matrix[i][j] # Maintain an increasing order deque of indices while dequ[j] and matrix[dequ[j][ - 1 ]][j] > = x: dequ[j].pop() dequ[j].append(i) # Remove elements that are no longer in the K-sized window if dequ[j] and dequ[j][ 0 ] < = i - K: dequ[j].popleft() # Deque to maintain indices and values of elements in the first K-1 columns dQ = deque() for j in range (K - 1 ): row = dequ[j][ 0 ] x = matrix[row][j] # Maintain an increasing order deque of indices and values while dQ and matrix[dQ[ - 1 ][ 0 ]][dQ[ - 1 ][ 1 ]] > = x: dQ.pop() dQ.append((row, j)) # Process the remaining columns for j in range (K - 1 , m): row = dequ[j][ 0 ] x = matrix[row][j] # Maintain an increasing order deque of indices and values while dQ and matrix[dQ[ - 1 ][ 0 ]][dQ[ - 1 ][ 1 ]] > = x: dQ.pop() dQ.append((row, j)) # Remove elements that are no longer in the K-sized window if dQ and dQ[ 0 ][ 1 ] < = j - K: dQ.popleft() # Store the minimum element in the result matrix res[i - K + 1 ][j - K + 1 ] = matrix[dQ[ 0 ][ 0 ]][dQ[ 0 ][ 1 ]] return res # Driver program to test min_ele_in_k_sized_submatrix if __name__ = = "__main__" : # Example matrix matrix = [ [ - 1 , 5 , 4 , 1 , - 3 ], [ 4 , 3 , 1 , 1 , 6 ], [ 2 , - 2 , 5 , 3 , 1 ], [ 8 , 5 , 1 , 9 , - 4 ], [ 12 , 3 , 5 , 8 , 1 ] ] K = 3 # Call the function to find the minimum element in each K-sized submatrix result_matrix = min_ele_in_k_sized_submatrix(matrix, K) # Print the result matrix for row in result_matrix: print ( " " .join( map ( str , row))) # This code is contributed by Susobhan Akhuli |
C#
using System; using System.Collections.Generic; class Program { // Function to find the minimum element in each K-sized submatrix of a given matrix static List<List< int >> MinElementInKsizedSubMatrix(List<List< int >> matrix, int K) { int n = matrix.Count; // Number of rows in the matrix int m = matrix[0].Count; // Number of columns in the matrix // Result matrix to store the minimum elements in each K-sized submatrix List<List< int >> res = new List<List< int >>(n - K + 1); for ( int i = 0; i < n - K + 1; i++) { res.Add( new List< int >(m - K + 1)); } // Vector of deques to maintain the indices of elements in each column List<Queue< int >> deque = new List<Queue< int >>(m); for ( int j = 0; j < m; j++) { deque.Add( new Queue< int >()); // Preprocess the first K-1 rows in each column for ( int i = 0; i < K - 1; i++) { int x = matrix[i][j]; // Maintain an increasing order deque of indices while (deque[j].Count > 0 && matrix[deque[j].Peek()][j] >= x) deque[j].Dequeue(); deque[j].Enqueue(i); } } // Process the remaining rows for ( int i = K - 1; i < n; i++) { for ( int j = 0; j < m; j++) { int x = matrix[i][j]; // Maintain an increasing order deque of indices while (deque[j].Count > 0 && matrix[deque[j].Peek()][j] >= x) deque[j].Dequeue(); deque[j].Enqueue(i); // Remove elements that are no longer in the K-sized window if (deque[j].Count > 1 && deque[j].Peek() <= i - K) deque[j].Dequeue(); } // Deque to maintain indices and values of elements in the first K-1 columns Queue<Tuple< int , int >> dQ = new Queue<Tuple< int , int >>(); for ( int j = 0; j < K - 1; j++) { int row = deque[j].Peek(); int x = matrix[row][j]; // Maintain an increasing order deque of indices and values while (dQ.Count > 0 && matrix[dQ.Peek().Item1][dQ.Peek().Item2] >= x) dQ.Dequeue(); dQ.Enqueue( new Tuple< int , int >(row, j)); } // Process the remaining columns for ( int j = K - 1; j < m; j++) { int row = deque[j].Peek(); int x = matrix[row][j]; // Maintain an increasing order deque of indices and values while (dQ.Count > 0 && matrix[dQ.Peek().Item1][dQ.Peek().Item2] >= x) dQ.Dequeue(); dQ.Enqueue( new Tuple< int , int >(row, j)); // Remove elements that are no longer in the K-sized window if (dQ.Count > 1 && dQ.Peek().Item2 <= j - K) dQ.Dequeue(); // Store the minimum element in the result matrix res[i - K + 1].Add(matrix[dQ.Peek().Item1][dQ.Peek().Item2]); } } return res; } static void Main() { // Example matrix List<List< int >> matrix = new List<List< int >> { new List< int > { -1, 5, 4, 1, -3 }, new List< int > { 4, 3, 1, 1, 6 }, new List< int > { 2, -2, 5, 3, 1 }, new List< int > { 8, 5, 1, 9, -4 }, new List< int > { 12, 3, 5, 8, 1 } }; int K = 3; // Call the function to find the minimum element in each K-sized submatrix List<List< int >> res = MinElementInKsizedSubMatrix(matrix, K); // Print the result matrix foreach ( var row in res) { foreach ( var col in row) Console.Write(col + " " ); Console.WriteLine(); } } } |
Javascript
function minElementInKSizeSubMatrix(matrix, K) { const n = matrix.length; const m = matrix[0].length; const res = new Array(n - K + 1).fill().map(() => new Array(m - K + 1)); // Array of Deques to maintain the indices of elements in each column const deq = new Array(m); for (let j = 0; j < m; j++) { deq[j] = []; for (let i = 0; i < K - 1; i++) { const x = matrix[i][j]; // Maintain an increasing order deque of indices while (deq[j].length > 0 && matrix[deq[j][deq[j].length - 1]][j] >= x) { deq[j].pop(); } deq[j].push(i); } } for (let i = K - 1; i < n; i++) { for (let j = 0; j < m; j++) { const x = matrix[i][j]; // Maintain an increasing order deque of indices while (deq[j].length > 0 && matrix[deq[j][deq[j].length - 1]][j] >= x) { deq[j].pop(); } deq[j].push(i); // Remove elements that are no longer in the K-sized window if (deq[j].length > 1 && deq[j][0] <= i - K) { deq[j].shift(); } } // Deque to maintain indices and values of elements in the first K-1 columns const dq = []; for (let j = 0; j < K - 1; j++) { const row = deq[j][0]; const x = matrix[row][j]; // Maintain an increasing order deque of indices and values while (dq.length > 0 && matrix[dq[dq.length - 1][0]][dq[dq.length - 1][1]] >= x) { dq.pop(); } dq.push([row, j]); } for (let j = K - 1; j < m; j++) { const row = deq[j][0]; const x = matrix[row][j]; // Maintain an increasing order deque of indices and values while (dq.length > 0 && matrix[dq[dq.length - 1][0]][dq[dq.length - 1][1]] >= x) { dq.pop(); } dq.push([row, j]); // Remove elements that are no longer in the K-sized window if (dq.length > 1 && dq[0][1] <= j - K) { dq.shift(); } // Store the minimum element in the result matrix res[i - K + 1][j - K + 1] = matrix[dq[0][0]][dq[0][1]]; } } return res; } // Example usage: const matrix = [ [-1, 5, 4, 1, -3], [4, 3, 1, 1, 6], [2, -2, 5, 3, 1], [8, 5, 1, 9, -4], [12, 3, 5, 8, 1] ]; const K = 3; // Call the function to find the minimum element in each K-sized submatrix const result = minElementInKSizeSubMatrix(matrix, K); // Print the result matrix for (let i = 0; i < result.length; i++) { console.log(result[i].join( " " )); } |
-2 -2 -3 -2 -2 -4 -2 -2 -4
Time Complexity: O((n-K+1)*(m-K+1)*K)
Auxiliary Space: O((n-K+1)*(m-K+1)+m+K)
Contact Us