Start learning free

LESSON 220 OF 344 · PARTIAL SUMS #2

Count Submatrices With All Ones in Java: Row Pairs and Column Runs

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

    JAVA · PARTIAL SUMS #2

    Count Submatrices With All Ones in Java, explained

    Problem overview

    The method numberOfSubmatricesWithAllOnes receives an m x n matrix mat of 0s and 1s, as an int[][]. It returns how many rectangular blocks of cells, of any height and width, contain only 1s. Every block counts, including overlapping ones and single cells.

    For mat = [[1,0,1],[1,1,0],[1,1,0]] the answer is 13. There are six single cells holding a 1, and the larger blocks bring the total to 13: two blocks of size 1x2, three of size 2x1, one of size 2x2 and one of size 3x1.

    Approach: fix the top and bottom rows, then count along the columns

    Checking every rectangle independently means choosing its top row, bottom row, left column and right column, and then scanning its cells. That is too much work. The lesson cuts it down in two steps.

    Fix a pair of rows. Choose a top row upRow and a bottom row downRow. Every rectangle in this horizontal slab spans exactly those rows. A column can be part of such a rectangle only if it holds a 1 in every row of the slab. Keep an array fullCol with one entry per column: 1 if the column is all ones within the slab so far, otherwise 0.

    Count along the columns. With fullCol known, a rectangle of this height is just a stretch of consecutive 1s in fullCol. A run of length L contains L * (L + 1) / 2 such stretches. The code gets this total without a formula. While scanning left to right, it keeps currLength, the length of the run ending at the current column, and adds it to the answer at every column. A run of length L then adds 1 + 2 + ... + L, because the stretches that end at the column in position k of the run have widths 1 to k.

    The slab grows downward one row at a time. When downRow moves down, any column with a 0 in the new row is switched off for good. It stays off for all taller slabs with the same top row, so fullCol never needs to be rebuilt within one top row. It is reset to all ones when upRow changes.

    Here is the first example. With upRow = 0 and downRow = 0, fullCol is [1,0,1], which adds 1 + 0 + 1 = 2. For downRow = 1 the second row [1,1,0] switches off column 2, leaving [1,0,0], which adds 1. For downRow = 2 it stays [1,0,0] and adds 1. So top row 0 gives 4. Top row 1 gives 3 + 3 = 6, and top row 2 gives 3. The total is 4 + 6 + 3 = 13.

    Step by step

    1. Start the counter matCount at 0.
    2. Create fullCol with one entry per column, mat[0].length, and fill it with 1s. A new int[] starts with zeros, so the fill is needed.
    3. Loop over the top row upRow from 0 to the last row.
    4. Reset fullCol to all ones. A new top row starts a new slab, and columns switched off for an earlier top row must be allowed again.
    5. Loop over the bottom row downRow from upRow down to the last row. Starting at upRow includes slabs that are one row tall.
    6. Loop over the columns and, for each one, look at the cell in the new row.
    7. Switch off columns with a zero. If mat[downRow][col] is 0, set fullCol[col] to 0.
    8. Prepare the run length. Declare currLength as 0 before scanning fullCol.
    9. Scan fullCol left to right with an enhanced for loop. Its variable holds each entry's value, 0 or 1, not its index.
    10. Extend the run on a 1 by adding one to currLength.
    11. Break the run on a 0 by setting currLength back to 0.
    12. Add the run length to matCount at every column, which counts the rectangles ending at that column.
    13. Return matCount after all the loops.

    The solution in Java

    class Solution {
    public int numberOfSubmatricesWithAllOnes(int[][] mat) {
        int matCount = 0;
        int[] fullCol = new int[mat[0].length];
        Arrays.fill(fullCol, 1);
        
        for (int upRow = 0; upRow < mat.length; upRow++) {
            Arrays.fill(fullCol, 1);
            
            for (int downRow = upRow; downRow < mat.length; downRow++) {
                for (int col = 0; col < mat[0].length; col++) {
                    if (mat[downRow][col] == 0) {
                        fullCol[col] = 0;
                    }
                }
                
                int currLength = 0;
                for (int col : fullCol) {
                    if (col == 1) {
                        currLength++;
                    } else {
                        currLength = 0;
                    }
                    matCount += currLength;
                }
            }
        }
        
        return matCount;
    }
}

    The Java details worth a closer look:

    • Dimensions of an int[][]. mat.length is the number of rows, and mat[0].length is the length of the first row, which is the number of columns. The constraints guarantee at least one row and column, so mat[0] exists.
    • Arrays.fill(array, value) sets every element of a one-dimensional array to the value. The first call is redundant, since the loop resets fullCol before it is used. It does no harm.
    • The enhanced for loop. for (int col : fullCol) gives the values and copies each into col. Assigning to it would not change the array. The earlier plain loop also used the name col, but that variable's scope ended with its loop, so the name can be used again.
    • int is big enough. The largest answer comes from a 150 by 150 matrix of 1s: (150 * 151 / 2)² = 128,255,625. That fits in an int, whose maximum is about 2.1 billion.

    Complexity

    Let the matrix have m rows and n columns.

    Time: O(m² * n). There are about m² / 2 pairs of (upRow, downRow), and each does O(n) work: one pass to update fullCol and one to count runs. With m and n up to 150, that is a few million steps, which is fast. Choosing all four sides and scanning each rectangle would be O(m² * n² * m * n).

    Space: O(n), for fullCol alone.

    Edge cases and common mistakes

    • A single cell. [[1]] gives 1 and [[0]] gives 0.
    • A single row. [[1,1,1]] gives 6, which is 1 + 2 + 3. [[1,0,1]] gives 2, because the zero breaks the run.
    • A full matrix. [[1,1],[1,1]] gives 9: four 1x1, two 1x2, two 2x1 and one 2x2.
    • Not resetting fullCol for each top row. A zero found in an earlier slab would keep its column switched off, and the count would come out too small.
    • Not resetting currLength for each slab. It must start at 0 before every scan of fullCol, or runs would leak from one slab into the next.
    • Adding currLength only when a run ends. A run of length L contributes L rectangles at its last column but also contributes at every earlier column. The addition must happen at every column.
    • Treating fullCol as the matrix row. It describes the whole slab, not just downRow. A column is on only if every row in the slab has a 1 there.

    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]] gives 1.
    • [[1,1],[1,1]] gives 9.
    • [[1,1,1]] gives 6.
    Keep going with JavaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free