[LeetCode] 221 Maximal Square

 Problem : https://leetcode.com/problems/maximal-square/

This problem is similar to 84. Largest Rectangle in Histogram .

Base on the same idea, we can find the largest square ends on each row.

Time complexity = O ( M * ( N + N ) ),  M = row of the matrix, N = column of the matrix.

class Solution {
    public int maximalSquare(char[][] matrix) {
        int ROW = matrix.length;
        int COLUMN = matrix[0].length;
        
        // rows[i] = the accumulated height of each column base on ith row
        int[][] rows = new int[ROW][COLUMN];
        int result = 0;
        
        for (int y = 0; y < ROW; y++) {
            for (int x = 0; x < COLUMN; x++) {
                if (matrix[y][x] == '1') {
                    rows[y][x] = 1;
                } else {
                    continue;
                }
                
                // increase the height of column x on row y
                if (y > 0 && matrix[y-1][x] == '1') {
                    rows[y][x] += rows[y-1][x];
                }
            }
            
            // find the largest square base on y row.
            result = Math.max(result, squareBaseOnRow(rows[y]));
        }
        
        return result;
    }
    
    /**
    * find the largest square which bottom line is on current row
    */
    int squareBaseOnRow(int[] row) {
        int N = row.length;
        int result = 0;
        
        Stack<Integer> stack = new Stack();
        
        for (int i = 0; i <= N; i++) {
            // add '0' height column in the end to clean the stack
            int currentHeight = i < N ? row[i] : 0;
            
            while (!stack.isEmpty() && row[stack.peek()] > currentHeight) {
                // the highest column so far
                int height = row[stack.pop()];

                // important!  
                // if stack is empty, there is no shorter column in front of it,
                // then the left boundry = 0.
                // otherwise, the left boundry = stack.peek() + 1

                int left = stack.isEmpty() ? 0 : stack.peek() + 1;
                int right = i;

                // because it needs a square ...
                int width = Math.min(height, right - left);
                result = Math.max(result, width * width);
            }
            
            stack.push(i);    
        }
        
        return result;
    }
}

Edited on 12/16/2021. Replaced with the monotonic stack based solution.