Given a matrix mat[][] and two integers K and S, the task is to count all K x K sub-matrix such that the sum of all the elements in the sub-matrix is greater than or equal to S.
Examples:
Input: K = 2, S = 15
mat[][] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}}
Output: 3
Explanation:
In the given matrix there are 3 sub-matrix
Sub-Matrix 1: (0, 1) to (1, 2)
Sum = 2 + 3 + 5 + 6 = 16
Sub-matrix 2: (1, 0) to (2, 1)
Sum = 4 + 5 + 7 + 8 = 24
Sub-matrix 3: (1, 1) to (2, 2)
Sum = 5 + 6 + 8 + 9 = 28
Input: K = 3, S = 35
arr[][] = {{1, 7, 1, 1, 1},
{2, 2, 2, 2, 2},
{3, 9, 6, 7, 3},
{4, 3, 2, 4, 5},
{5, 1, 5, 3, 1}}
Output: 5
Naive Approach: Iterate over all the possible sub-matrix of size K x K and find the sum of each matrix. If the sum of any sub-matrix is greater than the given sum S, then increment the count by 1.
Efficient Approach: The idea is to precompute the prefix sum of the matrix such that the sum of every sub-matrix sum can be computed in O(1) time. Finally, Iterate over all the possible positions of the matrix and check the sum of the sub-matrix of size K x K from that positions with the inclusion and exclusion principle. If the sum is greater than the given sum then increment the count of such sub-matrix by 1.
Below is the implementation of the above approach:
C++
// C++ program to count total number// of k x k sub matrix whose sum is// greater than the given number S#include <iostream>using namespace std;#define dim 5// Function to create Prefix sum // matrix from the given matrixvoid createTable(int mtrx[][dim], int k, int p, int dp[][dim]){ // Store first value in table dp[0][0] = mtrx[0][0]; // Initialize first row of matrix for (int j = 1; j < dim; j++) { dp[0][j] = mtrx[0][j] + dp[0][j - 1]; } // Initialize first column of matrix for (int i = 1; i < dim; i++) { dp[i][0] = mtrx[i][0] + dp[i - 1][0]; } // Initialize rest table with sum for (int i = 1; i < dim; i++) { for (int j = 1; j < dim; j++) { dp[i][j] = mtrx[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; } }}// Utility Function to count the submatrix// whose sum is greater than the Sint countSubMatrixUtil(int dp[][dim], int k, int p){ int count = 0; int subMatSum = 0; // Loop to iterate over all the // possible positions of the // given matrix mat[][] for (int i = k - 1; i < dim; i++) { for (int j = k - 1; j < dim; j++) { if (i == (k - 1) || j == (k - 1)) { // Condition to check, if K x K // is first sub matrix if (i == (k - 1) && j == (k - 1)) { subMatSum = dp[i][j]; } // Condition to check sub-matrix // has no margin at top else if (i == (k - 1)) { subMatSum = dp[i][j] - dp[i][j - k]; } // Condition when sub matrix // has no margin at left else { subMatSum = dp[i][j] - dp[i - k][j]; } } // Condition when submatrix has // margin at top and left else { subMatSum = dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k]; } // Increment count, If sub matrix // sum is greater than S if (subMatSum >= p) { count++; } } } return count;}// Function to count submatrix of// size k x k such that sum if // greater than or equal to Sint countSubMatrix(int mtrx[][dim], int k, int p){ int dp[dim][dim]; // For loop to initialize prefix sum // matrix with zero, initially for (int i = 0; i < dim; i++) { for (int j = 0; j < dim; j++) { dp[i][j] = 0; } } // Function to create the // prefix sum matrix createTable(mtrx, k, p, dp); return countSubMatrixUtil(dp, k, p);}// Driver Codeint main(){ int mtrx[dim][dim] = { { 1, 7, 1, 1, 1 }, { 2, 2, 2, 2, 2 }, { 3, 9, 6, 7, 3 }, { 4, 3, 2, 4, 5 }, { 5, 1, 5, 3, 1 } }; int k = 3; int p = 35; // Print total number of sub matrix cout << countSubMatrix(mtrx, k, p); return 0;} |
Java
// Java program to count total number// of k x k sub matrix whose sum is// greater than the given number Simport java.util.*;class GFG{static final int dim = 5;// Function to create prefix sum // matrix from the given matrixstatic void createTable(int mtrx[][], int k, int p, int dp[][]){ // Store first value in table dp[0][0] = mtrx[0][0]; // Initialize first row of matrix for(int j = 1; j < dim; j++) { dp[0][j] = mtrx[0][j] + dp[0][j - 1]; } // Initialize first column of matrix for(int i = 1; i < dim; i++) { dp[i][0] = mtrx[i][0] + dp[i - 1][0]; } // Initialize rest table with sum for(int i = 1; i < dim; i++) { for(int j = 1; j < dim; j++) { dp[i][j] = mtrx[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; } }}// Utility Function to count the submatrix// whose sum is greater than the Sstatic int countSubMatrixUtil(int dp[][], int k, int p){ int count = 0; int subMatSum = 0; // Loop to iterate over all the // possible positions of the // given matrix mat[][] for(int i = k - 1; i < dim; i++) { for(int j = k - 1; j < dim; j++) { if (i == (k - 1) || j == (k - 1)) { // Condition to check, if K x K // is first sub matrix if (i == (k - 1) && j == (k - 1)) { subMatSum = dp[i][j]; } // Condition to check sub-matrix // has no margin at top else if (i == (k - 1)) { subMatSum = dp[i][j] - dp[i][j - k]; } // Condition when sub matrix // has no margin at left else { subMatSum = dp[i][j] - dp[i - k][j]; } } // Condition when submatrix has // margin at top and left else { subMatSum = dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k]; } // Increment count, If sub matrix // sum is greater than S if (subMatSum >= p) { count++; } } } return count;}// Function to count submatrix of// size k x k such that sum if // greater than or equal to Sstatic int countSubMatrix(int mtrx[][], int k, int p){ int [][]dp = new int[dim][dim]; // For loop to initialize prefix sum // matrix with zero, initially for(int i = 0; i < dim; i++) { for(int j = 0; j < dim; j++) { dp[i][j] = 0; } } // Function to create the // prefix sum matrix createTable(mtrx, k, p, dp); return countSubMatrixUtil(dp, k, p);}// Driver Codepublic static void main(String[] args){ int mtrx[][] = { { 1, 7, 1, 1, 1 }, { 2, 2, 2, 2, 2 }, { 3, 9, 6, 7, 3 }, { 4, 3, 2, 4, 5 }, { 5, 1, 5, 3, 1 } }; int k = 3; int p = 35; // Print total number of sub matrix System.out.print(countSubMatrix(mtrx, k, p));}}// This code is contributed by Rohit_ranjan |
Python3
# Python3 program to count total number# of k x k sub matrix whose sum is# greater than the given number Sdim = 5# Function to create prefix sum # matrix from the given matrixdef createTable(mtrx, k, p, dp): # Store first value in table dp[0][0] = mtrx[0][0] # Initialize first row of matrix for j in range(1, dim): dp[0][j] = mtrx[0][j] + dp[0][j - 1] # Initialize first column of matrix for i in range(1, dim): dp[i][0] = mtrx[i][0] + dp[i - 1][0] # Initialize rest table with sum for i in range(1, dim): for j in range(1, dim): dp[i][j] = (mtrx[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) # Utility function to count the submatrix# whose sum is greater than the Sdef countSubMatrixUtil(dp, k, p): count = 0 subMatSum = 0 # Loop to iterate over all the # possible positions of the # given matrix mat[][] for i in range(k - 1, dim): for j in range(k - 1, dim, 1): if (i == (k - 1) or j == (k - 1)): # Condition to check, if K x K # is first sub matrix if (i == (k - 1) and j == (k - 1)): subMatSum = dp[i][j] # Condition to check sub-matrix # has no margin at top elif (i == (k - 1)): subMatSum = dp[i][j] - dp[i][j - k] # Condition when sub matrix # has no margin at left else: subMatSum = dp[i][j] - dp[i - k][j] # Condition when submatrix has # margin at top and left else: subMatSum = (dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k]) # Increment count, If sub matrix # sum is greater than S if (subMatSum >= p): count += 1 return count # Function to count submatrix of# size k x k such that sum if # greater than or equal to Sdef countSubMatrix(mtrx, k, p): dp = [[0 for i in range(dim)] for j in range(dim)] # For loop to initialize prefix sum # matrix with zero, initially for i in range(dim): for j in range(dim): dp[i][j] = 0 # Function to create the # prefix sum matrix createTable(mtrx, k, p, dp) return countSubMatrixUtil(dp, k, p)# Driver Codeif __name__ == '__main__': mtrx = [ [ 1, 7, 1, 1, 1 ], [ 2, 2, 2, 2, 2 ], [ 3, 9, 6, 7, 3 ], [ 4, 3, 2, 4, 5 ], [ 5, 1, 5, 3, 1 ] ] k = 3 p = 35 # Print total number of sub matrix print(countSubMatrix(mtrx, k, p))# This code is contributed by Bhupendra_Singh |
C#
// C# program to count total number// of k x k sub matrix whose sum is// greater than the given number Susing System;class GFG{static readonly int dim = 5;// Function to create prefix sum // matrix from the given matrixstatic void createTable(int [,]mtrx, int k, int p, int [,]dp){ // Store first value in table dp[0, 0] = mtrx[0, 0]; // Initialize first row of matrix for(int j = 1; j < dim; j++) { dp[0, j] = mtrx[0, j] + dp[0, j - 1]; } // Initialize first column of matrix for(int i = 1; i < dim; i++) { dp[i, 0] = mtrx[i, 0] + dp[i - 1, 0]; } // Initialize rest table with sum for(int i = 1; i < dim; i++) { for(int j = 1; j < dim; j++) { dp[i, j] = mtrx[i, j] + dp[i - 1, j] + dp[i, j - 1] - dp[i - 1, j - 1]; } }}// Utility Function to count the submatrix// whose sum is greater than the Sstatic int countSubMatrixUtil(int [,]dp, int k, int p){ int count = 0; int subMatSum = 0; // Loop to iterate over all the // possible positions of the // given matrix [,]mat for(int i = k - 1; i < dim; i++) { for(int j = k - 1; j < dim; j++) { if (i == (k - 1) || j == (k - 1)) { // Condition to check, if K x K // is first sub matrix if (i == (k - 1) && j == (k - 1)) { subMatSum = dp[i, j]; } // Condition to check sub-matrix // has no margin at top else if (i == (k - 1)) { subMatSum = dp[i, j] - dp[i, j - k]; } // Condition when sub matrix // has no margin at left else { subMatSum = dp[i, j] - dp[i - k, j]; } } // Condition when submatrix has // margin at top and left else { subMatSum = dp[i, j] - dp[i - k, j] - dp[i, j - k] + dp[i - k, j - k]; } // Increment count, If sub matrix // sum is greater than S if (subMatSum >= p) { count++; } } } return count;}// Function to count submatrix of// size k x k such that sum if // greater than or equal to Sstatic int countSubMatrix(int [,]mtrx, int k, int p){ int [,]dp = new int[dim, dim]; // For loop to initialize prefix sum // matrix with zero, initially for(int i = 0; i < dim; i++) { for(int j = 0; j < dim; j++) { dp[i, j] = 0; } } // Function to create the // prefix sum matrix createTable(mtrx, k, p, dp); return countSubMatrixUtil(dp, k, p);}// Driver Codepublic static void Main(String[] args){ int [,]mtrx = { { 1, 7, 1, 1, 1 }, { 2, 2, 2, 2, 2 }, { 3, 9, 6, 7, 3 }, { 4, 3, 2, 4, 5 }, { 5, 1, 5, 3, 1 } }; int k = 3; int p = 35; // Print total number of sub matrix Console.Write(countSubMatrix(mtrx, k, p));}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to count total number// of k x k sub matrix whose sum is// greater than the given number Svar dim = 5;// Function to create Prefix sum // matrix from the given matrixfunction createTable(mtrx, k, p, dp){ // Store first value in table dp[0][0] = mtrx[0][0]; // Initialize first row of matrix for (var j = 1; j < dim; j++) { dp[0][j] = mtrx[0][j] + dp[0][j - 1]; } // Initialize first column of matrix for (var i = 1; i < dim; i++) { dp[i][0] = mtrx[i][0] + dp[i - 1][0]; } // Initialize rest table with sum for (var i = 1; i < dim; i++) { for (var j = 1; j < dim; j++) { dp[i][j] = mtrx[i][j] + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; } }}// Utility Function to count the submatrix// whose sum is greater than the Sfunction countSubMatrixUtil(dp, k, p){ var count = 0; var subMatSum = 0; // Loop to iterate over all the // possible positions of the // given matrix mat[][] for (var i = k - 1; i < dim; i++) { for (var j = k - 1; j < dim; j++) { if (i == (k - 1) || j == (k - 1)) { // Condition to check, if K x K // is first sub matrix if (i == (k - 1) && j == (k - 1)) { subMatSum = dp[i][j]; } // Condition to check sub-matrix // has no margin at top else if (i == (k - 1)) { subMatSum = dp[i][j] - dp[i][j - k]; } // Condition when sub matrix // has no margin at left else { subMatSum = dp[i][j] - dp[i - k][j]; } } // Condition when submatrix has // margin at top and left else { subMatSum = dp[i][j] - dp[i - k][j] - dp[i][j - k] + dp[i - k][j - k]; } // Increment count, If sub matrix // sum is greater than S if (subMatSum >= p) { count++; } } } return count;}// Function to count submatrix of// size k x k such that sum if // greater than or equal to Sfunction countSubMatrix(mtrx, k, p){ var dp = Array.from(Array(dim), ()=>Array(dim)); // For loop to initialize prefix sum // matrix with zero, initially for (var i = 0; i < dim; i++) { for (var j = 0; j < dim; j++) { dp[i][j] = 0; } } // Function to create the // prefix sum matrix createTable(mtrx, k, p, dp); return countSubMatrixUtil(dp, k, p);}// Driver Codevar mtrx = [ [ 1, 7, 1, 1, 1 ], [ 2, 2, 2, 2, 2 ], [ 3, 9, 6, 7, 3 ], [ 4, 3, 2, 4, 5 ], [ 5, 1, 5, 3, 1 ]];var k = 3;var p = 35;// Print total number of sub matrixdocument.write( countSubMatrix(mtrx, k, p));</script> |
Output:
5
Time Complexity: O(M * N)
Auxiliary Space: O(M * N)
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!
