Largest Square

PROBLEM STATEMENT

You are given a binary grid containing only 0s and 1s. You are also given an integer, ‘K’ and you are asked ‘Q’ queries. In each query, you are given the location of a cell. For each query, you need to find the largest square containing at most ‘K’ 1s and having its center as the cell given in the query.

Input Format:

The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the T test cases follow. 

The first line of each test case contains two space-separated integers, ‘N’ and ‘M’, where ‘N’ and ‘M’ denote the dimensions of the binary grid. Then ‘N’ lines follow.

Each of these ‘N’ lines contains ‘M’ space-separated integers denoting the elements of the ‘i-th’ row. Each of these integers is either a 0 or a 1.

The next line contains two space-separated integers, ‘K’ and ‘Q’, where ‘K’ denotes the maximum number of 1s that a square can have and ‘Q’ denotes the number of queries to be run. Now, ‘Q’ lines follow.

Each of these ‘Q’ lines contains two space-separated integers, ‘A’ and ‘B’, denoting that in this query, the required square must have the cell located at ‘A-th’ row and ‘B-th’ column as its center.

Output Format:

For each test case, print ‘Q’ space-separated integers, denoting the length of the largest required square in each query.

Output for each test case will be printed in a separate line.

Note:

You do not need to print anything. It has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N,M <= 500
1 <= Q <= 1000
1 <= K <= N*M

Where ‘T’ denotes the number of test cases and ‘N’ and ‘M’ denote the dimensions of the binary grid. ‘Q’ denotes the number of queries and ‘K’ is the maximum number of 1s that the required square can have.

Time Limit: 1 sec.

Approach 1

The approach is to simply try to solve each query independently. We will start at the given cell and count the number of 1s in it and one by one count the number of 1s in each square whose center is that cell. As soon as this count becomes greater than ‘K’ we stop and return the length of the previous square because the required square is allowed to have not more than ‘K’ 1s.

Steps:

Define a vector, say results, to store the result of each query. We will return this after solving the result of each query.
Store the value of grid.size() in a variable, say N.
Store the value of grid[0].size() in a variable, say M.
Run a loop from i=0 to i<queries.size, and do:
1. Declare a variable, say cntrY, and make it equal to queries[i][0]. Declare another variable, say cntrX, and make it equal to queries[i][1]. These two values are the location of the cell which should serve as the center of the possible squares.
2. Declare a variable, say nearestEdgeDist, to store the value of the distance of the nearest edge of the grid from the center cell. Formally, make nearestEdgeDist = min(cntrY, n - cntrY, cntrX, m - cntrX).
3. Define a variable, say sideLength, to store the length of the biggest square meeting all the required conditions.
4. Run a loop from len=0 to len<=nearestEdgeDist, and do:
  1. Initialize a variable, say oneCount, to store the count of 1s in the present square.
  2. Run a loop from row=cntrY-len to row<=cntrY+len and another loop from col=cntrX-len to col<=cntrX+len, and do:
    1. If grid[row][col] has a value 1, then increase the count of oneCount.
  3. If the value of oneCount is greater than K, then we break out of the loop because this square contains more 1s than K, and naturally, any square bigger than this square will contain more 1s than K.
  4. If the count of 1s is not more than K, then that means that square is the largest possible square so far and we make sideLength = 2 * len +1.
5. Once, we have considered all possible squares, we have our answer for this query in the variable, sideLength, and we can push it in the vector, results.
After solving the results for each query, we can return the vector, results.

Try Problem

Approach 2

The approach is to use Dynamic Programming to avoid recalculating the number of 1s present in any given square. With the help of some precalculations, we can find out the number of 1s efficiently. We can also further optimize our solution by using binary search instead of increasing the length of the possible squares one by one.

Steps:

Define a vector, say results, to store the result of each query. We will return this after solving the result of each query.
Store the value of grid.size() in a variable, say N.
Store the value of grid[0].size() in a variable, say M.
Declare a 2D vector, say dp, to calculate the number of 1s in any given square efficiently.
Make dp[0][0]=grid[0][0].
Run a loop from i=1 to i<N, and make dp[i][0] = dp[i-1][0] + grid[i][0].
Run a loop from j=1 to j<M, and make dp[0][j] = dp[0][j-1] + grid[0][j].
Run a loop from i=1 to i<N, and another loop from j=1 to j<M and do:
1. dp[i][j] = dp[i-1][j] + dp[i][j-1] + grid[i][j] - dp[i-1][j-1].
Run a loop from i=0 to i<queries.size, and do:
1. Declare a variable, say cntrY, and make it equal to queries[i][0]. Declare another variable, say cntrX, and make it equal to queries[i][1]. These two values are the location of the cell which should serve as the center of the possible squares.
2. Declare a variable, say nearestEdgeDist, to store the value of the distance of the nearest edge of the grid from the center cell. Formally, make nearestEdgeDist = min(cntrY, n - cntrY - 1, cntrX, m - cntrX - 1).
3. Define a variable, say sideLength=0, to store the length of the biggest square meeting all the required conditions.
4. Now, we will apply binary search on the possible length of the square. So, define a variable, say low=0. This is the lower limit of half of the side length. Initialize another variable, say high=nearestEdgeDist. This is the upper limit of half of the side length.
5. Now, run a while loop until low<=high, and do:
  1. Define a variable, say len, and make it equal to (low + high) /2.
  2. Now, find the boundaries of this square. Declare ,
    1. top = cntrY - len.
    2. bottom = cntrY + len.
    3. left = cntrX - len.
    4. right = cntrX + len.
  3. Define a variable, say oneCount and make it equal to dp[bottom][right].
  4. If left>0, then make oneCount -= dp[bottom][left-1].
  5. If top>0, then make oneCount -= dp[top-1][right].
  6. If left>0 and top>0, then make oneCount += dp[top-1][left-1].
  7. If oneCount <= k, make sideLength = 2*len +1 and low = len+1.
  8. Else, make high = len-1.
6. Now, after applying binary search, push the value of sideLength to the vector, results.
Return the vector, results.