The blog for Design Patterns, Linux, HA and Myself!

12
July 2020

This document presents the solution to the problem 1504 - Count Submatrices With All Ones - Leetcode.

Note: Make sure to go through the code comments as well. It’ll help you understand the concept better.

` ````
Given a rows * columns matrix mat of ones and zeros, return how many submatrices have all ones.
Example 1:
Input: mat = [[1,0,1],
[1,1,0],
[1,1,0]]
Output: 13
Explanation:
There are 6 rectangles of side 1x1.
There are 2 rectangles of side 1x2.
There are 3 rectangles of side 2x1.
There is 1 rectangle of side 2x2.
There is 1 rectangle of side 3x1.
Total number of rectangles = 6 + 2 + 3 + 1 + 1 = 13.
Example 2:
Input: mat = [[0,1,1,0],
[0,1,1,1],
[1,1,1,0]]
Output: 24
Explanation:
There are 8 rectangles of side 1x1.
There are 5 rectangles of side 1x2.
There are 2 rectangles of side 1x3.
There are 4 rectangles of side 2x1.
There are 2 rectangles of side 2x2.
There are 2 rectangles of side 3x1.
There is 1 rectangle of side 3x2.
Total number of rectangles = 8 + 5 + 2 + 4 + 2 + 2 + 1 = 24.
Example 3:
Input: mat = [[1,1,1,1,1,1]]
Output: 21
Example 4:
Input: mat = [[1,0,1],[0,1,0],[1,0,1]]
Output: 5
```

Let’s start with a brute force approach for the input

```
input = [][]int{
{1, 0, 1},
{1, 1, 0},
{1, 1, 0},
}
```

This animation shows the count of all the submatrices with all 1s on the right-hand side. The green areas show the found submatrices. The color changes to red if we encounter 0.

So, What would we be doing in a brute force approach? We’ll

- Start with the first element of the array
- Find the width of the continuous 1s on the right side from the current index.
`input = [][]int{ {1, 0, 1}, {1, 1, 0}, {1, 1, 0}, }`

- For
`[1][0]`

, it is 2, containing`[1][0] and [1][1]`

and for`[0][0]`

it is only 1. - Keep the value of width inside
`maxWidth`

. - This will give the maximum width possible from the current index. Also, add 1 to
`numberOfSubMatrices`

if 1 is found. - Move to the next row at the same column and then count the number of continuous 1s, horizontally, from that index
until
`maxWidth`

number of 1s are found. - If there are lesser 1s than
`maxWidth`

then replace the value of`maxWidth`

with number of 1s found.`input = [][]int{ {1, 1, 1}, {1, 1, 0}, {1, 0, 0}, {0, 0, 0}, }`

- For this(^) example,
`maxWidth`

will be`3`

for`[0][0]`

. Then we’ll move to`[1][0]`

and`maxWidth`

will reduce to 2 and then to 1 and 0 subsequently while moving to the next row. Also, add 1 to`numberOfSubMatrices`

if 1 is found. - Repeat this process until
`maxWidth`

is 0. - This way we’ve found all the submatrices starting at
`[0][0]`

. - Repeat the steps 1 - 9 for all the indices in the input 2D array.

So, What will be the time complexity for this approach?

The steps 1-9 is of `O(M*N)`

time complexity, and these steps are to be repeated on all the elements. This will make
the time complexity `O(M*N*M*N)`

. If the input is a square matrix then the Time Complexity will be `O(n^4)`

.

What are the improvements that can be make on this approach?

- In the steps 6-8, we’re horizontally looping over the row elements until the
`maxWidth`

number of 1s have been counted. If we know the`maxWidth`

for all the indices beforehand then we won’t have to do steps 6-8.

This is how I’ve created the cache of `maxWidth`

and `maxHeight`

. The variable, `depthWidthCache`

, contains the `maxHeight`

and `maxWidth`

for each of the element of the matrix on the same indices. For example, `maxheight`

for `[0][0]`

is stored
at `depthWidthCache[0][0][0]`

and `maxWidth`

is stored at `depthWidthCache[0][0][1]`

.

```
func numSubmat(mat [][]int) int {
numberOfSubMats := 0
var depthWidthCache = make([][][2]int, len(mat))
for i, matRow := range mat {
depthWidthCache[i] = make([][2]int, len(matRow))
}
// calculating the maxWidth here
for i := 0; i < len(mat); i++ {
totalWidth := 0
for j := len(mat[i]) - 1; j > -1; j-- {
if mat[i][j] == 1 {
totalWidth++
depthWidthCache[i][j][1] = totalWidth
} else {
totalWidth = 0
}
}
}
// // calculating the maxHeight here
for j := 0; j < len(mat[0]); j++ {
totalHeight := 0
for i := len(mat) - 1; i > -1; i-- {
if mat[i][j] == 1 {
totalHeight++
depthWidthCache[i][j][0] = totalHeight
} else {
totalHeight = 0
}
}
}
```

For the following input:

```
[1, 0, 1]
[1, 1, 0]
[1, 1, 0]
```

`depthWidthCache`

will be

```
[[3 1] [0 0] [1 1]]
[[2 2] [2 1] [0 0]]
[[1 2] [1 1] [0 0]]
```

`[3 1]`

is the first element of `depthWidthCache`

. It means that the element, `mat[0][0]`

is part of a `3 x 1`

matrix.
Since, it is `3 x 1`

matrix, it will also be a `2 x 1`

and `1 x 1`

as well with all of them starting at `[0][0]`

. So,
we’ll add 3 to `numberOfSubMatrices`

.

Let’s take one more example:

`[1 2]`

located at `[2][0]`

. It means that the element, `mat[2][0]`

, is part of a `1 x 2`

matrix. Since, it is `1 x 2`

matrix, it will also be a `1 x 1`

as well with all of them starting at `[2][0]`

. So, we’ll add 2 to `numberOfSubMatrices`

.

At `[1][0]`

we find `[2 2]`

. It mean that the maximum width from here is 2 and the maximum height from here is 2 as well.
But, it doesn’t mean that there’s a matrix of `2 x 2`

starting from here. It just tells the max height and max width from
here is 2.

So, if the max width is 2 then it means that first row will contain 2 1s, i.e., `[1][0]`

and `[1][1]`

. We have to check
whether the next `maxHeight`

- 1 rows also contain the two 1s(or not?). If not, then we’ll reduce the `maxWidth`

just
like step 6.

Now, we can proceed with the actual solution:

```
numberOfSubMats := 0
for i := 0; i < len(mat); i++ {
for j := 0; j < len(mat[0]); j++ {
currentDepth := depthWidthCache[i][j][0]
currentWidth := depthWidthCache[i][j][1]
if currentDepth == 0 && currentWidth == 0 {
// if the current element is 0 then don't proceed
// and don't increase the count as well
continue
} else if currentDepth == 1 || currentWidth == 1 {
if currentDepth == 1 && currentWidth == 1 {
// this section means that we've found a 1
// but it doesn't have any neighbour that is also 1
numberOfSubMats++
} else {
// this section checks for the 1D matrix
if currentDepth == 1 {
// add the width
numberOfSubMats += currentWidth
} else {
// otherwise, add the height
numberOfSubMats += currentDepth
}
}
} else {
numberOfSubMats += currentWidth
for k := i + 1; k <= i+currentDepth-1; k++ {
maxWidthFromNextRowElem := depthWidthCache[k][j][1]
if maxWidthFromNextRowElem >= currentWidth {
numberOfSubMats += currentWidth
} else {
numberOfSubMats += maxWidthFromNextRowElem
currentWidth = maxWidthFromNextRowElem
}
}
}
}
}
```

Loading Comments...