LeetCode 1504: Count Submatrices With All Ones

Explanation:

To solve this problem, we can use dynamic programming. We will iterate through the matrix row by row and for each row, we will calculate the number of continuous ones ending at each cell. This information will help us to calculate the number of valid submatrices that end at each cell. By summing up the total count of valid submatrices for each cell, we can get the final answer.

Here are the steps:

1. Initialize a 2D array dp of the same size as the input matrix mat to store the count of continuous ones ending at each cell.
2. Iterate through each row of the matrix:
   • For the first cell of each row, the count of continuous ones ending at that cell will be the value of the cell itself.
   • For other cells, if the cell value is 1, update the count by adding the count of the cell to the left.
3. Iterate through each cell of the matrix and calculate the total number of valid submatrices ending at that cell by taking the minimum of the continuous ones at that cell and all the cells to its left in the same row.
4. Sum up the total count of valid submatrices for each cell to get the final answer.

Time Complexity: O(mn) where m is the number of rows and n is the number of columns in the matrix. Space Complexity: O(mn) for the dp array.

class Solution {
    public int numSubmat(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int[][] dp = new int[m][n];
        int count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    dp[i][j] = mat[i][j];
                } else {
                    dp[i][j] = mat[i][j] == 0 ? 0 : dp[i][j - 1] + 1;
                }
            }
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int min = dp[i][j];
                for (int k = i; k >= 0 && dp[k][j] > 0; k--) {
                    min = Math.min(min, dp[k][j]);
                    count += min;
                }
            }
        }

        return count;
    }
}