Given a matrix of size N x M and an integer X, the task is to find the number of sub-squares in the matrix with sum of elements equal to X.
Examples:
Input: N = 4, M = 5, X = 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:
{10}, {{2, 4}, {3, 1}} and {{1, 1, 1}, {1, 2, 1}, {1, 1, 1}} are subsquares with sum 10.
Input: N = 3, M = 4, X = 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 sum 8.
Naive Approach:
The simplest approach to solve the problem is to generate all possible sub-squares and check sum of all the elements of the sub-square equals to X.
C++
#include <iostream>#include <vector>using namespace std;int count_sub_squares(vector<vector<int> > matrix, int x){ int count = 0; int n = matrix.size(); int m = matrix[0].size(); int max_size = min(n, m); for (int size = 1; size <= max_size; size++) { for (int i = 0; i <= n - size; i++) { for (int j = 0; j <= m - size; j++) { int sum = 0; for (int p = i; p < i + size; p++) { for (int q = j; q < j + size; q++) { sum += matrix[p][q]; } } if (sum == x) { count++; } } } } return count;}int main(){ vector<vector<int> > matrix = { { 2, 4, 3, 2, 10 }, { 3, 1, 1, 1, 5 }, { 1, 1, 2, 1, 4 }, { 2, 1, 1, 1, 3 } }; int x = 10; int sub_squares = count_sub_squares(matrix, x); cout << "Number of sub-squares with sum " << x << " is " << sub_squares << endl; return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class SubSquares { public static int countSubSquares(List<List<Integer> > matrix, int x) { int count = 0; int n = matrix.size(); int m = matrix.get(0).size(); int max_size = Math.min(n, m); for (int size = 1; size <= max_size; size++) { for (int i = 0; i <= n - size; i++) { for (int j = 0; j <= m - size; j++) { int sum = 0; for (int p = i; p < i + size; p++) { for (int q = j; q < j + size; q++) { sum += matrix.get(p).get(q); } } if (sum == x) { count++; } } } } return count; } public static void main(String[] args) { List<List<Integer> > matrix = new ArrayList<>(); matrix.add(List.of(2, 4, 3, 2, 10)); matrix.add(List.of(3, 1, 1, 1, 5)); matrix.add(List.of(1, 1, 2, 1, 4)); matrix.add(List.of(2, 1, 1, 1, 3)); int x = 10; int subSquares = countSubSquares(matrix, x); System.out.println("Number of sub-squares with sum " + x + " is " + subSquares); }} |
Python3
def count_sub_squares(matrix, x): count = 0 n = len(matrix) m = len(matrix[0]) max_size = min(n, m) # Loop over all possible square sizes from 1 to max_size for size in range(1, max_size + 1): # Loop over all possible starting points (i, j) of the square for i in range(n - size + 1): for j in range(m - size + 1): # Calculate the sum of elements in the current square sum_ = 0 for p in range(i, i + size): for q in range(j, j + size): sum_ += matrix[p][q] # If the sum of elements in the current square is equal to x, increment count if sum_ == x: count += 1 return countdef main(): matrix = [ [2, 4, 3, 2, 10], [3, 1, 1, 1, 5], [1, 1, 2, 1, 4], [2, 1, 1, 1, 3] ] x = 10 sub_squares = count_sub_squares(matrix, x) print("Number of sub-squares with sum", x, "is", sub_squares)if __name__ == "__main__": main() |
Output
Number of sub-squares with sum 10 is 3
Time Complexity: O(N2 * M2*min(N,M))
Auxiliary Space: O(1), since no extra space has been taken.
Efficient Approach: To optimize the above naive approach the sum of all the element of all the matrix till each cell has to be made. Below are the steps:
- Precalculate the sum of all rectangles with its upper left corner at (0, 0) and lower right at (i, j) in O(N * M) computational complexity.
- Now, it can be observed that, for every upper left corner, there can be at most one square with sum X since elements of the matrix are positive.
- Keeping this in mind we can use binary search to check if there exists a square with sum X.
- For every cell (i, j) in the matrix, fix it as the upper left corner of the subsquare. Then, traverse over all possible subsquares with (i, j) as the upper left corner and increase count if sum is equal to X or not.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Size of a column#define m 5// Function to find the count of submatrix// whose sum is Xint countSubsquare(int arr[][m], int n, int X){ int dp[n + 1][m + 1]; memset(dp, 0, sizeof(dp)); // Copying arr to dp and making // it indexed 1 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp[i + 1][j + 1] = arr[i][j]; } } // Precalculate and store the sum // of all rectangles with upper // left corner at (0, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // Calculating sum in // a 2d grid dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; } } // Stores the answer int cnt = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // Fix upper left corner // at {i, j} and perform // binary search on all // such possible squares // Minimum length of square int lo = 1; // Maximum length of square int hi = min(n - i, m - j) + 1; // Flag to set if sub-square // with sum X is found bool found = false; while (lo <= hi) { int mid = (lo + hi) / 2; // Calculate lower // right index if upper // right corner is at {i, j} int ni = i + mid - 1; int nj = j + mid - 1; // Calculate the sum of // elements in the submatrix // with upper left column // {i, j} and lower right // column at {ni, nj}; int sum = dp[ni][nj] - dp[ni][j - 1] - dp[i - 1][nj] + dp[i - 1][j - 1]; if (sum >= X) { // If sum X is found if (sum == X) { found = true; } hi = mid - 1; // If sum > X, then size of // the square with sum X // must be less than mid } else { // If sum < X, then size of // the square with sum X // must be greater than mid lo = mid + 1; } } // If found, increment // count by 1; if (found == true) { cnt++; } } } return cnt;}// Driver Codeint main(){ int N = 4, X = 10; // Given Matrix arr[][] int arr[N][m] = { { 2, 4, 3, 2, 10 }, { 3, 1, 1, 1, 5 }, { 1, 1, 2, 1, 4 }, { 2, 1, 1, 1, 3 } }; // Function Call cout << countSubsquare(arr, N, X) << endl; return 0;} |
Java
// Java program for the above approach import java.util.*;class GFG{ // Size of a column static final int m = 5; // Function to find the count of submatrix // whose sum is X static int countSubsquare(int arr[][], int n, int X) { int [][]dp = new int[n + 1][m + 1]; // Copying arr to dp and making // it indexed 1 for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp[i + 1][j + 1] = arr[i][j]; } } // Precalculate and store the sum // of all rectangles with upper // left corner at (0, 0); for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // Calculating sum in // a 2d grid dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; } } // Stores the answer int cnt = 0; for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { // Fix upper left corner // at {i, j} and perform // binary search on all // such possible squares // Minimum length of square int lo = 1; // Maximum length of square int hi = Math.min(n - i, m - j) + 1; // Flag to set if sub-square // with sum X is found boolean found = false; while (lo <= hi) { int mid = (lo + hi) / 2; // Calculate lower // right index if upper // right corner is at {i, j} int ni = i + mid - 1; int nj = j + mid - 1; // Calculate the sum of // elements in the submatrix // with upper left column // {i, j} and lower right // column at {ni, nj}; int sum = dp[ni][nj] - dp[ni][j - 1] - dp[i - 1][nj] + dp[i - 1][j - 1]; if (sum >= X) { // If sum X is found if (sum == X) { found = true; } hi = mid - 1; // If sum > X, then size of // the square with sum X // must be less than mid } else { // If sum < X, then size of // the square with sum X // must be greater than mid lo = mid + 1; } } // If found, increment // count by 1; if (found == true) { cnt++; } } } return cnt; } // Driver Code public static void main(String[] args) { int N = 4, X = 10; // Given Matrix arr[][] int arr[][] = { { 2, 4, 3, 2, 10 }, { 3, 1, 1, 1, 5 }, { 1, 1, 2, 1, 4 }, { 2, 1, 1, 1, 3 } }; // Function Call System.out.print(countSubsquare(arr, N, X) + "\n"); }} // This code is contributed by sapnasingh4991 |
Python3
# Python3 program for the above approach# Size of a columnm = 5# Function to find the count of # submatrix whose sum is Xdef countSubsquare(arr, n, X): dp = [[ 0 for x in range(m + 1)] for y in range(n + 1)] # Copying arr to dp and making # it indexed 1 for i in range(n): for j in range(m): dp[i + 1][j + 1] = arr[i][j] # Precalculate and store the sum # of all rectangles with upper # left corner at (0, 0); for i in range(1, n + 1): for j in range(1, m + 1): # Calculating sum in # a 2d grid dp[i][j] += (dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]) # Stores the answer cnt = 0 for i in range(1, n + 1): for j in range(1, m + 1): # Fix upper left corner # at {i, j} and perform # binary search on all # such possible squares # Minimum length of square lo = 1 # Maximum length of square hi = min(n - i, m - j) + 1 # Flag to set if sub-square # with sum X is found found = False while (lo <= hi): mid = (lo + hi) // 2 # Calculate lower right # index if upper right # corner is at {i, j} ni = i + mid - 1 nj = j + mid - 1 # Calculate the sum of # elements in the submatrix # with upper left column # {i, j} and lower right # column at {ni, nj}; sum = (dp[ni][nj] - dp[ni][j - 1] - dp[i - 1][nj] + dp[i - 1][j - 1]) if (sum >= X): # If sum X is found if (sum == X): found = True hi = mid - 1 # If sum > X, then size of # the square with sum X # must be less than mid else: # If sum < X, then size of # the square with sum X # must be greater than mid lo = mid + 1 # If found, increment # count by 1; if (found == True): cnt += 1 return cnt# Driver Codeif __name__ =="__main__": N, X = 4, 10 # Given matrix arr[][] arr = [ [ 2, 4, 3, 2, 10 ], [ 3, 1, 1, 1, 5 ], [ 1, 1, 2, 1, 4 ], [ 2, 1, 1, 1, 3 ] ] # Function call print(countSubsquare(arr, N, X))# This code is contributed by chitranayal |
C#
// C# program for the above approach using System;class GFG{ // Size of a column static readonly int m = 5; // Function to find the count of submatrix // whose sum is X static int countSubsquare(int [,]arr, int n, int X) { int [,]dp = new int[n + 1, m + 1]; // Copying arr to dp and making // it indexed 1 for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { dp[i + 1, j + 1] = arr[i, j]; } } // Precalculate and store the sum // of all rectangles with upper // left corner at (0, 0); for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { // Calculating sum in // a 2d grid dp[i, j] += dp[i - 1, j] + dp[i, j - 1] - dp[i - 1, j - 1]; } } // Stores the answer int cnt = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { // Fix upper left corner // at {i, j} and perform // binary search on all // such possible squares // Minimum length of square int lo = 1; // Maximum length of square int hi = Math.Min(n - i, m - j) + 1; // Flag to set if sub-square // with sum X is found bool found = false; while (lo <= hi) { int mid = (lo + hi) / 2; // Calculate lower // right index if upper // right corner is at {i, j} int ni = i + mid - 1; int nj = j + mid - 1; // Calculate the sum of // elements in the submatrix // with upper left column // {i, j} and lower right // column at {ni, nj}; int sum = dp[ni, nj] - dp[ni, j - 1] - dp[i - 1, nj] + dp[i - 1, j - 1]; if (sum >= X) { // If sum X is found if (sum == X) { found = true; } hi = mid - 1; // If sum > X, then size of // the square with sum X // must be less than mid } else { // If sum < X, then size of // the square with sum X // must be greater than mid lo = mid + 1; } } // If found, increment // count by 1; if (found == true) { cnt++; } } } return cnt; } // Driver Code public static void Main(String[] args) { int N = 4, X = 10; // Given Matrix [,]arr int [,]arr = { { 2, 4, 3, 2, 10 }, { 3, 1, 1, 1, 5 }, { 1, 1, 2, 1, 4 }, { 2, 1, 1, 1, 3 } }; // Function call Console.Write(countSubsquare(arr, N, X) + "\n"); }} // This code is contributed by amal kumar choubey |
Javascript
<script>// Javascript program for the above approach // Size of a column var m = 5; // Function to find the count of submatrix // whose sum is X function countSubsquare(arr , n , X) { var dp = Array(n + 1); for(var i =0;i<n+1;i++) dp[i] = Array(m + 1).fill(0); // Copying arr to dp and making // it indexed 1 for (i = 0; i < n; i++) { for (j = 0; j < m; j++) { dp[i + 1][j + 1] = arr[i][j]; } } // Precalculate and store the sum // of all rectangles with upper // left corner at (0, 0); for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { // Calculating sum in // a 2d grid dp[i][j] += dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1]; } } // Stores the answer var cnt = 0; for (i = 1; i <= n; i++) { for (j = 1; j <= m; j++) { // Fix upper left corner // at {i, j} and perform // binary search on all // such possible squares // Minimum length of square var lo = 1; // Maximum length of square var hi = Math.min(n - i, m - j) + 1; // Flag to set if sub-square // with sum X is found var found = false; while (lo <= hi) { var mid = parseInt((lo + hi) / 2); // Calculate lower // right index if upper // right corner is at {i, j} var ni = i + mid - 1; var nj = j + mid - 1; // Calculate the sum of // elements in the submatrix // with upper left column // {i, j} and lower right // column at {ni, nj]; var sum = dp[ni][nj] - dp[ni][j - 1] - dp[i - 1][nj] + dp[i - 1][j - 1]; if (sum >= X) { // If sum X is found if (sum == X) { found = true; } hi = mid - 1; // If sum > X, then size of // the square with sum X // must be less than mid } else { // If sum < X, then size of // the square with sum X // must be greater than mid lo = mid + 1; } } // If found, increment // count by 1; if (found == true) { cnt++; } } } return cnt; } // Driver Code var N = 4, X = 10; // Given Matrix arr var arr = [ [ 2, 4, 3, 2, 10 ], [ 3, 1, 1, 1, 5 ], [ 1, 1, 2, 1, 4 ], [ 2, 1, 1, 1, 3 ] ]; // Function Call document.write(countSubsquare(arr, N, X) + "<br/>");// This code contributed by umadevi9616 </script> |
Output
3
Time Complexity: O(N * M * log(max(N, M)))
Auxiliary Space: O(N * M) since n*m space is being used for populating the 2-d array dp.
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!
