Java In place Solution beats 98.5%, O(n) time


  • 0
    T

    Similar idea as DP.

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
                return 0;
            }
    
            int m = matrix.length, n = matrix[0].length;
    
            for (int i = 1; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    if (matrix[i][j] == '1') {
                        int check = Math.min(matrix[i][j - 1], Math.min(matrix[i - 1][j], matrix[i - 1][j - 1]));
                        matrix[i][j] = check == '0' ? '1' : (char) (check + 1);
                    }
                }
            }
            
            char max = '0';
            
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    max = max - matrix[i][j] > 0 ? max : matrix[i][j];
                }
            }
            
            return (max - '0') * (max - '0');
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.