Valizada's blog

Maximal Square

Another mind blowing solution with dynamic programming to LeetCode problem number 26 from 30 day challenge

Problem statement: Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Input:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

The result is 4 because we are looking for a maximum square of ones. In our example, there are two such squares but all we are interested is the area, 2 by 2.

matrix

To solve, we will use a DP table which will store maximum possible square roots of the given sub matrix. We consider each cell as bottom right element of 2*2 square.

  1. Create empty array of the same dimensions as the matrix
  2. Iterate over all of the elements of the matrix
  3. If on first row or first column, value will remain as it is (0 or 1). There is no way the square can be extended as it is on the edge

For all the other cells, all that matters are ones, zeros cannot increase the size

  1. If cell value is '1', compare left cell, top cell and the cell of the left diagonal. Take the minimum which will tell us the maximum by which the square can be extended, then add 1 (size of the current cell).
  2. Every time the value is updated, compare it against a global max and update

matrix

And here is the solution in Java.

class Solution {
    public int maximalSquare(char[][] m) {
        if(m.length == 0) {
            return 0;
        }
        int max = 0;
        var a = new int[m.length][m[0].length];
        for(int i = 0; i < m.length; i++) {
            for(int j = 0; j < m[0].length; j++) {
                if(i == 0 || j == 0) {
                    a[i][j] = Integer.parseInt(String.valueOf(m[i][j]));
                } else if(m[i][j] == '1') {
                    a[i][j] = Math.min(a[i-1][j-1], 
                    Math.min(a[i][j-1], a[i-1][j])) + 1;
                }
                max = Math.max(max, a[i][j]);
            }
        }
        return max*max;
    }
}