1504. Count Submatrices With All Ones
Approach
For each row compute consecutive-1 widths; for each column scan upward counting how many consecutive rows have width >= current width.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
Dynamic programming solves problems by breaking them into overlapping sub-problems and storing results to avoid redundant work. The key steps are: define state, write a recurrence relation, set base cases, and choose top-down (memoization) or bottom-up (tabulation). DP often yields O(n²) → O(n) time improvements over brute force.
Matrix problems often involve BFS/DFS flood fill, dynamic programming on 2D grids, or spiral/diagonal traversal. For row × column DP, break it into 1D sub-problems column by column. Common pitfalls: boundary checks and modifying the input matrix in-place.
// Approach: For each row compute consecutive-1 widths; for each column scan upward counting how many consecutive rows have width >= current width.
// Time: O(m·n) Space: O(m·n)
public class Solution
{
public int NumSubmat(int[][] mat)
{
int rows = mat.Length; // the number of rows in given matrix
int cols = mat[0].Length; // the number of columns in given matrix
int[][] width = new int[rows][]; // buffer to store the width of consecutive ones ending at (i, j)
// Initialize the width array
for (int i = 0; i < rows; i++)
width[i] = new int[cols];
// Compute the width matrix
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
// If the cell contains a '1', calculate the width
if (mat[i][j] == 1)
width[i][j] = (j == 0) ? 1 : 1 + width[i][j - 1];
// '0' cells are initialized as zero, no need to explicitly set them
}
}
int count = 0; // variable to accumulate the count of submatrices
// For each position in the matrix, calculate the number of submatrices
// that can be formed ending at (i, j)
for (int i = 0; i < rows; ++i)
{
for (int j = 0; j < cols; ++j)
{
// Start with a large number to minimize with the width of rows above
int minWidth = int.MaxValue;
// Move up from row 'i' to '0' and calculate the minWidth for submatrices ending at (i, j)
for (int k = i; k >= 0 && minWidth > 0; --k)
{
minWidth = Math.Min(minWidth, width[k][j]);
count += minWidth; // accumulate the count with the current minWidth
}
}
}
return count; // returning the total count of submatrices
}
}