# One scan beat 80% with O(n) space and O(n^2) space solution

• One Scan initial O(n^2) space solution: beat 80%

If operation is cheap, so I put initial state inside of if(matrix[i][j] == '1').
Whenever it's on the leftmost column or uppermost row, init memory table as 1.

``````public class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int rows = matrix.length;
int cols = matrix[0].length;
int[][] lenMatrix = new int[rows][cols];

int max = 0;
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(matrix[i][j] == '1'){
if(i == 0 || j == 0){
lenMatrix[i][j] = 1;
}else{
lenMatrix[i][j] = Math.min(Math.min(lenMatrix[i-1][j-1],lenMatrix[i][j-1]),lenMatrix[i-1][j]) + 1;
}
max = Math.max(max, lenMatrix[i][j]);
}
}
}

return max*max;
}
}
``````

One scan O(n) solution based on previous solution.

``````public class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
int rows = matrix.length;
int cols = matrix[0].length;
//int[][] lenMatrix = new int[rows][cols];

int[] pre = new int[cols];
int[] cur = new int[cols];

int max = 0;
for(int i = 0; i < rows; i++){
pre = cur;
cur = new int[cols];
for(int j = 0; j < cols; j++){
if(matrix[i][j] == '1'){
if(i == 0 || j == 0){
cur[j] = 1;
}else{
cur[j] = Math.min(Math.min(pre[j], pre[j-1]), cur[j-1]) + 1;
}
max = Math.max(max, cur[j]);
}
}
}

return max*max;
}
}
``````

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