Maximum size square sub-matrix with all 1s
Problem Statement
Given a binary matrix (containing only 0s and 1s), find the maximum size square sub-matrix that contains all 1s.
Example:
- Input:
matrix = [
[0, 1, 1, 0, 1],
[1, 1, 0, 1, 0],
[0, 1, 1, 1, 0],
[1, 1, 1, 1, 0],
[1, 1, 1, 1, 1]
]
- Output:
3(A 3×3 square of all 1s exists)
Noob-Friendly Explanation
Imagine you have a grid of tiles — some are white (1) and some are black (0). You want to find the biggest square area that is entirely white. You're looking for the largest square where every single tile is white. Think of it like trying to place the biggest square rug possible on only the white tiles.
Approach 1: Brute Force
Intuition
For every cell in the matrix, try all possible square sizes starting from that cell as the top-left corner. Check if all cells in that square are 1. Track the maximum size found.
Algorithm
- For each cell (i, j), try square sizes from 1 up to the maximum possible.
- For each size, check if all cells in the square are 1.
- Track the maximum valid square size.
class Solution {
public static int maxSquareBrute(int[][] matrix) {
int rows = matrix.length;
if (rows == 0) return 0;
int cols = matrix[0].length;
int maxSize = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (matrix[i][j] == 1) {
int maxPossible = Math.min(rows - i, cols - j);
for (int size = 1; size <= maxPossible; size++) {
if (isAllOnes(matrix, i, j, size)) {
maxSize = Math.max(maxSize, size);
} else {
break;
}
}
}
}
}
return maxSize;
}
private static boolean isAllOnes(int[][] matrix, int row, int col, int size) {
for (int i = row; i < row + size; i++) {
for (int j = col; j < col + size; j++) {
if (matrix[i][j] == 0) return false;
}
}
return true;
}
public static void main(String[] args) {
int[][] matrix = {
{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1}
};
System.out.println(maxSquareBrute(matrix)); // Output: 3
}
}Complexity Analysis
- Time Complexity: O(m * n * min(m,n)^2) - for each cell, we check squares up to min(m,n) and each check takes O(size^2)
- Space Complexity: O(1) - no extra space used
Approach 2: Optimal
Intuition
Use dynamic programming. dp[i][j] represents the side length of the largest square with all 1s whose bottom-right corner is at (i, j). Each cell depends on its top, left, and top-left diagonal neighbors.
Algorithm
- Create a
dpmatrix of the same size. - Copy the first row and first column from the original matrix.
- For all other cells where
matrix[i][j] == 1:dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1. - Track the maximum value in the dp matrix.
class Solution {
public static int maxSquare(int[][] matrix) {
int rows = matrix.length;
if (rows == 0) return 0;
int cols = matrix[0].length;
int[][] dp = new int[rows][cols];
int maxSize = 0;
// Copy first column
for (int i = 0; i < rows; i++) {
dp[i][0] = matrix[i][0];
maxSize = Math.max(maxSize, dp[i][0]);
}
// Copy first row
for (int j = 0; j < cols; j++) {
dp[0][j] = matrix[0][j];
maxSize = Math.max(maxSize, dp[0][j]);
}
// Fill the rest
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
if (matrix[i][j] == 1) {
dp[i][j] = Math.min(dp[i - 1][j],
Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
maxSize = Math.max(maxSize, dp[i][j]);
} else {
dp[i][j] = 0;
}
}
}
return maxSize;
}
public static void main(String[] args) {
int[][] matrix = {
{0, 1, 1, 0, 1},
{1, 1, 0, 1, 0},
{0, 1, 1, 1, 0},
{1, 1, 1, 1, 0},
{1, 1, 1, 1, 1}
};
System.out.println(maxSquare(matrix)); // Output: 3
}
}Complexity Analysis
- Time Complexity: O(m * n) - single pass through the matrix
- Space Complexity: O(m * n) - the dp matrix