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 codeÂ
let 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!
