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_MAXusing namespace std;// Function to return the smallest elements of all KxK submatrices of a given NxM matrixvoid 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 matrixdef 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 matrixarr = [[-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 KK = 3# Function callprint_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 matrixfunction 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 matrixlet 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 submatricesprint_smallest_elements(arr, K); |
Output
-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 matrixvector<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 Codeint 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 approachimport 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 approachimport 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 resdef 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 matrixarr = [ [ -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 KK = 3# Function callsmallestinKsubmatrices(arr, K)# This code is contributed by Shivam Singh |
C#
// C# program for the above approachusing System;class GFG{// Function to returns a smallest// elements of all KxK submatrices// of a given NxM matrixpublic 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 Codepublic 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> |
Output:
-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) )
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!
