Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Let side[i][j] be the side of the largest all-1 square whose bottom-right corner is (i, j).
  2. 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);
    }
}

Solve Maximal Square online · All practice problems