Start learning free

LESSON 220 OF 344 · PARTIAL SUMS #2

Count Submatrices With All Ones in Python: O(m² · n) Row Slabs

Practice O(n^3) Read the full explanation

Given an m x n binary matrix mat, return the number of submatrices that 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.

 

Constraints:

  • 1 <= m, n <= 150
  • mat[i][j] is either 0 or 1.
STEP 1 OF 13
    Ctrl + Enter to check

    PYTHON · PARTIAL SUMS #2

    Count Submatrices With All Ones in Python, explained

    Problem overview

    The method numberOfSubmatricesWithAllOnes receives a binary matrix mat with m rows and n columns. It returns how many rectangular submatrices consist entirely of 1s. A submatrix is any block of consecutive rows and consecutive columns, and a single cell counts as a 1x1 submatrix.

    For [[1, 0, 1], [1, 1, 0], [1, 1, 0]] the answer is 13. There are six 1x1 blocks (one per 1), two 1x2 blocks, three 2x1 blocks, one 2x2 block and one 3x1 block. Rectangles of different positions are counted separately, even when they have the same shape.

    Approach: fix the rows, then count along the columns

    Choosing a rectangle means choosing a top row, a bottom row, a left column and a right column. Trying all four choices directly is too slow, so the lesson fixes the first two and counts the last two cleverly.

    Fix a top row upRow and a bottom row downRow. The rows between them form a horizontal slab. A column is full for this slab if every cell of it inside the slab is 1. A rectangle in the slab with all ones must use only full columns, and any run of consecutive full columns gives all the rectangles you can cut from it.

    So the problem inside one slab is a one-dimensional count: given a row of full/not-full flags, how many runs of consecutive full flags are there, counting every sub-run? A run of length L holds L * (L + 1) / 2 of them. The lesson counts them by scanning left to right. At each column, if the run of full columns ending there has length currLength, then exactly currLength rectangles end at that column: widths 1, 2, up to currLength. Add that to the total at every column.

    Moving downRow down by one row only adds one row to the slab, so the full-column flags can be updated in place. A column can only lose its status as the slab grows, which makes the update a single pass over the columns.

    Step by step

    1. Start the total. matCount begins at 0.
    2. Create fullCol as a list of 1s, one per column: [1] * len(mat[0]). Entry c says whether column c is still all ones in the current slab.
    3. Loop over upRow from the first row to the last. It fixes the slab's top edge.
    4. Reset fullCol to 1s at the start of each top row with a small loop over i. A new slab starts with no disqualified columns. Without the reset, zeros from the previous top row would leak into it.
    5. Loop over downRow from upRow to the last row. The slab now spans upRow to downRow.
    6. Loop over each column col to fold in the row just added.
    7. Disqualify columns that hit a zero. If mat[downRow][col] is 0, set fullCol[col] to 0. It never goes back to 1 while the slab grows.
    8. Start a run counter: currLength = 0, after the update loop.
    9. Loop over fullCol itself. The loop variable, named col again, now holds the flag (0 or 1), not an index.
    10. Extend the run on a 1: add 1 to currLength.
    11. Reset the run on a 0: set currLength to 0.
    12. Add currLength to matCount at every column, inside the same loop. These are the rectangles ending at that column for this slab.
    13. Return matCount after all loops.

    The solution in Python

    class Solution:
    def numberOfSubmatricesWithAllOnes(self, mat):
        matCount = 0
        fullCol = [1] * len(mat[0])
        for upRow in range(len(mat)):
            for i in range(len(fullCol)):
                fullCol[i] = 1
            for downRow in range(upRow, len(mat)):
                for col in range(len(mat[0])):
                    if not mat[downRow][col]:
                        fullCol[col] = 0

                currLength = 0
                for col in fullCol:
                    if col == 1:
                        currLength += 1
                    else:
                        currLength = 0
                    matCount += currLength
        return matCount

    Here is the slab starting at row 0 for the first example. After row 0, fullCol is [1, 0, 1], which adds 1 and 0 and 1, so 2 (two 1x1 blocks). After row 1 it is [1, 0, 0], adding 1 (a 2x1 block). After row 2 it is still [1, 0, 0], adding 1 (a 3x1 block).

    Python details worth knowing:

    • [1] * n builds a list of n ones. This is safe for numbers. With lists inside, the copies would all be the same object.
    • not mat[downRow][col] is true when the cell is 0, because not treats 0 as false.
    • The reused name col. The first loop uses col as an index and the second as a value from fullCol. Python allows it because the loops are separate, but it can confuse readers.
    • Resetting in place. The loop with i writes 1s into the same list, so there is only one fullCol. Assigning a new list would do the same.

    Complexity

    Time: O(m² · n). The two row loops visit about m² / 2 slabs. For each, two passes over the n columns do constant work per column. With m and n up to 150, that is roughly 150 · 150 · 150 operations, around three million.

    Space: O(n). The only extra storage is fullCol.

    Edge cases and common mistakes

    • Single cell. [[1]] gives 1 and [[0]] gives 0.
    • Full matrix. [[1, 1], [1, 1]] gives 9: four 1x1, two 1x2, two 2x1 and one 2x2.
    • One row. [[1, 1, 1]] gives 6, the run-counting formula 3 * 4 / 2.
    • Forgetting the reset. Without resetting fullCol for each upRow, later top rows start with columns already marked as broken, and the count comes out too low.
    • Not resetting currLength per slab. The counter must restart at 0 for each downRow, since runs don't carry over between slabs.
    • Adding only at the end of a run. The sum must be taken at every column, not once per run, otherwise the shorter widths are lost.

    Testing

    • [[1, 0, 1], [1, 1, 0], [1, 1, 0]] gives 13.
    • [[0, 1, 1, 0], [0, 1, 1, 1], [1, 1, 1, 0]] gives 24.
    • [[1, 1], [1, 1]] gives 9.
    • [[1, 1, 1]] gives 6.
    • [[0]] gives 0.
    Keep going with PythonAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free