Find Maximum Length Of A Square Submatrix Having Sum Of Elements At-Most K

0 0 6 minutes read

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 approach
import 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 K
function 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:

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 zambiatek!