Maximal square

Challenge

Implement:

int maximal_square(const int *grid, int rows, int cols);

Return the side length of the largest square consisting entirely of 1s in a rows x cols 0/1 matrix (row-major).

Input format

Row-major 0/1 grid, dimensions.

Output format

Side length of the largest all-1 square.

Constraints

dp[i][j] is the side of the largest square ending at (i,j).

Starter code

#include <stddef.h>
/* Side length of the largest all-1 square in a rows x cols 0/1 matrix (row-major). */
int maximal_square(const int *grid,int rows,int cols){ (void)grid;(void)rows;(void)cols; return 0; }

Common mistakes

Taking the max instead of the min of the three neighbours (that overcounts).

Edge cases to handle

All zeros -> 0.

Background lessons

• Matrix DP