Solution Approach
The solution approach is straightforward. In the solution, we will check for the largest number of consecutive columns with at least one 1 in them for each query. We may not care about the rows for the area, considering any number of rows below x2-x1+1 will decrease the area. So we find the largest number of consecutive columns and then multiply it with x2-x1+1 to get the required maximum area.
The steps of implementation are:
-
Take the number of rows and columns in N and M, respectively. Now input the N*M matrix. Take in the value of the number of queries in Q. for each query, input the top left and bottom right boundaries x1,y1,x2,y2 in a list, and then add this list in the queries list.
-
Loop over to solve each query independently.
-
For query i, Initialize area and count with 0. Store the values of the top left and bottom right boundary in x1,y1,x2, and y2 variables. Loop over the columns from y1-1 to y2 as the index starts at 1. Inside this loop, run a loop for a row and break the loop as soon as a value 1 is found in any row.
-
Now, if the row has 1 in it, include this row else, start again with count =0, the count stores the number of consecutive columns with at least one 1.
-
At last, find the area by multiplying the count that is the rectangle's width by(x2-x1+1) that, is the total height of the rectangle, and print this value.
- Repeat this process for each query.
Python Implementation
def main():
#input the number of rows and columns
N, M = list(map(int,input().split(" ")))
matrix = []
#input the matrix of size N*M
for i in range(N):
row = list(map(int, input()))
matrix.append(row)
#input the number of queries and store the boundaries x1,y1,x2,y2 in queries list
Q = int(input())
queries = []
for i in range(Q):
quer = list(map(int,input().split(" ")))
queries.append(quer)
#Loop over to solve each query independently
for i in range(Q):
area, count = 0, 0
#(x1,y1) is the top left boundary
#(x2,y2) is the bottom right boundary
x1,y1,x2,y2 = queries[i]
#Loop over for each column to count the largest number of consecutive columns that have at least one 1 in it.
for col in range(y1-1, y2):
flag = 0
#for each row, check for presence of at least one 1
for row in range(x1-1, x2):
if matrix[row][col] == 1:
flag = 1
break
#if 1 is present in this col increment count, else set count to 0.
if flag :
count += 1
else:
count = 0
#evaluate the area by multiplying the width and height of rectangle
#here width is the value of count
#and height is the number of rows including x1 and x2.
var = count*(x2-x1+1)
if area < var :
area =var
#print the result for each query.
print(area)
#execute main
main()
You can also try this code with Online Python Compiler
Input
4 4
0000
0010
0100
1000
1
1 2 3 4
Output
6
Complexities
Time complexity
O(Q*M*N), where Q is the number of queries, M and N are the numbers of columns and rows, respectively.
Reason: We are solving each query independently, therefore the term Q in the complexity, and then we are searching for the largest rectangle by looking at each column and row for the given left and right boundaries, which will take N*M operations in the worst case if the window size is as large as the matrix. Hence the complexity O(Q*M*N).
Space Complexity
O(N*M + 4*Q), where Q is the number of queries, M and N are the numbers of columns and rows, respectively.
Reason: To store the elements in our matrix, we need a data structure that takes N*M space complexity, and then to store the left and right boundaries, another data structure is required that takes 4*Q space. Hence, The complexity of O(N*M + 4*Q).
FAQ’s
1. What is a matrix?
A matrix is a 2d array where the elements are stored in rows and columns. It is sometimes also called an array of an array. It is good when we have to store the data in tabular form.
2. What is data structure in programming?
A data structure is a way of organising data such that the access, manipulation, and storage of data become efficient and convenient. Some data structures include array, LinkedList, stack, queue, tree, and graph.
3. What is the main function of python?
The main function is important for the execution of a program. It specifies the point from which the program is to be executed when run directly and does not execute when imported as a module.
4. How do you analyze the performance of an algorithm?
The performance of an algorithm is analyzed using Time and Space complexity. Time complexity gives the run time an algorithm, and space complexity gives the amount of space the algorithm takes when executed.
5. What is the default return type of input function in python?
The default return type of input function is a string, and for taking input of integer or list, we have to explicitly typecast the returned value with int() or list() function. A split() function can also be used to take a list as input separated by some symbol in a single line.
Key Takeaways
In this article, we learned how to solve the "Largest area” problem. The problem was based on multiple queries, which are solved separately.
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more?
Attempt our Online Mock Test Series on Coding Ninjas Studio now!
Happy Coding!
8+ registered 