Practice › Dynamic Programming
Maximal Square
Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft, Apple
Print the area of the largest square containing only 1s in the binary matrix.
Input
First line: r c. Next r lines: c values (0 or 1).
Output
The area of the largest all-1 square.
Constraints
- 1 ≤ r, c ≤ 300
side[i][j] = 1 + min(side[i−1][j], side[i][j−1], side[i−1][j−1]) when the cell is 1 — the largest square whose bottom-right corner is (i, j).
Example 1
Input
4 5 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0
Output
4
Example 2
Input
1 1 0
Output
0
Hints
- Let side[i][j] be the side of the largest all-1 square whose bottom-right corner is (i, j).
- If the cell is 1: side[i][j] = 1 + min(side[i−1][j], side[i][j−1], side[i−1][j−1]). The answer is the largest side, squared.
Approach
A square of side k ending at (i, j) needs squares of side k − 1 ending at the cell above, to the left, and diagonally up-left — so the limiting one is the minimum of the three. Cells with 0 get 0. Keep only the previous row; print best² because the question asks for the area.
Complexity: O(r · c) time · O(c) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int R, C;
cin >> R >> C;
vector<int> prev(C + 1, 0), cur(C + 1, 0);
int best = 0;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
int x;
cin >> x;
cur[j] = x ? 1 + min({prev[j], cur[j - 1], prev[j - 1]}) : 0;
best = max(best, cur[j]);
}
swap(prev, cur);
}
cout << (long long)best * best << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
R, C = data[0], data[1]
g = data[2:]
prev, best = [0] * (C + 1), 0
for i in range(R):
cur = [0] * (C + 1)
for j in range(1, C + 1):
if g[i * C + j - 1]:
cur[j] = 1 + min(prev[j], cur[j - 1], prev[j - 1])
best = max(best, cur[j])
prev = cur
print(best * best)Java solution
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) throws IOException {
StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
in.nextToken();
int R = (int) in.nval;
in.nextToken();
int C = (int) in.nval;
int[] prev = new int[C + 1], cur = new int[C + 1];
int best = 0;
for (int i = 1; i <= R; i++) {
for (int j = 1; j <= C; j++) {
in.nextToken();
cur[j] = (int) in.nval == 1 ? 1 + Math.min(prev[j], Math.min(cur[j - 1], prev[j - 1])) : 0;
best = Math.max(best, cur[j]);
}
int[] t = prev; prev = cur; cur = t;
}
System.out.println((long) best * best);
}
}