Start learning free

LESSON 219 OF 343 · PARTIAL SUMS #2

Count Submatrices with All Ones in C++: O(m² · n) by Row Pairs

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

    C++ · PARTIAL SUMS #2

    Count Submatrices With All Ones in C++, explained

    Problem overview

    The function numberOfSubmatricesWithAllOnes receives an m x n matrix mat of 0s and 1s. It returns how many rectangular submatrices consist only of 1s. A submatrix is any block of consecutive rows and consecutive columns, so a single cell counts, and so does a 2x3 block.

    For mat = [[1,0,1],[1,1,0],[1,1,0]] the answer is 13: six 1x1 rectangles, two 1x2, three 2x1, one 2x2 and one 3x1. The matrix has at most 150 rows and 150 columns.

    Approach: fix the top and bottom rows

    A submatrix is determined by its top row, bottom row, left column and right column. Trying all four choices would be far too slow. The trick is to fix only the two rows and count the column ranges quickly.

    Pick a top row upRow and a bottom row downRow. Call a column intact if every cell in that column between those two rows is 1. A submatrix with this top and bottom is all ones exactly when each of its columns is intact. So the question becomes: how many ranges of consecutive columns consist only of intact columns?

    A run of L consecutive intact columns contains L ranges ending at its last column, namely the ones of width 1, 2, ..., L. If you scan left to right keeping currLength, the length of the current run, and add currLength to the total at every column, you count each range once, at its right edge. A column that isn't intact resets currLength to 0.

    The intact flags don't need recomputing from scratch. Keep the top row fixed and move the bottom row down one row at a time. Adding row downRow can only turn intact columns off, never on, so one pass over that row updates the flags.

    Here is the first example with upRow = 0. With downRow = 0 the flags are [1, 0, 1], which gives runs of length 1, 0 and 1, so 2 submatrices. With downRow = 1 the flags become [1, 0, 0], giving 1. With downRow = 2 they stay [1, 0, 0], giving 1. That is 4 for this top row. The top rows 1 and 2 give 6 and 3, and the total is 13.

    Step by step

    1. Create the counter. matCount starts at 0 and accumulates every submatrix found.
    2. Create the flags. fullCol has one entry per column, all set to 1. Entry c says whether column c is still intact for the current rows. vector<int>(count, value) builds count copies of value.
    3. Loop over the top row with upRow from the first row to the last.
    4. Reset the flags at the start of each top row. A new top row begins a new slab, and flags switched off by earlier top rows would wrongly carry over.
    5. Loop over the bottom row with downRow from upRow to the last row. Starting at upRow includes one-row slabs.
    6. Visit every column of the row just added.
    7. Switch off the zero columns. If mat[downRow][col] is 0, set fullCol[col] to 0. The flag stays off for every taller slab with the same top row.
    8. Start a run counter. Declare currLength as 0 for each slab, after the flags are updated.
    9. Scan the flags with a range-based loop. It yields the flag values, not column indices.
    10. Extend the run on a 1 by incrementing currLength.
    11. Break the run on a 0 by setting currLength to 0.
    12. Add currLength to matCount at every column, including the zero columns, where it adds 0.
    13. Return matCount after all loops.

    The solution in C++

    class Solution {
public:
    int numberOfSubmatricesWithAllOnes(vector<vector<int>>& mat) {
        int matCount = 0;
        vector<int> fullCol(mat[0].size(), 1);

        for (int upRow = 0; upRow < mat.size(); upRow++) {
            for (int i = 0; i < fullCol.size(); i++) {
                fullCol[i] = 1;
            }

            for (int downRow = upRow; downRow < mat.size(); downRow++) {
                for (int col = 0; col < mat[0].size(); col++) {
                    if (!mat[downRow][col]) {
                        fullCol[col] = 0;
                    }
                }

                int currLength = 0;
                for (int col : fullCol) {
                    if (col == 1) {
                        currLength++;
                    } else {
                        currLength = 0;
                    }
                    matCount += currLength;
                }
            }
        }

        return matCount;
    }
};

    The C++ details worth knowing:

    • !mat[downRow][col]. The ! operator turns an int into a bool: 0 becomes true and any other value becomes false. So the condition reads "this cell is 0".
    • Two different col variables. In the update loop, col is a column index. In the final range-based loop, int col : fullCol is a copy of a flag value, 0 or 1. They live in separate scopes, so the code is valid, but the second name is easy to misread as an index.
    • Vector constructor. vector<int> fullCol(mat[0].size(), 1) uses parentheses on purpose. With braces, {n, 1} would mean a vector holding the two numbers n and 1.
    • Reference parameter. vector<vector<int>>& mat avoids copying the whole matrix. The solution only reads it.
    • Unsigned sizes. The loops compare an int index with size(), which is unsigned. That is fine for non-negative indices, though the compiler may warn.

    Complexity

    Let the matrix have m rows and n columns.

    Time: O(m² · n). There are about m²/2 pairs of (top row, bottom row). For each pair the code does two passes over n columns, one to update the flags and one to count runs. With m = n = 150 that is about 3.4 million column steps, well within the limits.

    Space: O(n). The only extra memory is the fullCol vector.

    The answer itself is at most (150 · 151 / 2)² = 128,255,625, which fits in an int. This is the count for a matrix of all ones.

    Edge cases and common mistakes

    • A single cell. [[1]] gives 1 and [[0]] gives 0.
    • All ones. A 2x2 block of 1s gives 9: four 1x1, two 1x2, two 2x1 and one 2x2.
    • A single row. [[1, 1, 1]] gives 6, which is 1 + 2 + 3.
    • Not resetting fullCol for each top row. Zeros found under an earlier top row would remove columns that are intact for the new top row, and the count would be too low.
    • Not resetting currLength for each slab. A run would leak from one slab into the next. It must be declared inside the downRow loop.
    • Adding only at the end of a run. Adding currLength at every column, not once per run, is what counts the shorter ranges inside it.
    • Starting downRow at upRow + 1. That skips all submatrices that are one row tall.

    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 C++About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free