My Java Solution O(mn)


  • 4
    Q

    Basic idea is to iterate over all columns and rows of a matrix (starting with i=j=1). If value in a cell>0 and cells to the north, west, and north-west are >0, pick smallest value of those 3 cells, take it's square root, add 1, and assign square of new value to current cell. For example given matrix

    1   1   1   1   1   1
    1   1   1   0   1   1
    1   1   1   1   1   1
    1   1   1   1   1   1
    1   1   1   1   1   1
    1   1   1   1   0   1
    
    We get:
    
    1   1   1   1   1   1
    1   4   4   0   1   4
    1   4   9   1   1   4
    1   4   9   4   4   4
    1   4   9   9   9   9
    1   4   9  16   0   1
    

    Our answer is the largest value in new matrix: 16

    public class Solution {
        static int[] squares = new int[1001];
        static{
            for (int i=0;i<=1000;i++){
                squares[i] = i*i;
            }
        } 
            
        public int maximalSquare(char[][] matrix) {
            if (matrix == null || matrix.length == 0){
                return 0;
            }
            int result = 0;
            
            int[][] intMatrix = new int[matrix.length][matrix[0].length];
        	for (int i=0;i<matrix.length;i++){
        		for (int j=0;j<matrix[0].length;j++){
        		    int val = matrix[i][j]-'0';
        		    if (val == 1){
        		        result = 1;
        		    }
        			intMatrix[i][j] = val;
        		}
        	}
            
            for (int i = 1; i<intMatrix.length;i++){
                for (int j=1; j<intMatrix[0].length;j++){
                    if (intMatrix[i][j]!=0){
                        int val1 = intMatrix[i][j-1];
                        int val2 = intMatrix[i-1][j];
                        int val3 = intMatrix[i-1][j-1];
                        int min1 = Math.min(val1, val2);
                        int min = Math.min(min1, val3);
                        if (min!=0){
                            int index = (int)Math.sqrt(min);
                            intMatrix[i][j] = (int)squares[index+1];
                            if (intMatrix[i][j]>result){
                                result = intMatrix[i][j];
                            }
                        }
                    }
                }
            }
            return result;
        }
    }

  • 2
    J

    Inspired by your idea. I made a little modifications. Seems a little faster. 384ms.

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            if(matrix == null || matrix.length == 0) {
                return 0;
            }
            
            int res = 0;
            int m = matrix.length;
            int n = matrix[0].length;
            int[][] sq = new int[m][n];
            
            for(int i = 0; i < m; i++) {
                if(matrix[i][0] == '1') {
                    sq[i][0] = 1;
                    res = 1;
                } else {
                    sq[i][0] = 0;
                }
            }
            for(int j = 0; j < n; j++) {
                if(matrix[0][j] == '1') {
                    sq[0][j] = 1;
                    res = 1;
                } else {
                    sq[0][j] = 0;
                }
            }
            
            for(int i = 1; i < m; i++) {
                for(int j = 1; j < n; j++) {
                   if(matrix[i][j] == '1') {
                       int min = Math.min(Math.min(sq[i][j-1], sq[i-1][j]), sq[i-1][j-1]);
                       //if(min != 0) {
                           sq[i][j] = (int)Math.pow(Math.sqrt(min)+1, 2);
                           res = Math.max(res, sq[i][j]);
                       //}
                   }
                }
            }
            
            return res;
        }
    } 

  • 0
    Q

    Thanks, good observation that we only need to populate first row, and first column in int[][] matrix, and 'if (min !=0) {' check can be removed, as we need to set sq[i][j] to 1 since we didn't set it initially. Also you don't need 'else {sq[i][0] = 0; }', and 'else {sq[0][j] = 0;}; blocks as 0 is default value for int.


  • 0
    Z
    Here is my poor solution, but also AC , hoho
    
    
    
    public int maximalSquare(char[][] input) {
        if(input==null || input.length==0 || input[0].length==0) return 0;
        int[][] matrix=preHandle(transferToInt(input));
        int max=0;
        for(int i=0;i<matrix.length;++i){
            int t=getMaxArea(matrix[i]);
            if(t>max) max=t;
        }
        return max;
    }
    public int[][] transferToInt(char[][] input){
        int[][] result=new int[input.length][];
        for(int i=0;i<input.length;++i){
            result[i]=new int[input[0].length];
            for(int j=0;j<input[0].length;++j)
                result[i][j]=Integer.valueOf(input[i][j]+"");
        }
        return result;
    }
    public int[][] preHandle(int[][] matrix){
        for(int i=1;i<matrix.length;++i){
            for(int j=0;j<matrix[0].length;++j){
                if(matrix[i][j]==1)
                    matrix[i][j]+=matrix[i-1][j];
            }
        }
        return matrix;
    }
    public int getMaxArea(int[] arr){
        int maxLevel=1;
        for(int i=0;i<arr.length;++i)
            if(arr[i]>maxLevel)
                maxLevel=arr[i];
        int maxArea=0;
        for(int i=1;i<=maxLevel;++i){
            int maxLength=0,tmpLength=0;
            for(int j=0;j<arr.length;++j){
                if(arr[j]>=i){
                    tmpLength++;
                }else{
                    if(tmpLength>maxLength) maxLength=tmpLength;
                    tmpLength=0;
                }
            }
            if(tmpLength>maxLength) maxLength=tmpLength;
            int minEdge=Math.min(maxLength,i); // just change here , it will work with rectangular.  ;)
            if(minEdge*minEdge>maxArea) maxArea=minEdge*minEdge;
        }
        return maxArea;
    }

  • 0
    D

    Also inspired by your logic I made it run even faster. 348ms. You don't need to square as you proceed with the algorithm. You only need to do once when you find the length of one side of the largest square then return the square of that

    public class Solution {
        public int maximalSquare(char[][] matrix) {
            
            if(matrix == null || matrix.length == 0){
                return 0;
            }
            
            int row = matrix.length;
            int col = matrix[0].length;
            
            int[][] counts = new int[row][col];
            
            int currentLargestVal = 0;
            
            for(int x=0; x<row; x++){
                counts[x][0] = getVal(matrix[x][0]);
                if(counts[x][0] == 1){
                    currentLargestVal = 1;
                }
            }
            
            for(int x=1; x<col; x++){
                counts[0][x] = getVal(matrix[0][x]);
                if(counts[0][x] == 1){
                    currentLargestVal = 1;
                }
            }
            
            
            for(int x=1; x<row; x++){
                for(int y=1; y<col; y++){
                    int val = getVal(matrix[x][y]);
                    if(val == 1){
                        
                        int nw = counts[x-1][y-1];
                        int w = counts[x][y-1];
                        int n = counts[x-1][y];
                        
                        int newVal;
                        
                        newVal = Math.min(nw, n);
                        newVal = Math.min(newVal, w) + 1;
    
                        counts[x][y] = newVal;
                        
                        currentLargestVal = Math.max(currentLargestVal, newVal);
                    }
                }
            }
            
            if(currentLargestVal == 0){
                return 0;
            }
            
            return (int) Math.pow(currentLargestVal, 2);        
        }
        
        public int getVal(char c){
            if(c == '1'){
                return 1;
            }else{
                return 0;
            }
            
        }
    }
    

Log in to reply
 

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