'Coding has over 700 languages', '67% of programming jobs aren’t in the
technology industry', 'Coding is behind almost everything that is powered
by electricity', 'Knowing how to code is a major requirement for
astronomers', 'The first computer didn’t use any electricity', 'Do you
know there is a coding language named “Go“', 'Computer programming is one
of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the
name of the first programming language', 'The first programmer was the
daughter of a mad poet', 'Many programming languages share the same
structure', 'Coding will soon be as important as reading', 'How many
programmers does it take to change a light bulb? None, that’s a hardware
problem', 'Why do Java developers wear glasses? Because they can’t C',
'Software and temples are much the same — first we build them, then we
pray', 'An engineer will not call it a bug — it’s an undocumented
feature', 'In a room full of top software designers, if two agree on the
same thing, that’s a majority', 'C programmers never die. They are just
cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java',
'The best thing about a boolean is even if you are wrong, you are only off
by a bit', 'Linux is only free if your time has no value', 'The computer
was born to solve problems that did not exist before', 'Coding has over
700 languages', '67% of programming jobs aren’t in the technology
industry', 'Coding is behind almost everything that is powered by
electricity', 'Knowing how to code is a major requirement for
astronomers', 'The first computer didn’t use any electricity', 'Do you
know there is a coding language named “Go“', 'Computer programming is one
of the fastest-growing careers', 'Fortran (FORmula TRANslation) was the
name of the first programming language', 'The first programmer was the
daughter of a mad poet', 'Many programming languages share the same
structure', 'Coding will soon be as important as reading', 'How many
programmers does it take to change a light bulb? None, that’s a hardware
problem', 'Why do Java developers wear glasses? Because they can’t C',
'Software and temples are much the same — first we build them, then we
pray', 'An engineer will not call it a bug — it’s an undocumented
feature', 'In a room full of top software designers, if two agree on the
same thing, that’s a majority', 'C programmers never die. They are just
cast into void', 'Knock, knock … Who’s there? … *very long pause* … Java',
'The best thing about a boolean is even if you are wrong, you are only off
by a bit', 'Linux is only free if your time has no value', 'The computer
was born to solve problems that did not exist before',

Problem of the day

New update is available. Click here to update.

Last Updated: 20 Nov, 2020

Hard

```
In the above image, areas in green, red, and violet color are all submatrices of the original 4x4 matrix.
```

```
1. Binary valued matrix has only two values in each cell : 0 and 1.
2. A submatrix is a matrix formed by selecting certain rows and columns from a larger matrix.
3. The area of a matrix with 'h' rows and 'w' columns is equal to 'h' * 'w'.
```

```
The first line of the input contains an integer 'T' denoting the number of test cases.
The first line of each test case contains two space-separated integers 'N' and 'M', where 'N' = the number of rows in the given matrix and 'M' = the number of columns in the given matrix.
Then 'N' lines follow for each test case. Each line contains 'M' space-separated integers (either 1 or 0) denoting matrix elements.
```

```
For each test case print in a single line the area of maximum size submatrix of all 1’s in the given matrix on a new line.
The output of each test case will be printed in a separate line.
```

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

```
1 <= 'T' <= 50
1 <= 'N', 'M' <= 100
Time Limit: 1 sec
```

- We start from the first row and move downwards.
- We create three 1-dimensional arrays HEIGHT[], LEFT[], RIGHT[].
- ‘HEIGHT’[i]: stores the number of current continuous 1’s in column i.
- LEFT[i] : stores the leftmost index ‘j’ such that all indices say ‘K’, ‘K’ belongs to [j, i], ‘HEIGHT’[k] >= ‘HEIGHT’[i].
- RIGHT [i]: stores the rightmost index ‘j’ such that all indices say ‘K’, ‘K’ belongs to [i, j], ‘HEIGHT’[k] >= ‘HEIGHT’[i].
- By the above definitions, it’s easier to figure out that we can update our maximum area with the value (‘HEIGHT’[i] * (RIGHT [i] - LEFT [i])).
- Now let’s think how will we update the above three 1-dimensional arrays itself.
- Initialize the ‘HEIGHT’[] array with 0.
- Iterate through the rows from 0 to N-1.
- For each column:
- If the current value (MAT [i][j]) is 1, then update ‘HEIGHT’[j]++.
- Else reset the value of ‘HEIGHT’[j] to 0.
- Note that:
- Initially, ‘HEIGHT’ was initialized to 0. So LEFT[] array should be initialised to 0 as per definition.
- And similarly, RIGHT[] array should be initialized to M.
- Updating the LEFT[] array in each iteration among rows 0 to N-1:
- We scan from left to right.
- Initialize LEFTBOUNDARY = 0, which means left boundary for all 1’s in the current row.
- Iterate in the current row:
- If the current value (MAT [i][j]) is 1, then you can reset the LEFT[j] from 0 to LEFTBOUNDARY.
- Else left[j] = 0 and update LEFTBOUNDARY to j+1. As the current value is 0, so next LEFTBOUNDARY for all the cells in the Matrix ahead of column j is at least j+1.
- Similarly, for the RIGHT[] array in each iteration among rows 0 to N-1:
- We scan from right to left.
- Initialize RIGHTBOUNDARY = 0, which means right boundary for all 1’s in the current row.
- Iterate in the current row:
- If the current value (MAT[i][j]) is 1, then you can reset the RIGHT[j] from M to RIGHTBOUNDARY.
- Else RIGHT[j] = 0 and update RIGHTBOUNDARY to j-1. As current value is 0, so next RIGHTBOUNDARY for all the cells in the Matrix before column j is atmost j-1.

- Let’s first understand how do we calculate the largest area in a histogram.
- Let’s take an example image:

In the above example, the largest rectangle area in the histogram is 5*2 = 10 units.

- The trick is to maintain a data structure that could mimic the function of the monotone increasing queue, which a stack can perform.
- Suppose you have an input array HEIGHT[0], HEIGHT[1], HEIGHT[2] …. HEIGHT[N-1].

- Let’s suppose that we are at some index ‘J’, then we try to fix HEIGHT[J] as the right side of the rectangle, then any of the heights { HEIGHT[0] …. HEIGHT[J-1] } in the monotone increasing queue can be the left side of the rectangle.
- Before adding current height, i.e. HEIGHT[J], to monotone increasing queue, for all the values in the queue that have HEIGHT[I] >= HEIGHT[J] can be part of a rectangle of fixed height, HEIGHT[J]. Thus, all such HEIGHT[I] is possible left sides of the current rectangle. Maximize the area of the rectangle possible in the histogram.
- Pop all such heights from the queue and increase the breadth of the rectangle by 1. When there are no more elements to pop out of the queue. Push the current index in the queue, as it is guaranteed to follow monotone increasing height property.
- Note that, if the histogram contains just one height, for such cases, initially push 0 to the queue to calculate maximum area.
- At each row, we will maintain an additional 1- dimensional array HEIGHT[] which denotes the height of contiguous 1’s at any column ‘J’, 0 <= ‘J’ <= 'M'-1, from bottom to top. Here bottom means current row ‘I’.
- If the value of MAT[I][J] = 0, then HEIGHT[J] is set to 0, else it is incremented by 1.
- This 1-dimensional height array at each row mimics the histogram. The only thing left is to apply the “Largest area in histogram” function to the updated HEIGHT[] array in each row.
- Maximize area at each step and return.

Similar problems

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

SudoKube

Ninja

Posted: 18 May, 2022

King Placement

Moderate

Posted: 22 May, 2022

Ninja and the experiment

Moderate

Posted: 5 Sep, 2022

Search In A Sorted 2D Matrix

Moderate

Posted: 23 Nov, 2022

Spiral Matrix

Easy

Posted: 24 Nov, 2022