Largest Square

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
4 upvotes
Asked in companies
HCL TechnologiesZSDeutsche Bank

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.

Detailed explanation ( Input/output format, Notes, Images )
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.
Sample Input 1:
1
4 4
1 0 0 0 
0 1 0 0 
1 0 1 0 
0 1 1 0
2 2
1 1
1 2
Sample Output 1:
1 3
Explanation for sample input 1:
In the given test case, the value of ‘K’ is 2. 

For the first query, the center given is (1, 1). The (1, 1) cell has 1 so the total count of 1s in this square remains 1 which is less than ‘K’. The next bigger square is of length 3 whose top-left cell is (0, 0) and the bottom-right cell is (2, 2). The total number of 1s in this square is 4 which is more than ‘K’ so we can’t consider this square and hence, the result for this query will be 1.  

In the second query, the center given is (1, 2). If we consider the square whose top-left cell is (0, 1) and bottom-right cell is (2, 3), then the number of 1s in this square will be 2 which is equal to ‘K’. We can not choose a bigger square because there is no bigger square possible, having its center at (1, 2). So, the answer to this query will be 3.

.

Sample Input 2:
1
5 5
1 0 0 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 1
1 0 0 0 0
4 1
2 2
Sample Output 2:
5
Explanation for sample input 2:
In the given test case, the value of ‘K’ is 4. 

For the first query, we take (2, 2) as the center. If we consider the square whose top-left cell is (0, 0) and bottom-right cell is (4, 4), then the number of 1s in this square will be 4 which is equal to ‘K’. We can not choose a bigger square because there is no bigger square possible, having its center at (2, 2). So, the answer to this query will be 5 as this is the length of the required square.
Hint

Solve each query independently. 

Approaches (2)
Using Brute Force

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:

 

  1. Define a vector, say results, to store the result of each query. We will return this after solving the result of each query.
  2. Store the value of grid.size() in a variable, say N.
  3. Store the value of grid[0].size() in a variable, say M. 
  4. 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.
  5. After solving the results for each query, we can return the vector, results.
Time Complexity

O(Q * N * M * X), where ‘Q’ is the total number of queries. ‘N’ and ‘M’ are the dimensions of the grid and ‘X’ is the distance of the center from the nearest edge of the grid.

 

For each query, we are trying all the squares whose center is the cell given in the query. There can be as many as ‘X’ such squares. For every such square, we are counting the number of 1s in it. This takes O(N*M) time for each square. So, for each query, the time complexity will become O(N*M*X). Since there are ‘Q’ queries, the overall complexity becomes O(Q*N*M*X).

Space Complexity

O(1)

 

We are not using any extra auxiliary space.

Code Solution
(100% EXP penalty)
Largest Square
Full screen
Console