Count Square Submatrices with All Ones - Practice Coding Problems

Count Square Submatrices with All Ones - Problem

Given a m × n matrix of ones and zeros, return how many square submatrices have all ones.

A square submatrix is a contiguous block of cells that forms a square shape (equal width and height). You need to count all possible squares of any size (1×1, 2×2, 3×3, etc.) where every cell in the square contains the value 1.

Input & Output

Example 1 — Basic 3×3 Matrix

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

› Output: 9

💡 Note: Count squares of all sizes: 6 squares of size 1×1, 2 squares of size 2×2, and 1 square of size 3×3 (but blocked by the 0). Total = 6 + 2 + 0 = 8. Wait, let me recalculate: 1×1 squares at positions where matrix[i][j]=1 gives us 8 squares. 2×2 squares: top-left corners at (0,0) and (0,1) both fail due to the 0 at (1,1). Actually, only 1×1 squares work, so 8 total.

Example 2 — All Ones

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

› Output: 5

💡 Note: 4 squares of size 1×1 + 1 square of size 2×2 = 5 total squares

Example 3 — Single Row

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

› Output: 2

💡 Note: Only 1×1 squares possible: at positions (0,0) and (0,2) where value is 1

Constraints

1 ≤ matrix.length ≤ 300
1 ≤ matrix[0].length ≤ 300
matrix[i][j] is 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

2D matrix with 0s and 1s

Find Squares

Identify all square regions with only 1s

Count Total

Sum squares of all sizes: 1×1, 2×2, 3×3, etc.

Key Takeaway

🎯 Key Insight: Use DP where dp[i][j] = size of largest square ending at (i,j), then sum all dp values

Asked in

G Google 45 a Amazon 38 M Microsoft 32

The key insight is that dp[i][j] represents the side length of the largest square ending at position (i,j), and the total count equals the sum of all dp values. Best approach uses Dynamic Programming with recurrence dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. Time: O(m×n), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Dynamic Programming - Build Squares	O(m × n)	O(m × n)	Use DP to track the largest square ending at each position
Brute Force - Check All Squares	O(m² × n² × min(m,n))	O(1)	Try every possible square position and size, checking if all cells are 1

Dynamic Programming - Build Squares — Algorithm Steps

Create DP table same size as matrix
Fill first row and column based on matrix values
For each cell, calculate max square size using recurrence relation
Sum all DP values to get total count

Visualization

Tap to expand

Step-by-Step Walkthrough

DP Table

Create table to store max square size at each position

Recurrence

dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

Count

Sum all dp values to get total squares

Code -

solution.c — C

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

int min3(int a, int b, int c) {
    int min_ab = (a < b) ? a : b;
    return (min_ab < c) ? min_ab : c;
}

int solution(int** matrix, int m, int n) {
    if (m == 0 || n == 0) return 0;
    
    int** dp = (int**)malloc(m * sizeof(int*));
    for (int i = 0; i < m; i++) {
        dp[i] = (int*)calloc(n, sizeof(int));
    }
    
    int totalCount = 0;
    
    // Fill the DP table
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (matrix[i][j] == 1) {
                if (i == 0 || j == 0) {
                    dp[i][j] = 1;
                } else {
                    // The size of the largest square ending at (i,j)
                    dp[i][j] = min3(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1;
                }
                
                // Add the count of squares ending at (i,j)
                totalCount += dp[i][j];
            }
        }
    }
    
    // Free memory
    for (int i = 0; i < m; i++) {
        free(dp[i]);
    }
    free(dp);
    
    return totalCount;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    
    // Simple parsing for 2D array
    int matrix[20][20];
    int m = 0, n = 0;
    
    char* ptr = strchr(line, '[');
    if (ptr) ptr++;
    
    while (ptr && *ptr) {
        if (*ptr == '[') {
            ptr++;
            n = 0;
            while (*ptr && *ptr != ']') {
                if (*ptr >= '0' && *ptr <= '9') {
                    matrix[m][n++] = *ptr - '0';
                }
                ptr++;
            }
            m++;
        }
        if (*ptr) ptr++;
    }
    
    // Convert to proper 2D array for function call
    int* rows[20];
    for (int i = 0; i < m; i++) {
        rows[i] = matrix[i];
    }
    
    int result = solution(rows, m, n);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n)

Single pass through the matrix with constant work per cell

✓ Linear Growth

Space Complexity

O(m × n)

DP table of same size as input matrix

⚡ Linearithmic Space

52.0K Views

Medium Frequency

~15 min Avg. Time

1.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

Dynamic Programming - Build Squares — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler