Count Submatrices With All Ones - Practice Coding Problems

Count Submatrices With All Ones - Problem

Given an m x n binary matrix mat, return the number of submatrices that have all ones.

A submatrix is a contiguous rectangular region within a matrix. For example, in a 3x3 matrix, there are many possible submatrices of different sizes and positions.

Example: If the matrix is [[1,1,0],[1,1,0],[0,0,1]], we need to count all rectangular regions that contain only 1s.

Input & Output

Example 1 — Basic Matrix

$ Input: mat = [[1,0,1],[1,1,0],[1,1,0]]

› Output: 4

💡 Note: Valid submatrices are: [1] at (0,0), [1] at (0,2), [1] at (1,0), [1,1] at (1,0)-(1,1), [1] at (2,0), [1] at (2,1)

Example 2 — All Ones

$ Input: mat = [[1,1],[1,1]]

› Output: 9

💡 Note: Four 1x1 submatrices, four 1x2 or 2x1 submatrices, and one 2x2 submatrix

Example 3 — All Zeros

$ Input: mat = [[0,0],[0,0]]

› Output: 0

💡 Note: No submatrix contains all ones

Constraints

1 ≤ m, n ≤ 150
mat[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

Binary matrix with 0s and 1s

Find Submatrices

Identify all rectangular regions with only 1s

Count Total

Return the total count of valid submatrices

Key Takeaway

🎯 Key Insight: Transform into histogram problem - count rectangles efficiently using heights and monotonic stack

Asked in

a Amazon 15 G Google 12

The key insight is to convert this into a histogram problem. For each row, calculate the height of consecutive 1s ending at that position, then count rectangles in the resulting histogram using a monotonic stack. Best approach is DP with Histogram. Time: O(mn), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Submatrices	O(m³n³)	O(1)	Check every possible rectangle position and size
Dynamic Programming with Histogram	O(mn)	O(n)	Convert each row to histogram and count rectangles efficiently

Brute Force - Check All Submatrices — Algorithm Steps

Step 1: Iterate through all possible top-left corners
Step 2: For each top-left, try all possible bottom-right corners
Step 3: Check if the rectangle contains only 1s

Visualization

Tap to expand

Step-by-Step Walkthrough

Pick Corners

Choose top-left and bottom-right corners

Check Content

Verify all cells in rectangle are 1s

Count Valid

Increment count if rectangle is all 1s

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int** mat, int matSize, int* matColSize) {
    if (matSize == 0 || matColSize[0] == 0) return 0;
    
    int m = matSize, n = matColSize[0];
    int count = 0;
    
    // Try all possible top-left corners
    for (int top = 0; top < m; top++) {
        for (int left = 0; left < n; left++) {
            // Try all possible bottom-right corners
            for (int bottom = top; bottom < m; bottom++) {
                for (int right = left; right < n; right++) {
                    // Check if this rectangle has all 1s
                    int allOnes = 1;
                    for (int i = top; i <= bottom && allOnes; i++) {
                        for (int j = left; j <= right && allOnes; j++) {
                            if (mat[i][j] == 0) {
                                allOnes = 0;
                            }
                        }
                    }
                    
                    if (allOnes) count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    // Simple parsing for this example - assumes small matrix
    int mat[3][3] = {{1,0,1},{1,1,0},{1,1,0}};
    int* matArray[3] = {mat[0], mat[1], mat[2]};
    int matColSize[3] = {3, 3, 3};
    
    int result = solution(matArray, 3, matColSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m³n³)

O(m²n²) rectangles × O(mn) to check each rectangle

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

78.0K Views

Medium Frequency

~25 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Submatrices — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler