10. You are given a matrix of MxN boolean values representing a board of free (True) or occupied (False) fields. Find the size of the largest square of free fields. Use C . Algorithm, Question, Explanation, Solution. At toptal-com .
By: Chrysanthus Date Published: 16 Jan 2026
Paradigm
Dynamic Programming will be used for high speed. Dynamic programming is a paradigm for solving problems in an optimized way. It consists of finding solutions for intermediate subproblems, which can be stored and reused for solving the actual problem. Dynamic programming is the best approach for difficult problems that always become trivial once we know the solution for a slightly easier instance of that problem - the intermediate subproblem.
If the intermediate subproblems are not overlapping, then we have just a case of Divide and Conquer.
Many dynamic programming problems involves a two dimensional array, also called a matrix or a table. An attempt to deduce a logical pattern in the content of the 2D array is made, before the code of few number of operations, is written from the pattern.
If the intermediate subproblems are not overlapping, then we have just a case of Divide and Conquer.
Many dynamic programming problems involves a two dimensional array, also called a matrix or a table. An attempt to deduce a logical pattern in the content of the 2D array is made, before the code of few number of operations, is written from the pattern.
Illustration
Consider the following given board matrix:
| i/j | 0 | 1 | 2 | 3 | 4 |
| 0 | false | true | true | true | false |
| 1 | true | true | true | true | true |
| 2 | false | true | true | true | true |
| 3 | false | true | true | true | true |
The largest square of free (true) fields in this matrix is from row 0 to row 2 (inclusive) and from column 1 to column 3 (inclusive). It is not the group from row 1 to row 3 (inclusive) and from column 1 to column 4 (inclusive), as that forms a rectangle and not a square.
The size of the require square above is 3, which is one of the lengths (one of the sides).
The size of the require square above is 3, which is one of the lengths (one of the sides).
Identifying a Square
A field with a True value represents a 1 x 1 square on its own.If a field such as matrix[2][3] has a free (True) field on its left, a free(True) field on its top-left, and a free(True) field on its top, then it is the bottom-right corner of a 2x2 square (2 x 2, means 2 by 2). This particular square (of size 1) happens to be part of the 3 x 3 square above.
If this 2 x 2 square has a single width column of free (True) fields on its left, has a single height row of free (True) fields on its top, and a single free (True) field on its top-left, then that is 3 x 3 square, like the required answer above.
If this 3 x 3 square has a single width column of free (True) fields on its left, has a single height row of free (True) fields on its top, and a single free (True) field on its top-left, then that is 4 x 4 square. There is no 4 x 4 square, or larger, of free fields above.
Similar reasoning applies to 5 x 5 squares, 6 x 6 squares, and so on.
Dynamic Programming Table
A dynamic programming table has to be created with the same number of rows above plus 1, and the same number of columns above plus 1. All the elements of the table are first initialized to 0. The initialized table is:|
dp(i/j) | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 2 | 0 | 0 | 0 | 0 | 0 | 0 |
| 3 | 0 | 0 | 0 | 0 | 0 | 0 |
| 4 | 0 | 0 | 0 | 0 | 0 | 0 |
dp stands for dynamic programming, and refers to the above table. The extra preceding row and extra preceding column, account for the logical situation where the number of rows is 0 and the number of columns is 0. Actually, no matrix would exist, if the number of rows is 0 or if the number of columns is 0.
Final dp Table
The final dynamic programming table for the above given matrix is:
| dp(i/j) | 0 | 1 | 2 | 3 | 4 | 5 |
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 1 | 1 | 0 |
| 2 | 0 | 1 | 1 | 2 | 2 | 1 |
| 3 | 0 | 0 | 1 | 2 | 3 | 2 |
| 4 | 0 | 0 | 1 | 2 | 3 | 3 |
Row 0 in the given matrix is row 1 here = 0 + 1. The rest of the rows follow.
Column 0 in the given matrix is column 1 here = 0 + 1. The rest of the columns follow.
A single cell value of false, means that the square size length of that cell is 0. A single cell value of true, means that the square size length of that cell is 1. So all the values in row 0 in the given matrix are the same as all the values in row 1 in this dp table (excluding the preceding 0). Also, all the values in column 0 in the given matrix are the same as all the values in column 1 in this dp table (excluding the preceding 0).
Within the dp table, a cell value of 0 means that the corresponding cell in the given matrix has false. Within the dp table, a cell value of 1 means that the corresponding cell in the given matrix has true.
Within the dp table, a cell value of 2 means that the corresponding cell in the given matrix has true, and it is the bottom-right corner of a 2 x 2 square. That is a sub-square (one cell) of a 2 x 2 square (four cells). Its left neighbor within the 2 x 2 square should have 1 for a true cell; its top-left neighbor should have 1 for a true cell, and its top neighbor should have 1 for a true cell, forming a 2 x 2 further sub-square (overlapping of big and small squares).
Within the dp table, a cell value of 3 means that the corresponding cell in the given matrix has true, and it is the bottom-right corner of a 3 x 3 square. That is a sub-square (one cell) of a 3 x 3 square (nine cells). Three squares overlapping here! A 3 x 3 square contains a 2 x 2 sub-square which begins at its top-left corner.
The cell with the value 3 should have its left neighbor cell with value 2, to indicate the bottom-right corner of a 2 x 2 square (to its left), or should have 3 indicating the bottom-right corner of a 3 x 3 square, still to its left.
The cell with the value 3 should have its top-left neighbor cell with value 2, to indicate the bottom-right corner of a 2 x 2 square (to its top-left), or should have 3 indicating the bottom-right corner of a 3 x 3 square, still to its top-left.
The cell with the value 3 should have its top neighbor cell with value 2, to indicate the bottom-right corner of a 2 x 2 square to its top, or should have 3 indicating the bottom-right corner of a 3 x 3 square, still to its top.
Similar analysis would continue with 4 x 4, 5 x 5, 6 x 6 squares, and so on.
Note: There is no square with side length that is more than 3, in the given matrix above.
Note: there are actually three squares with side length 3, above. One starts at cell [1][2], having its bottom-right corner at cell [3][4]. Another one starts at cell [2][2], having its bottom right-corner at cell [4][4]. The last one starts at cell [2][3], having its bottom-right corner at cell [4][5]. Refer to the board given matrix above.
Column 0 in the given matrix is column 1 here = 0 + 1. The rest of the columns follow.
A single cell value of false, means that the square size length of that cell is 0. A single cell value of true, means that the square size length of that cell is 1. So all the values in row 0 in the given matrix are the same as all the values in row 1 in this dp table (excluding the preceding 0). Also, all the values in column 0 in the given matrix are the same as all the values in column 1 in this dp table (excluding the preceding 0).
Within the dp table, a cell value of 0 means that the corresponding cell in the given matrix has false. Within the dp table, a cell value of 1 means that the corresponding cell in the given matrix has true.
Within the dp table, a cell value of 2 means that the corresponding cell in the given matrix has true, and it is the bottom-right corner of a 2 x 2 square. That is a sub-square (one cell) of a 2 x 2 square (four cells). Its left neighbor within the 2 x 2 square should have 1 for a true cell; its top-left neighbor should have 1 for a true cell, and its top neighbor should have 1 for a true cell, forming a 2 x 2 further sub-square (overlapping of big and small squares).
Within the dp table, a cell value of 3 means that the corresponding cell in the given matrix has true, and it is the bottom-right corner of a 3 x 3 square. That is a sub-square (one cell) of a 3 x 3 square (nine cells). Three squares overlapping here! A 3 x 3 square contains a 2 x 2 sub-square which begins at its top-left corner.
The cell with the value 3 should have its left neighbor cell with value 2, to indicate the bottom-right corner of a 2 x 2 square (to its left), or should have 3 indicating the bottom-right corner of a 3 x 3 square, still to its left.
The cell with the value 3 should have its top-left neighbor cell with value 2, to indicate the bottom-right corner of a 2 x 2 square (to its top-left), or should have 3 indicating the bottom-right corner of a 3 x 3 square, still to its top-left.
The cell with the value 3 should have its top neighbor cell with value 2, to indicate the bottom-right corner of a 2 x 2 square to its top, or should have 3 indicating the bottom-right corner of a 3 x 3 square, still to its top.
Similar analysis would continue with 4 x 4, 5 x 5, 6 x 6 squares, and so on.
Note: There is no square with side length that is more than 3, in the given matrix above.
Note: there are actually three squares with side length 3, above. One starts at cell [1][2], having its bottom-right corner at cell [3][4]. Another one starts at cell [2][2], having its bottom right-corner at cell [4][4]. The last one starts at cell [2][3], having its bottom-right corner at cell [4][5]. Refer to the board given matrix above.
Filling the dp Table and identifying the Squares
Row 0 in the given matrix is row 1 in the dp table = 0 + 1. The rest of the rows follow.Column 0 in the given matrix is column 1 in the dp table = 0 + 1. The rest of the columns follow.
Each of the cell values of row 0 in the dp table has length size of 0, because no square exists with zero height. Each of the cell values of column 0 in the dp table has length size of 0, because no square exists with zero width.
In the dp table, with the values in row 0 and row 1, column 0 and column 1, in mind (already available), the rest of the cells in the dp table are addressed, row by row, from the top, and from the left of each row.
For each new (current) cell, the value in the left neighboring cell, is compare with the value in the top-left neighboring cell, which is also compared with the value in the top neighboring cell. That is, the values in all these three cells are compared. The value to go into the new (current) cell is the minimum of these three values, plus 1.
For the current cell [2][3], which is the bottom-right corner of a 2 x 2 square, the three cell values are (1, 1, 1). The smallest of these three values is still 1. And the value for cell [2][3] becomes 2 = 1 + 1.
For the current cell [3][4], which is the bottom-right corner of a 3 x 3 square, the three cell values are (2, 2, 2). The smallest of these three values is still 2. And the value for cell [3][4] becomes 3 = 2 + 1.
For the current cell [4][4], which is the bottom-right corner of a 3 x 3 square, the three cell values are (2, 2, 3). The smallest of these three values is 2. And the value for cell [4][4] becomes 3 = 2 + 1.
For the current cell [4][5], which is the bottom-right corner of a 3 x 3 square, the three cell values are (3, 3, 2). The smallest of these three values is 2. And the value for cell [4][5] becomes 3 = 2 + 1.
Strategy
The value in each cell of the dp table is the size length of a square. The square may be a 1 x 1 square, or a 2 x 2 square, or a 3 x3 square, or a 4 x 4 square, or a 5 x 5 square, and so on.The dp table which is an M+1 by N+1 array in the program, is produced, and while it is being produced, the maximum cell value is noted. The highest of these values is the required answer (largest square size).
Before the production of the dp table starts, the largest square size is considered as 0 (for comparison with possible first maximum size that is greater).
The Program
The program is:#include <stdio.h>The output is 3 . Read through the code.
#include <stdbool.h>
// Helper function to find the minimum of three numbers
int min(int a, int b, int c) {
if (a <= b && a <= c)
return a;
if (b <= a && b <= c)
return b;
return c;
}
int largestSquare(bool **board, int M, int N) { //** means 2D array
if (M == 0 || N == 0) {
return 0;
}
int dp[M + 1][N + 1];
int max_size = 0;
// Initialize the dp matrix with zeros
for (int i = 0; i <= M; i++) {
for (int j = 0; j <= N; j++) {
dp[i][j] = 0;
}
}
// principal algorithm
for (int i = 1; i <= M; i++) {
for (int j = 1; j <= N; j++) {
if (board[i - 1][j - 1] > 0) { // not for false
dp[i][j] = min(dp[i][j - 1], dp[i - 1][j - 1], dp[i - 1][j]) + 1;
// Update the overall maximum size found so far
if (dp[i][j] > max_size) {
max_size = dp[i][j];
}
}
}
}
return max_size;
}
int main(int argc, char **argv) {
bool board_matrix[4][5] = {
{false, true, true, true, false},
{true, true, true, true, true},
{false, true, true, true, true},
{false, true, true, true, true}
};
int M = 4;
int N = 5;
// Pointers setup for dynamic allocation simulation
bool* board_ptrs[4];
for (int i = 0; i < M; i++) {
board_ptrs[i] = board_matrix[i];
}
int size = largestSquare(board_ptrs, M, N);
printf("%d\n", size);
return 0;
}