Largest Square in a Binary Matrix with at most K 1s for multiple Queries

Given a binary matrix M where each element of the matrix will be 0 or 1, the task is to find the largest square that can be formed with center (i, j) and contains most K 1’s.

Input: M[][] = {
{1, 0, 1, 0, 0}
{1, 0, 1, 1, 1}
{1, 1, 1, 1, 1}
{1, 0, 0, 1, 0}},
i = 1, j = 2, K = 9
Output: 3
Explanation:
Maximum length square with center at (1, 2)
that can be formed is of 3 length from (0, 1) to (2, 3)

Input: M[][] = {
{ 1, 1, 1 },
{ 1, 1, 1 },
{ 1, 1, 1 }},
i = 1, j = 1, K = 9
Output: 3

Naive Approach:

For each query, consider all squares with center (i, j) and keep incrementing the length of the squares from 1 to its maximum possible value up to which the count of 1s in the square is less than K. The maximum possible value of the length of the square will be 2*MIN_DIST + 1 where MIN_DIST is the minimum distance of the center from the edges of the matrix. So for an R*C matrix with center (i, j),

MIN_DIST = min( i, j, R-i-1, C-j-1 )

Below is the implementation of the above approach:

C++

// C++ implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
 
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
 
// Function to calculate the
// largest square with atmost K
// 1s for Q queries
void largestSquare(int matrix[][MAX],
             int R, int C, int q_i[],
            int q_j[], int K, int Q){
                 
    // Loop to solve for each query
    for (int q = 0; q < Q; q++) {
        int i = q_i[q];
        int j = q_j[q];
        int min_dist = min(min(i, j),
          min(R - i - 1, C - j - 1));
        int ans = -1;
        for (int k = 0; k <= min_dist;
                                 k++) {
            int count = 0;
            // Traversing the each sub
            // square and counting total
            for (int row = i - k; 
              row <= i + k; row++)
                for (int col = j - k;
                  col <= j + k; col++)
                    count += matrix[row][col];
             
            // Breaks when exceeds
            // the maximum count
            if (count > K)
                break;
             
            ans = 2 * k + 1;
        }
        cout << ans << "\n";
    }
}
 
// Driver Code
int main()
{
    int matrix[][MAX] = { { 1, 0, 1, 0, 0 },
                        { 1, 0, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 },
                        { 1, 0, 0, 1, 0 } };
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
    largestSquare(matrix, 4, 5, q_i,
                          q_j, K, Q);
    return 0;
}

Java

// Java implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
class GFG{
     
static int MAX = 100;
 
// Function to calculate the
// largest square with atmost K
// 1s for Q queries
static void largestSquare(int matrix[][], 
                          int R, int C, 
                          int q_i[], int q_j[], 
                          int K, int Q)
{
     
    // Loop to solve for each query
    for(int q = 0; q < Q; q++) 
    {
       int i = q_i[q];
       int j = q_j[q];
       int min_dist = Math.min(Math.min(i, j),
                      Math.min(R - i - 1, 
                               C - j - 1));
       int ans = -1;
       for(int k = 0; k <= min_dist; k++)
       {
          int count = 0;
           
          // Traversing the each sub
          // square and counting total
          for(int row = i - k; row <= i + k; row++)
             for(int col = j - k; col <= j + k; col++)
                count += matrix[row][col];
             
            // Breaks when exceeds
            // the maximum count
            if (count > K)
                break;
             
            ans = 2 * k + 1;
        }
         
        System.out.print(ans + "\n");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int matrix[][] = { { 1, 0, 1, 0, 0 },
                       { 1, 0, 1, 1, 1 },
                       { 1, 1, 1, 1, 1 },
                       { 1, 0, 0, 1, 0 } };
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
    largestSquare(matrix, 4, 5, q_i, q_j, K, Q);
}
}
 
// This code is contributed by Amit Katiyar

Python3

# Python3 implementation to find the 
# largest square in the matrix such 
# that it contains at most K 1's 
 
MAX = 100
 
# Function to calculate the 
# largest square with atmost K 
# 1s for Q queries 
def largestSquare(matrix, R, C, q_i, q_j, K, Q): 
                 
    # Loop to solve for each query 
    for q in range(Q): 
        i = q_i[q] 
        j = q_j[q] 
        min_dist = min(min(i, j), 
                   min(R - i - 1, C - j - 1)) 
        ans = -1
        for k in range(min_dist + 1):
             
            count = 0
             
            # Traversing the each sub 
            # square and counting total 
            for row in range(i - k, i + k + 1): 
                for col in range(j - k, j + k + 1): 
                    count += matrix[row][col] 
             
            # Breaks when exceeds 
            # the maximum count 
            if count > K: 
                break
             
            ans = 2 * k + 1
        print(ans) 
         
# Driver Code 
matrix = [ [ 1, 0, 1, 0, 0 ], 
           [ 1, 0, 1, 1, 1 ], 
           [ 1, 1, 1, 1, 1 ], 
           [ 1, 0, 0, 1, 0 ] ] 
K = 9
Q = 1
q_i = [ 1 ] 
q_j = [ 2 ] 
largestSquare(matrix, 4, 5, q_i, q_j, K, Q)
                         
# This code is contributed by divyamohan123                     
                    

C#

// C# implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
using System;
 
class GFG{
     
//static int MAX = 100;
 
// Function to calculate the
// largest square with atmost K
// 1s for Q queries
static void largestSquare(int [,]matrix, 
                          int R, int C, 
                          int []q_i, int []q_j, 
                          int K, int Q)
{
     
    // Loop to solve for each query
    for(int q = 0; q < Q; q++) 
    {
       int i = q_i[q];
       int j = q_j[q];
       int min_dist = Math.Min(Math.Min(i, j), 
                               Math.Min(R - i - 1,
                                        C - j - 1));
       int ans = -1;
       for(int k = 0; k <= min_dist; k++)
       {
          int count = 0;
           
          // Traversing the each sub
          // square and counting total
          for(int row = i - k; row <= i + k; row++)
             for(int col = j - k; col <= j + k; col++)
                count += matrix[row, col];
                 
          // Breaks when exceeds
          // the maximum count
          if (count > K)
              break;
           
          ans = 2 * k + 1;
       }
       Console.Write(ans + "\n");
    }
}
 
// Driver Code
public static void Main(String[] args)
{
    int [,]matrix = { { 1, 0, 1, 0, 0 },
                      { 1, 0, 1, 1, 1 },
                      { 1, 1, 1, 1, 1 },
                      { 1, 0, 0, 1, 0 } };
    int K = 9, Q = 1;
    int []q_i = {1};
    int []q_j = {2};
     
    largestSquare(matrix, 4, 5, q_i, q_j, K, Q);
}
}
 
// This code is contributed by Amit Katiyar

Javascript

<script>
 
// Javascript implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
 
var MAX = 100;
 
// Function to calculate the
// largest square with atmost K
// 1s for Q queries
function largestSquare( matrix,
             R, C, q_i, q_j, K, Q){
                 
    // Loop to solve for each query
    for (var q = 0; q < Q; q++) {
        var i = q_i[q];
        var j = q_j[q];
        var min_dist = Math.min(Math.min(i, j),
          Math.min(R - i - 1, C - j - 1));
        var ans = -1;
        for (var k = 0; k <= min_dist;
                                 k++) {
            var count = 0;
            // Traversing the each sub
            // square and counting total
            for (var row = i - k; 
              row <= i + k; row++)
                for (var col = j - k;
                  col <= j + k; col++)
                    count += matrix[row][col];
             
            // Breaks when exceeds
            // the maximum count
            if (count > K)
                break;
             
            ans = 2 * k + 1;
        }
        document.write( ans + "<br>");
    }
}
 
// Driver Code
var matrix = [ [ 1, 0, 1, 0, 0 ],
                    [ 1, 0, 1, 1, 1 ],
                    [ 1, 1, 1, 1, 1 ],
                    [ 1, 0, 0, 1, 0 ] ];
var K = 9, Q = 1;
var q_i = [1 ];
var q_j = [2 ];
largestSquare(matrix, 4, 5, q_i,
                      q_j, K, Q);
 
// This code is contributed by famously.
</script>

Output

The worst-case time complexity for the given solution is O(Q*N*N*MIN_DIST) where N is the length of the square(which is maximum 2*MIN_DIST + 1).

Efficient Approach using Dynamic Programming:

The idea is to use Dynamic Programming to count the number of 1s in each square and then increment the length by 1 until the limit and then finally check the count of the 1s is less than the K or not. If yes, then update the answer.
To compute the number of 1s in a submatrix from (x1, y1) to (x2, y2) using:

Number of 1's = sumDP[x2][y2] - sumDP[x2][y1-1] -
                sumDP[x1-1][y2] + sumDP[x1-1][y1-1]

Below is the implementation of the above approach:

C++

// C++ implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
 
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
 
// Function to find the 
// largest square in the matrix such
// that it contains atmost K 1's
void largestSquare(int matrix[][MAX],
            int R, int C, int q_i[],
            int q_j[], int K, int Q){
     
    int countDP[R][C];
    memset(countDP, 0, sizeof(countDP));
 
    // Precomputing the countDP 
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
    for (int i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] + 
                             matrix[i][0];
    for (int j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                             matrix[0][j];
    for (int i = 1; i < R; i++)
        for (int j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                       countDP[i - 1][j] +
                       countDP[i][j - 1] -
                       countDP[i - 1][j - 1];
     
    // Loop to solve Queries
    for (int q = 0; q < Q; q++) {
        int i = q_i[q];
        int j = q_j[q];
        // Calculating the maximum
        // possible distance of the
        // centre from edge
        int min_dist = min(min(i, j), 
          min(R - i - 1, C - j - 1));
        int ans = -1;
        for (int k = 0; k <= min_dist;
                                  k++) {
            int x1 = i - k, x2 = i + k;
            int y1 = j - k, y2 = j + k;
             
            // Calculating the number
            // of 1s in the submatrix
            int count = countDP[x2][y2];
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
 
            if (count > K)
                break;
            ans = 2 * k + 1;
        }
        cout << ans << "\n";
    }
}
 
// Driver Code
int main()
{
    int matrix[][MAX] = { { 1, 0, 1, 0, 0 },
                        { 1, 0, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 },
                        { 1, 0, 0, 1, 0 } };
 
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
    largestSquare(matrix, 4, 5, q_i,
                          q_j, K, Q);
    return 0;
}

Java

// Java implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
import java.util.*;
 
class GFG{
     
static int MAX = 100;
 
// Function to find the 
// largest square in the matrix such
// that it contains atmost K 1's
static void largestSquare(int matrix[][], int R,
                          int C, int q_i[], 
                          int q_j[], int K,
                          int Q)
{
    int [][]countDP = new int[R][C];
 
    // Precomputing the countDP 
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
    for(int i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] + 
                             matrix[i][0];
    for(int j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                         matrix[0][j];
    for(int i = 1; i < R; i++)
        for(int j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                           countDP[i - 1][j] +
                           countDP[i][j - 1] -
                           countDP[i - 1][j - 1];
     
    // Loop to solve Queries
    for(int q = 0; q < Q; q++)
    {
        int i = q_i[q];
        int j = q_j[q];
         
        // Calculating the maximum
        // possible distance of the
        // centre from edge
        int min_dist = Math.min(Math.min(i, j), 
                       Math.min(R - i - 1, 
                                C - j - 1));
                                 
        int ans = -1;
        for(int k = 0; k <= min_dist; k++)
        {
            int x1 = i - k, x2 = i + k;
            int y1 = j - k, y2 = j + k;
             
            // Calculating the number
            // of 1s in the submatrix
            int count = countDP[x2][y2];
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
            if (count > K)
                break;
            ans = 2 * k + 1;
        }
        System.out.print(ans + "\n");
    }
}
 
// Driver Code
public static void main(String[] args)
{
    int matrix[][] = { { 1, 0, 1, 0, 0 },
                       { 1, 0, 1, 1, 1 },
                       { 1, 1, 1, 1, 1 },
                       { 1, 0, 0, 1, 0 } };
 
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
     
    largestSquare(matrix, 4, 5, q_i,
                        q_j, K, Q);
}
}
 
// This code is contributed by gauravrajput1

Python3

# Python3 implementation to find the 
# largest square in the matrix such 
# that it contains atmost K 1's 
 
# Function to find the largest 
# square in the matrix such 
# that it contains atmost K 1's 
def largestSquare(matrix, R, C, q_i, 
                     q_j, K, Q):
     
    countDP = [[0 for x in range(C)]
                  for x in range(R)] 
     
    # Precomputing the countDP 
    # prefix sum of the matrix 
    countDP[0][0] = matrix[0][0] 
     
    for i in range(1, R):
        countDP[i][0] = (countDP[i - 1][0] +
                          matrix[i][0])
     
    for j in range(1, C):
        countDP[0][j] = (countDP[0][j - 1] +
                          matrix[0][j])
     
    for i in range(1, R):
        for j in range(1, C):
            countDP[i][j] = (matrix[i][j] +
                            countDP[i - 1][j] +
                            countDP[i][j - 1] -
                            countDP[i - 1][j - 1])
     
    # Loop to solve Queries 
    for q in range(0, Q):
        i = q_i[q]
        j = q_j[q]
         
        # Calculating the maximum 
        # possible distance of the 
        # centre from edge 
        min_dist = min(i, j, R - i - 1,
                             C - j - 1)
        ans = -1
        for k in range(0, min_dist + 1): 
            x1 = i - k
            x2 = i + k
            y1 = j - k
            y2 = j + k 
                 
            # Calculating the number 
            # of 1s in the submatrix 
            count = countDP[x2][y2]; 
             
            if (x1 > 0): 
                    count -= countDP[x1 - 1][y2]
            if (y1 > 0):
                    count -= countDP[x2][y1 - 1]
            if (x1 > 0 and y1 > 0):
                    count += countDP[x1 - 1][y1 - 1]
                 
            if (count > K):
                    break
                     
            ans = 2 * k + 1
             
        print(ans)
         
# Driver Code 
matrix = [ [ 1, 0, 1, 0, 0 ], 
           [ 1, 0, 1, 1, 1 ], 
           [ 1, 1, 1, 1, 1 ], 
           [ 1, 0, 0, 1, 0 ] ] 
K = 9
Q = 1
q_i = [1] 
q_j = [2] 
 
largestSquare(matrix, 4, 5, q_i, q_j, K, Q) 
 
# This code is contributed by Stream_Cipher

C#

// C# implementation to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
using System;
 
class GFG{ 
     
//static int MAX = 100; 
 
// Function to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
static void largestSquare(int [,]matrix, int R, 
                          int C, int []q_i, 
                          int []q_j, int K, 
                          int Q) 
{ 
    int [,]countDP = new int[R, C]; 
 
    // Precomputing the countDP 
    // prefix sum of the matrix 
    countDP[0, 0] = matrix[0, 0]; 
    for(int i = 1; i < R; i++) 
        countDP[i, 0] = countDP[i - 1, 0] + 
                             matrix[i, 0];
                              
    for(int j = 1; j < C; j++) 
        countDP[0, j] = countDP[0, j - 1] + 
                         matrix[0, j]; 
                          
    for(int i = 1; i < R; i++) 
        for(int j = 1; j < C; j++) 
            countDP[i, j] = matrix[i, j] + 
                           countDP[i - 1, j] + 
                           countDP[i, j - 1] - 
                           countDP[i - 1, j - 1]; 
     
    // Loop to solve Queries 
    for(int q = 0; q < Q; q++) 
    { 
        int i = q_i[q]; 
        int j = q_j[q]; 
         
        // Calculating the maximum 
        // possible distance of the 
        // centre from edge 
        int min_dist = Math.Min(Math.Min(i, j), 
                       Math.Min(R - i - 1, 
                                C - j - 1)); 
                                 
        int ans = -1; 
        for(int k = 0; k <= min_dist; k++) 
        { 
            int x1 = i - k, x2 = i + k; 
            int y1 = j - k, y2 = j + k; 
             
            // Calculating the number 
            // of 1s in the submatrix 
            int count = countDP[x2, y2]; 
            if (x1 > 0) 
                count -= countDP[x1 - 1, y2]; 
            if (y1 > 0) 
                count -= countDP[x2, y1 - 1]; 
            if (x1 > 0 && y1 > 0) 
                count += countDP[x1 - 1, y1 - 1]; 
            if (count > K) 
                break; 
 
            ans = 2 * k + 1; 
        } 
        Console.Write(ans + "\n"); 
    } 
} 
 
// Driver Code 
public static void Main(String[] args) 
{ 
    int [,]matrix = { { 1, 0, 1, 0, 0 }, 
                      { 1, 0, 1, 1, 1 }, 
                      { 1, 1, 1, 1, 1 }, 
                      { 1, 0, 0, 1, 0 } }; 
 
    int K = 9, Q = 1; 
    int []q_i = { 1 }; 
    int []q_j = { 2 }; 
     
    largestSquare(matrix, 4, 5, q_i, 
                  q_j, K, Q); 
} 
}
 
// This code is contributed by princi singh

Javascript

<script>
 
// Javascript implementation to find the
// largest square in the matrix such
// that it contains atmost K 1's
let MAX = 100;
 
// Function to find the
// largest square in the matrix such
// that it contains atmost K 1's
function largestSquare(matrix, R, C, q_i, q_j, K, Q)
{
    let countDP = new Array(R);
    for(let i = 0; i < R; i++)
    {
        countDP[i] = new Array(C);
        for(let j = 0; j < C; j++)
            countDP[i][j] = 0;
    }
  
    // Precomputing the countDP
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
    for(let i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] +
                             matrix[i][0];
    for(let j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                         matrix[0][j];
    for(let i = 1; i < R; i++)
        for(let j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                           countDP[i - 1][j] +
                           countDP[i][j - 1] -
                           countDP[i - 1][j - 1];
      
    // Loop to solve Queries
    for(let q = 0; q < Q; q++)
    {
        let i = q_i[q];
        let j = q_j[q];
          
        // Calculating the maximum
        // possible distance of the
        // centre from edge
        let min_dist = Math.min(Math.min(i, j),
                       Math.min(R - i - 1,
                                C - j - 1));
                                  
        let ans = -1;
        for(let k = 0; k <= min_dist; k++)
        {
            let x1 = i - k, x2 = i + k;
            let y1 = j - k, y2 = j + k;
              
            // Calculating the number
            // of 1s in the submatrix
            let count = countDP[x2][y2];
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
            if (count > K)
                break;
            ans = 2 * k + 1;
        }
        document.write(ans + "<br>");
    }
}
 
// Driver Code
let matrix = [ [ 1, 0, 1, 0, 0 ],
               [ 1, 0, 1, 1, 1 ],
               [ 1, 1, 1, 1, 1 ],
               [ 1, 0, 0, 1, 0 ] ];
let  K = 9, Q = 1;
let q_i = [1];
let q_j = [2];
 
largestSquare(matrix, 4, 5, q_i,
              q_j, K, Q);
 
// This code is contributed by unknown2108
 
</script>

Output

The worst-case time complexity for the given solution is O(R*C + Q*MIN_DIST) where R, C is the dimensions of the initial matrix.

Efficient Approach using Dynamic Programming and Binary Search:

The idea is to use a Binary search to find the largest square instead of incrementing the length of a side iteratively and converge towards the side which gives at most K 1’s.
The search space for the binary search will be-

// Minimum possible answer will be
// the square with side 0
l = 0

// Maximum possible will be to include
// the whole square possible from (i, j)
r = min(min(i, j), 
        min(R - i - 1, C - i - 1))

Below is the implementation of the above approach:

C++

// C++ implementation to find the 
// largest square in the matrix such
// that it contains atmost K 1's
 
#include <bits/stdc++.h>
using namespace std;
const int MAX = 100;
 
// Function to find the 
// largest square in the matrix such
// that it contains atmost K 1's
void largestSquare(int matrix[][MAX], 
            int R, int C, int q_i[],
            int q_j[], int K, int Q){
     
    int countDP[R][C];
    memset(countDP, 0, sizeof(countDP));
 
    // Precomputation of the countDP
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
    for (int i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] +
                             matrix[i][0];
    for (int j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                             matrix[0][j];
    for (int i = 1; i < R; i++)
        for (int j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                       countDP[i - 1][j] +
                       countDP[i][j - 1] -
                   countDP[i - 1][j - 1];
     
    // Loop to solve each query
    for (int q = 0; q < Q; q++) {
        int i = q_i[q];
        int j = q_j[q];
        int min_dist = min(min(i, j),
          min(R - i - 1, C - j - 1));
        int ans = -1, l = 0, u = min_dist;
         
        // Binary Search to the side which
        // have atmost in K 1's in square
        while (l <= u) {
            int mid = (l + u) / 2;
            int x1 = i - mid, x2 = i + mid;
            int y1 = j - mid, y2 = j + mid;
            // Count total number of 1s in
            // the sub square considered
            int count = countDP[x2][y2];
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
             
            // If the count is less than or
            // equals to the maximum move
            // to right half
            if (count <= K) {
                ans = 2 * mid + 1;
                l = mid + 1;
            }
            else
                u = mid - 1;
        }
        cout << ans << "\n";
    }
}
 
int main()
{
    int matrix[][MAX] = { { 1, 0, 1, 0, 0 },
                        { 1, 0, 1, 1, 1 },
                        { 1, 1, 1, 1, 1 },
                        { 1, 0, 0, 1, 0 } };
 
    int K = 9, Q = 1;
    int q_i[] = { 1 };
    int q_j[] = { 2 };
    largestSquare(matrix, 4, 5,
                q_i, q_j, K, Q);
    return 0;
}

Java

// Java implementation to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
import java.util.*; 
 
class GFG{
 
// Function to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
static void largestSquare(int matrix[][], int R,
                          int C, int q_i[], 
                          int q_j[], int K, int Q)
{ 
    int countDP[][] = new int[R][C]; 
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            countDP[i][j] = 0; 
 
    // Precomputation of the countDP 
    // prefix sum of the matrix 
    countDP[0][0] = matrix[0][0]; 
     
    for(int i = 1; i < R; i++) 
        countDP[i][0] = countDP[i - 1][0] + 
                             matrix[i][0]; 
     
    for(int j = 1; j < C; j++) 
        countDP[0][j] = countDP[0][j - 1] + 
                         matrix[0][j]; 
     
    for(int i = 1; i < R; i++) 
        for(int j = 1; j < C; j++) 
            countDP[i][j] = matrix[i][j] + 
                           countDP[i - 1][j] + 
                           countDP[i][j - 1] - 
                           countDP[i - 1][j - 1]; 
     
    // Loop to solve each query 
    for(int q = 0; q < Q; q++)
    { 
        int i = q_i[q]; 
        int j = q_j[q]; 
         
        int min_dist = Math.min(Math.min(i, j), 
                                Math.min(R - i - 1,
                                         C - j - 1)); 
                                          
        int ans = -1, l = 0, u = min_dist; 
         
        // Binary Search to the side which 
        // have atmost in K 1's in square 
        while (l <= u)
        { 
            int mid = (l + u) / 2; 
            int x1 = i - mid, x2 = i + mid; 
            int y1 = j - mid, y2 = j + mid; 
             
            // Count total number of 1s in 
            // the sub square considered 
            int count = countDP[x2][y2]; 
             
            if (x1 > 0) 
                count -= countDP[x1 - 1][y2]; 
            if (y1 > 0) 
                count -= countDP[x2][y1 - 1]; 
            if (x1 > 0 && y1 > 0) 
                count += countDP[x1 - 1][y1 - 1]; 
             
            // If the count is less than or 
            // equals to the maximum move 
            // to right half 
            if (count <= K) 
            { 
                ans = 2 * mid + 1; 
                l = mid + 1; 
            } 
            else
                u = mid - 1; 
        } 
        System.out.println(ans); 
    } 
} 
 
// Driver code
public static void main(String args[]) 
{ 
    int matrix[][] = { { 1, 0, 1, 0, 0 }, 
                       { 1, 0, 1, 1, 1 }, 
                       { 1, 1, 1, 1, 1 }, 
                       { 1, 0, 0, 1, 0 } }; 
 
    int K = 9, Q = 1; 
    int q_i[] = {1}; 
    int q_j[] = {2}; 
     
    largestSquare(matrix, 4, 5, q_i, q_j, K, Q); 
} 
}
 
// This code is contributed by Stream_Cipher

Python3

# Python3 implementation to find the 
# largest square in the matrix such 
# that it contains atmost K 1's 
 
# Function to find the 
# largest square in the matrix such 
# that it contains atmost K 1's 
def largestSquare(matrix, R, C, q_i, 
                     q_j, K, Q):
                          
    countDP = [[0 for x in range(C)]
                  for x in range(R)] 
     
    # Precomputing the countDP 
    # prefix sum of the matrix 
    countDP[0][0] = matrix[0][0] 
     
    for i in range(1, R):
        countDP[i][0] = (countDP[i - 1][0] +
                              matrix[i][0])
    for j in range(1, C):
        countDP[0][j] = (countDP[0][j - 1] +
                          matrix[0][j])
    for i in range(1, R):
        for j in range(1, C):
            countDP[i][j] = (matrix[i][j] +
                            countDP[i - 1][j] +
                            countDP[i][j - 1] -
                            countDP[i - 1][j - 1])
     
    # Loop to solve Queries 
    for q in range(0,Q):
        i = q_i[q]
        j = q_j[q]
         
        # Calculating the maximum 
        # possible distance of the 
        # centre from edge 
        min_dist = min(i, j, R - i - 1, 
                             C - j - 1)
        ans = -1
        l = 0
        u = min_dist
         
        while (l <= u):
            mid = int((l + u) / 2) 
            x1 = i - mid
            x2 = i + mid 
            y1 = j - mid
            y2 = j + mid 
             
        # Count total number of 1s in 
        # the sub square considered 
            count = countDP[x2][y2]
             
            if (x1 > 0):
                    count -= countDP[x1 - 1][y2] 
            if (y1 > 0):
                    count -= countDP[x2][y1 - 1]
            if (x1 > 0 and y1 > 0): 
                    count += countDP[x1 - 1][y1 - 1]
             
        # If the count is less than or 
        # equals to the maximum move 
        # to right half 
            if (count <= K): 
                    ans = 2 * mid + 1
                    l = mid + 1
            else:
                u = mid - 1
                 
        print(ans)
         
# Driver Code 
matrix = [ [ 1, 0, 1, 0, 0 ], 
           [ 1, 0, 1, 1, 1 ], 
           [ 1, 1, 1, 1, 1 ], 
           [ 1, 0, 0, 1, 0 ] ] 
K = 9
Q = 1
q_i = [1] 
q_j = [2] 
 
largestSquare(matrix, 4, 5, q_i, q_j, K, Q) 
 
# This code is contributed by Stream_Cipher

C#

// C# implementation to find the 
// largest square in the matrix such 
// that it contains atmost K 1's 
using System.Collections.Generic; 
using System;
 
class GFG{
 
// Function to find the largest 
// square in the matrix such 
// that it contains atmost K 1's 
static void largestSquare(int [,]matrix, int R,
                          int C, int []q_i, 
                          int []q_j, int K, int Q)
{ 
    int [,]countDP = new int[R, C]; 
    for(int i = 0; i < R; i++)
        for(int j = 0; j < C; j++)
            countDP[i, j]=0; 
 
    // Precomputation of the countDP 
    // prefix sum of the matrix 
    countDP[0, 0] = matrix[0, 0]; 
    for(int i = 1; i < R; i++) 
        countDP[i, 0] = countDP[i - 1, 0] + 
                         matrix[i, 0]; 
                          
    for(int j = 1; j < C; j++) 
        countDP[0, j] = countDP[0, j - 1] + 
                         matrix[0, j]; 
                          
    for(int i = 1; i < R; i++) 
        for(int j = 1; j < C; j++) 
            countDP[i, j] = matrix[i, j] + 
                           countDP[i - 1, j] + 
                           countDP[i, j - 1] - 
                           countDP[i - 1, j - 1]; 
     
    // Loop to solve each query 
    for(int q = 0; q < Q; q++)
    { 
        int i = q_i[q]; 
        int j = q_j[q]; 
         
        int min_dist = Math.Min(Math.Min(i, j), 
                                Math.Min(R - i - 1,
                                         C - j - 1));
                                          
        int ans = -1, l = 0, u = min_dist; 
         
        // Binary Search to the side which 
        // have atmost in K 1's in square 
        while (l <= u) 
        { 
            int mid = (l + u) / 2; 
            int x1 = i - mid, x2 = i + mid; 
            int y1 = j - mid, y2 = j + mid; 
             
            // Count total number of 1s in 
            // the sub square considered 
            int count = countDP[x2, y2];
             
            if (x1 > 0) 
                count -= countDP[x1 - 1, y2]; 
            if (y1 > 0) 
                count -= countDP[x2, y1 - 1]; 
            if (x1 > 0 && y1 > 0) 
                count += countDP[x1 - 1, y1 - 1]; 
             
            // If the count is less than or 
            // equals to the maximum move 
            // to right half 
            if (count <= K) 
            { 
                ans = 2 * mid + 1; 
                l = mid + 1; 
            } 
            else
                u = mid - 1; 
        } 
        Console.WriteLine(ans); 
    } 
} 
 
// Driver code
public static void Main() 
{ 
    int [,]matrix = { { 1, 0, 1, 0, 0 }, 
                      { 1, 0, 1, 1, 1 }, 
                      { 1, 1, 1, 1, 1 }, 
                      { 1, 0, 0, 1, 0 } }; 
 
    int K = 9, Q = 1; 
    int []q_i = { 1 }; 
    int []q_j = { 2 }; 
     
    largestSquare(matrix, 4, 5, 
                     q_i, q_j, K, Q); 
} 
}
 
// This code is contributed by Stream_Cipher

Javascript

<script>
// Javascript implementation to find the
// largest square in the matrix such
// that it contains atmost K 1's
 
// Function to find the
// largest square in the matrix such
// that it contains atmost K 1's
function largestSquare(matrix,R,C,q_i,q_j,K,Q)
{
    let countDP = new Array(R);
    for(let i = 0; i < R; i++)
    {
        countDP[i]=new Array(C);
        for(let j = 0; j < C; j++)
            countDP[i][j] = 0;
     }
    // Precomputation of the countDP
    // prefix sum of the matrix
    countDP[0][0] = matrix[0][0];
      
    for(let i = 1; i < R; i++)
        countDP[i][0] = countDP[i - 1][0] +
                             matrix[i][0];
      
    for(let j = 1; j < C; j++)
        countDP[0][j] = countDP[0][j - 1] +
                         matrix[0][j];
      
    for(let i = 1; i < R; i++)
        for(let j = 1; j < C; j++)
            countDP[i][j] = matrix[i][j] +
                           countDP[i - 1][j] +
                           countDP[i][j - 1] -
                           countDP[i - 1][j - 1];
      
    // Loop to solve each query
    for(let q = 0; q < Q; q++)
    {
        let i = q_i[q];
        let j = q_j[q];
          
        let min_dist = Math.min(Math.min(i, j),
                                Math.min(R - i - 1,
                                         C - j - 1));
                                           
        let ans = -1, l = 0, u = min_dist;
          
        // Binary Search to the side which
        // have atmost in K 1's in square
        while (l <= u)
        {
            let mid = Math.floor((l + u) / 2);
            let x1 = i - mid, x2 = i + mid;
            let y1 = j - mid, y2 = j + mid;
              
            // Count total number of 1s in
            // the sub square considered
            let count = countDP[x2][y2];
              
            if (x1 > 0)
                count -= countDP[x1 - 1][y2];
            if (y1 > 0)
                count -= countDP[x2][y1 - 1];
            if (x1 > 0 && y1 > 0)
                count += countDP[x1 - 1][y1 - 1];
              
            // If the count is less than or
            // equals to the maximum move
            // to right half
            if (count <= K)
            {
                ans = 2 * mid + 1;
                l = mid + 1;
            }
            else
                u = mid - 1;
        }
        document.write(ans+"<br>");
    }
}
 
// Driver code
let matrix=[[ 1, 0, 1, 0, 0 ],
                       [ 1, 0, 1, 1, 1 ],
                       [ 1, 1, 1, 1, 1 ],
                       [ 1, 0, 0, 1, 0 ]];
 
let K = 9, Q = 1;
let q_i = [1];
let q_j = [2];
 
largestSquare(matrix, 4, 5, q_i, q_j, K, Q);
 
 
// This code is contributed by patel2127
</script>

Output

Time Complexity: O( R*C + Q*log(MIN_DIST) )

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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!

Largest Square in a Binary Matrix with at most K 1s for multiple Queries

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

C++

Java

Python3

C#

Javascript

Working with Titles and Heading – Python docx Module

Creating a Receipt Calculator using Python

One Liner for Python if-elif-else Statements

LEAVE A REPLY Cancel reply

Most Popular

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

Interviewed With Kyle Smith – Founder and CEO of Escalated by Shauli Zacks

EDITOR PICKS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR POSTS

Android 16 QPR2 Beta 3 lands with a flurry of bug fixes

Google is working on dedicated ‘Bills’ and ‘Travel’ folders for Gmail

Mint Mobile’s big bet on 5G home internet might change everything

POPULAR CATEGORY

ABOUT US

FOLLOW US