Start learning free

LESSON 223 OF 347 · PARTIAL SUMS #2

Count Submatrices With All Ones in C#: O(rows² x cols)

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

    NumberOfSubmatricesWithAllOnes receives a binary matrix as a jagged array, int[][] mat, and returns how many rectangular submatrices contain only 1s. Two rectangles count separately if their position differs, even when they cover the same pattern. A single cell with a 1 is a submatrix, and the matrix has between 1 and 150 rows and columns.

    For [[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. For [[0,1,1,0],[0,1,1,1],[1,1,1,0]] the answer is 24.

    Approach

    A rectangle is fixed by its top row, bottom row, left column and right column. Trying all four choices with a check of the cells inside would be far too slow. The solution fixes the top and bottom rows first, which gives a horizontal slab, and counts the rectangles inside that slab in one scan.

    Inside a slab, a column is intact if every cell of that column within the slab is 1. A rectangle with exactly those top and bottom rows is all ones precisely when all its columns are intact. So the rectangles in the slab are the contiguous stretches of intact columns.

    The key observation is how to count them. Scan the columns left to right and track currLength, the length of the run of intact columns that ends at the current column. If the run has length L, then L rectangles use the current column as their right edge, namely the ones of widths 1, 2, ..., L. Adding currLength to the total at every column therefore counts every rectangle in the slab exactly once. A broken column resets the run to 0 and adds nothing.

    Growing the slab

    For a fixed top row, the bottom row moves down one row at a time. Making the slab one row taller can only break columns, never repair them, so the array fullCol is updated in place: a 0 in the new row sets that column's entry to 0. No rescan of the earlier rows is needed. When the top row changes, fullCol is refilled with 1s.

    On the first example, the slab from row 0 to row 0 has intact columns [1, 0, 1], which adds 2. Rows 0 to 1 leave only column 0 intact, adding 1, and rows 0 to 2 add 1 again. That is 4 for top row 0. Top row 1 contributes 3 + 3 = 6, and top row 2 contributes 3. The total is 4 + 6 + 3 = 13.

    Step by step

    1. Declare matCount as the running total.
    2. Create fullCol as an int[] with one entry per column, filled with 1s using Array.Fill.
    3. Loop over the top row, upRow, from 0 to the last row.
    4. Refill fullCol with 1s at the start of each top row, so earlier slabs don't disqualify columns in the new one.
    5. Loop the bottom row, i, from upRow down to the last row.
    6. Update the columns. For each column, if mat[i][col] is 0, store 0 in fullCol[col].
    7. Start a fresh currLength at 0 for every slab, then scan fullCol from left to right.
    8. Extend or reset the run: add 1 to currLength for an intact column, or set it to 0 otherwise.
    9. Add currLength to matCount on every column, then return matCount after the loops.

    The solution in C#

    class Solution {
    public int NumberOfSubmatricesWithAllOnes(int[][] mat) {
        int matCount = 0;
        int[] fullCol = new int[mat[0].Length];
        Array.Fill(fullCol, 1);

        for (int upRow = 0; upRow < mat.Length; upRow++) {
            Array.Fill(fullCol, 1);

            for (int i = upRow; i < mat.Length; i++) {
                for (int col = 0; col < mat[0].Length; col++) {
                    if (mat[i][col] == 0) {
                        fullCol[col] = 0;
                    }
                }

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

        return matCount;
    }
}

    C# details:

    • Jagged arrays. int[][] is an array of row arrays, so mat.Length is the number of rows, mat[0].Length is the number of columns, and a cell is mat[i][col]. This differs from the two-dimensional int[,], which uses grid[x, y].
    • Array.Fill(array, value) sets every element of an array to the same value. It is a static method of System.Array, available since .NET Core 2.0.
    • Two variables named col. The for loop's col is an index, and the foreach loop's col is a value from fullCol. The two loops are siblings, so each variable exists only inside its own loop and they don't clash. Using the same name for both is confusing, though, so a name such as flag for the second would read better.
    • foreach reads, it doesn't write. You can't assign to the loop variable, which is fine here because foreach only reads fullCol.

    Complexity

    Time: O(R² x C), where R is the number of rows and C the number of columns. There are about R²/2 (top, bottom) pairs, and each does O(C) work for the update and again for the scan. With 150 x 150 inputs, that is a few million steps.

    Space: O(C). Only fullCol is allocated, one entry per column.

    Edge cases and common mistakes

    • Forgetting to reset fullCol when upRow changes. Zeros from an earlier slab then wrongly disqualify columns, and the count comes out too small.
    • Not resetting currLength per slab. A run must not carry over from one slab to the next. The declaration sits inside the i loop for this reason.
    • Adding only at the end of a run. Adding currLength at every column counts all rectangle widths. Adding once per run would count only the widest.
    • A matrix of all zeros returns 0, and a single [[1]] returns 1.
    • An all-ones matrix with R rows and C columns has R(R+1)/2 x C(C+1)/2 submatrices. For 2 rows and 3 columns that is 3 x 6 = 18, which the code returns.
    • Counting with int. The largest case, a 150 x 150 matrix of ones, has (150 x 151 / 2)² = 128,255,625 submatrices, which fits in an int.

    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,1,1]] gives 18.
    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