Codiwan.com

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

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

```
```

``````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

2. 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},
}
``````
3. For ``, it is 2, containing ` and ` and for `` it is only 1.
4. Keep the value of width inside `maxWidth`.
5. This will give the maximum width possible from the current index. Also, add 1 to `numberOfSubMatrices` if 1 is found.
6. 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.
7. 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},
}
``````
8. For this(^) example, `maxWidth` will be `3` for ``. Then we’ll move to `` 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.
9. Repeat this process until `maxWidth` is 0.
10. This way we’ve found all the submatrices starting at ``.
11. 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 `` is stored at `depthWidthCache` and `maxWidth` is stored at `depthWidthCache`.

``````func numSubmat(mat [][]int) int {
numberOfSubMats := 0
var depthWidthCache = make([][]int, len(mat))
for i, matRow := range mat {
depthWidthCache[i] = make([]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] = totalWidth
} else {
totalWidth = 0
}
}
}

// // calculating the maxHeight here
for j := 0; j < len(mat); j++ {
totalHeight := 0
for i := len(mat) - 1; i > -1; i-- {
if mat[i][j] == 1 {
totalHeight++
depthWidthCache[i][j] = 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` 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 ``. So, we’ll add 3 to `numberOfSubMatrices`.

Let’s take one more example:

`[1 2]` located at ``. It means that the element, `mat`, 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 ``. So, we’ll add 2 to `numberOfSubMatrices`.

At `` 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., `` and ``. 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); j++ {
currentDepth := depthWidthCache[i][j]
currentWidth := depthWidthCache[i][j]
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 {
numberOfSubMats += currentWidth
} else {
numberOfSubMats += currentDepth
}
}
} else {
numberOfSubMats += currentWidth
for k := i + 1; k <= i+currentDepth-1; k++ {
maxWidthFromNextRowElem := depthWidthCache[k][j]
if maxWidthFromNextRowElem >= currentWidth {
numberOfSubMats += currentWidth
} else {
numberOfSubMats += maxWidthFromNextRowElem
currentWidth = maxWidthFromNextRowElem
}
}
}
}
}
``````
Loading Comments... 