Smallest element from all square submatrices of size K from a given Matrix

0 0 13 minutes read

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} } -> 5

Input: 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);

Output

-2 -2 -3 
-2 -2 -4 
-2 -2 -4

Time Complexity: O(N * M * K²)
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>

Output:

-2 -2 -3 
-2 -2 -4 
-2 -2 -4

Time Complexity: O( max(N, M)³)
Auxiliary Space: O( (N-K+1)*(M-K+1) )

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!