Given a N x M matrix where N is the number of rows and M is the number of columns in the given matrix and an integer K. The task is to find the maximum length of a square submatrix having the sum of elements less than or equal to K or print 0 if no such square exits.
Examples:
Input: r = 4, c = 4 , k = 6
matrix[][] = { {1, 1, 1, 1},
{1, 0, 0, 0},
{1, 0, 0, 0},
{1, 0, 0, 0},
}
Output: 3
Explanation:
Square from (0,0) to (2,2) with
sum 5 is one of the valid answer.
Input: r = 4, c = 4 , k = 1
matrix[][] = { {2, 2, 2},
{2, 2, 2},
{2, 2, 2},
{2, 2, 2},
}
Output: 0
Explanation:
There is no valid answer.
Approach:
The idea is to calculate the prefix sum matrix. Once the prefix sum matrix is calculated, the required sub-matrix sum can be calculated in O(1) time complexity. Use the sliding window technique to calculate the maximum length square submatrix. For every square of length cur_max+1, where cur_max is the currently found maximum length of a square submatrix, we check whether the sum of elements in the current submatrix, having the length of cur_max+1, is less than or equal to K or not. If yes, then increase the result by 1, otherwise, we continue to check.
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <iostream>using namespace std; // Function to return maximum // length of square submatrix // having sum of elements at-most K int maxLengthSquare(int row, int column, int arr[][4], int k) { // Matrix to store prefix sum int sum[row + 1][column + 1] ; for(int i = 1; i <= row; i++) for(int j = 0; j <= column; j++) sum[i][j] = 0; // Current maximum length int cur_max = 1; // Variable for storing // maximum length of square int max = 0; for (int i = 1; i <= row; i++) { for (int j = 1; j <= column; j++) { // Calculating prefix sum sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + arr[i - 1][j - 1] - sum[i - 1][j - 1]; // Checking whether there // exits square with length // cur_max+1 or not if(i >= cur_max && j >= cur_max && sum[i][j] - sum[i - cur_max][j] - sum[i][j - cur_max] + sum[i - cur_max][j - cur_max] <= k) { max = cur_max++; } } } // Returning the // maximum length return max; } // Driver code int main() { int row = 4, column = 4; int matrix[4][4] = { {1, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0} }; int k = 6; int ans = maxLengthSquare(row, column, matrix, k); cout << ans; return 0; }// This code is contributed by AnkitRai01 |
Java
// Java implementation of // the above approachimport java.util.*;class GFG{ // Function to return maximum // length of square submatrix // having sum of elements at-most K public static int maxLengthSquare(int row,int column, int[][] arr, int k) { // Matrix to store prefix sum int sum[][] = new int[row + 1][column + 1]; // Current maximum length int cur_max = 1; // Variable for storing // maximum length of square int max = 0; for (int i = 1; i <= row; i++) { for (int j = 1; j <= column; j++) { // Calculating prefix sum sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + arr[i - 1][j - 1] - sum[i - 1][j - 1]; // Checking whether there // exits square with length // cur_max+1 or not if(i >=cur_max&&j>=cur_max&&sum[i][j]-sum[i - cur_max][j] - sum[i][j - cur_max] + sum[i - cur_max][j - cur_max] <= k){ max = cur_max++; } } } // Returning the // maximum length return max; } // Driver code public static void main(String args[]) { int row = 4 , column = 4; int matrix[][] = { {1, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0} }; int k = 6; int ans = maxLengthSquare(row,column,matrix, k); System.out.println(ans); }} |
Python3
# Python3 implementation of the above approach import numpy as np# Function to return maximum # length of square submatrix # having sum of elements at-most K def maxLengthSquare(row, column, arr, k) : # Matrix to store prefix sum sum = np.zeros((row + 1, column + 1)); # Current maximum length cur_max = 1; # Variable for storing # maximum length of square max = 0; for i in range(1, row + 1) : for j in range(1, column + 1) : # Calculating prefix sum sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + \ arr[i - 1][j - 1] - \ sum[i - 1][j - 1]; # Checking whether there # exits square with length # cur_max+1 or not if(i >= cur_max and j >= cur_max and sum[i][j] - sum[i - cur_max][j] - sum[i][j - cur_max] + sum[i - cur_max][j - cur_max] <= k) : max = cur_max; cur_max += 1; # Returning the maximum length return max; # Driver code if __name__ == "__main__" : row = 4 ; column = 4; matrix = [[1, 1, 1, 1], [1, 0, 0, 0], [1, 0, 0, 0], [1, 0, 0, 0]]; k = 6; ans = maxLengthSquare(row, column, matrix, k); print(ans); # This code is contributed by AnkitRai01 |
C#
// C# implementation of the above approach using System;class GFG { // Function to return maximum // length of square submatrix // having sum of elements at-most K public static int maxLengthSquare(int row,int column, int[,] arr, int k) { // Matrix to store prefix sum int [,]sum = new int[row + 1,column + 1]; // Current maximum length int cur_max = 1; // Variable for storing // maximum length of square int max = 0; for (int i = 1; i <= row; i++) { for (int j = 1; j <= column; j++) { // Calculating prefix sum sum[i, j] = sum[i - 1, j] + sum[i, j - 1] + arr[i - 1, j - 1] - sum[i - 1, j - 1]; // Checking whether there // exits square with length // cur_max+1 or not if(i >=cur_max && j>=cur_max && sum[i, j]-sum[i - cur_max, j] - sum[i, j - cur_max] + sum[i - cur_max, j - cur_max] <= k) { max = cur_max++; } } } // Returning the // maximum length return max; } // Driver code public static void Main() { int row = 4 , column = 4; int [,]matrix = { {1, 1, 1, 1}, {1, 0, 0, 0}, {1, 0, 0, 0}, {1, 0, 0, 0} }; int k = 6; int ans = maxLengthSquare(row, column, matrix, k); Console.WriteLine(ans); } } // This code is contributed by AnkitRai01 |
Javascript
<script>// Javascript implementation of the above approach// Function to return maximum// length of square submatrix// having sum of elements at-most Kfunction maxLengthSquare(row, column, arr, k) { // Matrix to store prefix sum let sum = new Array();[row + 1][column + 1]; for (let i = 0; i < row + 1; i++) { let temp = new Array(); for (let j = 0; j < column + 1; j++) { temp.push([]) } sum.push(temp) } for (let i = 1; i <= row; i++) for (let j = 0; j <= column; j++) sum[i][j] = 0; // Current maximum length let cur_max = 1; // Variable for storing // maximum length of square let max = 0; for (let i = 1; i <= row; i++) { for (let j = 1; j <= column; j++) { // Calculating prefix sum sum[i][j] = sum[i - 1][j] + sum[i][j - 1] + arr[i - 1][j - 1] - sum[i - 1][j - 1]; // Checking whether there // exits square with length // cur_max+1 or not if (i >= cur_max && j >= cur_max && sum[i][j] - sum[i - cur_max][j] - sum[i][j - cur_max] + sum[i - cur_max][j - cur_max] <= k) { max = cur_max++; } } } // Returning the // maximum length return max;}// Driver codelet row = 4, column = 4;let matrix = [[1, 1, 1, 1],[1, 0, 0, 0],[1, 0, 0, 0],[1, 0, 0, 0]];let k = 6;let ans = maxLengthSquare(row, column, matrix, k);document.write(ans);// This code is contributed by gfgking</script> |
Output:
3
Time Complexity: O(N x M)
Auxiliary Space: O(N x M), where N and M are the given rows and columns of the 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!
