Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Example
3.
Solution Approach
3.1.
Python Implementation
3.1.1.
Input 
3.1.2.
Output
3.2.
Complexities
3.2.1.
Time complexity
3.2.2.
Space Complexity
4.
FAQ’s
5.
Key Takeaways
Last Updated: Mar 27, 2024
Easy

Largest Area

Author Teesha Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The product of its sides gives the area of a rectangle; if one side is 10 and the other is 20, then the area of this rectangle is 10*20 = 200 square units.

Problem Statement

A computer virus had infected Amy’s computer when she was downloading a bunch of courses for her college academics. The virus stopped and closed all the programs on her laptop. 

Amy can only see a matrix of size N*M on her screen. Each matrix cell has a number of 0 or 1 and has a color. Initially, all cells are black.

The next thing Amy sees is that the virus opens Q windows. For each window, the coordinates of two points are visible on the screen x1,y1 and x2,y2, which are the top left and bottom right points for the window the virus paints in white. All the cells x,y for which x1<=x<=x2 and y1<=y<=y2 satisfies are painted white. Index starts at 1.

Each window has a password that must be typed to move to the next window and stop the virus. The password for each window is the maximum area of the rectangle for which all cells are painted white, and each column has at least one 1 in it. 

Help Amy to stop the virus.

Input format 

The first line contains two integers, N and M - the number of rows and columns.

The following N lines describe the matrix with M numbers of 0 or 1 only, without separating spaces.

The following line consists of integer Q - the number of windows. Next, Q lines describe i th window: each contains the coordinates of the left and right boundaries x1,y1 and x2,y2.

Output format

The Q lines should each contain a single integer A - the password for the window i (

1 <= i <= Q).

Example

Input

4 4
0000
0010
0100
1000
1
1 2 3 4


Output

6

Explanation

The Matrix is of size 4*4 with given values, and there is only one window. So the virus paints the following windows white.

Out of the painted white columns, there are two columns with at least one 1 in them, shown in green below.

Now there is only one rectangle whose area is 3*2 = 6. Hence, the answer is 6.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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()


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!

Previous article
Solving the I Love String Problem Using KMP Algorithm
Next article
Length of Longest Substring Occurring in a Given Substring at Least ‘K’ Times
Live masterclass