Given a matrix, arr[][] of dimensions M*N, and an integer S, the task is to print the count of the number of subsquares of the matrix, whose sum is equal to S.
Examples:
Input: M = 4, N = 5, S = 10, arr[][]={{2, 4, 3, 2, 10}, {3, 1, 1, 1, 5}, {1, 1, 2, 1, 4}, {2, 1, 1, 1, 3}}
Output: 3
Explanation:
Sub-squares {10}, {{2, 4}, {3, 1}} and {{1, 1, 1}, {1, 2, 1}, {1, 1, 1}} have sums equal to 10.Input: M = 3, N = 4, S = 8, arr[][]={{3, 1, 5, 3}, {2, 2, 2, 6}, {1, 2, 2, 4}}
Output: 2
Explanation:
Sub-squares {{2, 2}, {2, 2}} and {{3, 1}, {2, 2}} have sums equal to 8.
Naive Approach: The simplest approach to solve the problem is to generate all possible subsquares and check sum of all the elements of the sub-square equals to S.
Time Complexity: O(N3 * M3)
Auxiliary Space: O(1)
Alternate Approach: The above approach can be optimized by finding the prefix sum of a Matrix which results in the constant time calculation of the sum of all elements of the submatrix. Follow the steps below to solve the problem:
- Find the prefix sum of the matrix arr[][] and store it in a 2D vector say dp of dimension (M + 1)*(N + 1).
- Initialize a variable, say count as 0, to store the count of subsquares with sum S.
- Iterate over the range [1, min(N, M)] using a variable x and perform the following operations:
- Iterate over every element of the matrix arr[][] using the variables i and j and perform the following operations:
- If i and j are greater than or equal to x then find the sum of subsquares of dimension x * x with (i, j) as the bottom-right vertex in a variable, say Sum.
- Update the Sum variable as, Sum = dp[i][j] – dp[i – x][j] – dp[i][j – x] + dp[i – x][j – x].
- If the Sum is equal to S, then increment the count by 1.
- Iterate over every element of the matrix arr[][] using the variables i and j and perform the following operations:
- Finally, after completing the above steps, print the value in count as the answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function to compute prefix sumvoid find_prefixsum(int M, int N, vector<vector<int> >& arr, vector<vector<int> >& dp){ // Assign 0 to first column for (int i = 0; i <= M; i++) { dp[i][0] = 0; } // Assign 0 to first row for (int j = 0; j <= N; j++) { dp[0][j] = 0; } // Iterate over the range //[1, M] for (int i = 1; i <= M; i++) { // Iterate over the range //[1, N] for (int j = 1; j <= N; j++) { // Update dp[i][j] = dp[i][j - 1] + arr[i - 1][j - 1]; } } // Iterate over the range //[1, M] for (int i = 1; i <= M; i++) { // Iterate over the range //[1, N] for (int j = 1; j <= N; j++) { // Update dp[i][j] = dp[i][j] + dp[i - 1][j]; } }}// Function to find sub-squares// with given sum Sint findSubsquares(vector<vector<int> > arr, int M, int N, int S){ // Stores the prefix sum of // matrix vector<vector<int> > dp(M + 1, vector<int>(N + 1)); // Function call to find // prefix Sum of matrix find_prefixsum(M, N, arr, dp); // Stores the count of // subsquares with sum S int cnt = 0; for (int x = 1; x <= min(N, M); x++) { // Iterate over every // element of the matrix for (int i = x; i <= M; i++) { for (int j = x; j <= N; j++) { // Stores the sum of // subsquare of dimension // x*x formed with i, j as // the bottom-right // vertex int sum = dp[i][j] - dp[i - x][j] - dp[i][j - x] + dp[i - x][j - x]; // If sum is equal to S if (sum == S) { // Increment cnt by 1 cnt++; } } } } // Return the result return cnt;}// Driver Codeint main(){ // Input int M = 4, N = 5; vector<vector<int> > arr = { { 2, 4, 3, 2, 10 }, { 3, 1, 1, 1, 5 }, { 1, 1, 2, 1, 4 }, { 2, 1, 1, 1, 3 } }; int S = 10; // Function call cout << findSubsquares(arr, M, N, S); return 0;} |
Java
/*package whatever //do not write package name here */import java.io.*;class GFG{ // Function to compute prefix sum static void find_prefixsum(int M, int N, int[][] arr,int[][] dp) { // Assign 0 to first column for (int i = 0; i <= M; i++) { dp[i][0] = 0; } // Assign 0 to first row for (int j = 0; j <= N; j++) { dp[0][j] = 0; } // Iterate over the range //[1, M] for (int i = 1; i <= M; i++) { // Iterate over the range //[1, N] for (int j = 1; j <= N; j++) { // Update dp[i][j] = dp[i][j - 1] + arr[i - 1][j - 1]; } } // Iterate over the range //[1, M] for (int i = 1; i <= M; i++) { // Iterate over the range //[1, N] for (int j = 1; j <= N; j++) { // Update dp[i][j] = dp[i][j] + dp[i - 1][j]; } } } // Function to find sub-squares // with given sum S static int findSubsquares(int[][] arr, int M, int N,int S) { // Stores the prefix sum of // matrix int[][] dp = new int[M + 1][N + 1]; // Function call to find // prefix Sum of matrix find_prefixsum(M, N, arr, dp); // Stores the count of // subsquares with sum S int cnt = 0; for (int x = 1; x <= Math.min(N, M); x++) { // Iterate over every // element of the matrix for (int i = x; i <= M; i++) { for (int j = x; j <= N; j++) { // Stores the sum of // subsquare of dimension // x*x formed with i, j as // the bottom-right // vertex int sum = dp[i][j] - dp[i - x][j] - dp[i][j - x] + dp[i - x][j - x]; // If sum is equal to S if (sum == S) { // Increment cnt by 1 cnt++; } } } } // Return the result return cnt; } // Driver Code public static void main(String[] args) { // Input int M = 4, N = 5; int[][] arr = { { 2, 4, 3, 2, 10 }, { 3, 1, 1, 1, 5 }, { 1, 1, 2, 1, 4 }, { 2, 1, 1, 1, 3 } }; int S = 10; // Function call System.out.println(findSubsquares(arr, M, N, S)); }}// This code is contributed by shinjanpatra |
Python3
# python program for the above approach# Function to compute prefix sumdef find_prefixsum(M, N, arr, dp): # Assign 0 to first column for i in range(0, M+1): dp[i][0] = 0 # Assign 0 to first row for j in range(0, N+1): dp[0][j] = 0 # Iterate over the range # [1, M] for i in range(1, M+1): # Iterate over the range # [1, N] for j in range(1, N+1): dp[i][j] = dp[i][j - 1] + arr[i - 1][j - 1] # Iterate over the range # [1, M] for i in range(1, M+1): # Iterate over the range # [1, N] for j in range(1, N+1): # Update dp[i][j] = dp[i][j] + dp[i - 1][j]# Function to find sub-squares# with given sum Sdef findSubsquares(arr, M, N, S): # Stores the prefix sum of # matrix dp = [[0 for i in range(N + 1)] for col in range(M + 1)] # Function call to find # prefix Sum of matrix find_prefixsum(M, N, arr, dp) # Stores the count of # subsquares with sum S cnt = 0 for x in range(1, min(N, M)): # Iterate over every # element of the matrix for i in range(x, M + 1): for j in range(x, N + 1): # Stores the sum of # subsquare of dimension # x*x formed with i, j as # the bottom-right # vertex sum = dp[i][j] - dp[i - x][j] - dp[i][j - x] + dp[i - x][j - x] # If sum is equal to S if (sum == S): # Increment cnt by 1 cnt += 1 # Return the result return cnt# Driver Code# InputM = 4N = 5arr = [[2, 4, 3, 2, 10], [3, 1, 1, 1, 5], [1, 1, 2, 1, 4], [2, 1, 1, 1, 3]]S = 10# Function callprint(findSubsquares(arr, M, N, S))# This code is contributed by amreshkumar3 |
C#
// C# program for the above approachusing System;class GFG { // Function to compute prefix sum static void find_prefixsum(int M, int N, int[, ] arr, int[, ] dp) { // Assign 0 to first column for (int i = 0; i <= M; i++) { dp[i, 0] = 0; } // Assign 0 to first row for (int j = 0; j <= N; j++) { dp[0, j] = 0; } // Iterate over the range //[1, M] for (int i = 1; i <= M; i++) { // Iterate over the range //[1, N] for (int j = 1; j <= N; j++) { // Update dp[i, j] = dp[i, j - 1] + arr[i - 1, j - 1]; } } // Iterate over the range //[1, M] for (int i = 1; i <= M; i++) { // Iterate over the range //[1, N] for (int j = 1; j <= N; j++) { // Update dp[i, j] = dp[i, j] + dp[i - 1, j]; } } } // Function to find sub-squares // with given sum S static int findSubsquares(int[, ] arr, int M, int N, int S) { // Stores the prefix sum of // matrix int[, ] dp = new int[M + 1, N + 1]; // Function call to find // prefix Sum of matrix find_prefixsum(M, N, arr, dp); // Stores the count of // subsquares with sum S int cnt = 0; for (int x = 1; x <= Math.Min(N, M); x++) { // Iterate over every // element of the matrix for (int i = x; i <= M; i++) { for (int j = x; j <= N; j++) { // Stores the sum of // subsquare of dimension // x*x formed with i, j as // the bottom-right // vertex int sum = dp[i, j] - dp[i - x, j] - dp[i, j - x] + dp[i - x, j - x]; // If sum is equal to S if (sum == S) { // Increment cnt by 1 cnt++; } } } } // Return the result return cnt; } // Driver Code public static void Main() { // Input int M = 4, N = 5; int[, ] arr = { { 2, 4, 3, 2, 10 }, { 3, 1, 1, 1, 5 }, { 1, 1, 2, 1, 4 }, { 2, 1, 1, 1, 3 } }; int S = 10; // Function call Console.WriteLine(findSubsquares(arr, M, N, S)); }}// This code is contributed by ukasp. |
Javascript
<script>// Javascript program for the above approach// Function to compute prefix sumfunction find_prefixsum(M, N, arr, dp){ // Assign 0 to first column for (var i = 0; i <= M; i++) { dp[i][0] = 0; } // Assign 0 to first row for (var j = 0; j <= N; j++) { dp[0][j] = 0; } // Iterate over the range //[1, M] for (var i = 1; i <= M; i++) { // Iterate over the range //[1, N] for (var j = 1; j <= N; j++) { // Update dp[i][j] = dp[i][j - 1] + arr[i - 1][j - 1]; } } // Iterate over the range //[1, M] for (var i = 1; i <= M; i++) { // Iterate over the range //[1, N] for (var j = 1; j <= N; j++) { // Update dp[i][j] = dp[i][j] + dp[i - 1][j]; } }}// Function to find sub-squares// with given sum Sfunction findSubsquares(arr, M, N, S){ // Stores the prefix sum of // matrix var dp = Array.from(Array(M+1), ()=>Array(N+1)); // Function call to find // prefix Sum of matrix find_prefixsum(M, N, arr, dp); // Stores the count of // subsquares with sum S var cnt = 0; for (var x = 1; x <= Math.min(N, M); x++) { // Iterate over every // element of the matrix for (var i = x; i <= M; i++) { for (var j = x; j <= N; j++) { // Stores the sum of // subsquare of dimension // x*x formed with i, j as // the bottom-right // vertex var sum = dp[i][j] - dp[i - x][j] - dp[i][j - x] + dp[i - x][j - x]; // If sum is equal to S if (sum == S) { // Increment cnt by 1 cnt++; } } } } // Return the result return cnt;}// Driver Code// Inputvar M = 4, N = 5;var arr = [ [ 2, 4, 3, 2, 10 ], [ 3, 1, 1, 1, 5 ], [ 1, 1, 2, 1, 4 ], [ 2, 1, 1, 1, 3 ] ];var S = 10;// Function calldocument.write( findSubsquares(arr, M, N, S));// This code is contributed by rrrtnx.</script> |
Output
3
Time Complexity: O(M * N * min(M, N))
Auxiliary Space: O(N * M)
Efficient Approach: The above approach can be further optimized using a binary search Algorithm. Refer to the link for the efficient solution [Count of submatrix with sum X in a given Matrix].
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!
