2D Prefix Sum Interview Pattern | 221 Maximal Square

Last problem on Prefix Sum Interview Pattern!
This one uses Binary Search on Answer as well.

00:00-01:40 Problem Introduction
01:41-04:20 Brute Force
04:21-10:30 Prefix Sum for O(N^3)
10:31-14:21 Binary Search on Answer
14:22-21:18 Code

[fomoCoder]

this was surely not a medium question :P BS on answers + prefixSum

[dayashankarlakhotia]

public int maximalSquare (char[][]matrix){
int m=matrix.length, n=matrix[0].length;
int[]dp=new int[n];
maxLen=0, prev=0;
for(int i=0;i<m;++i)
for(int j=0;j<n;++j)
int cur=dp[j];

dp[j]=matrix[i][j]=='1'?1:0;
else
dp[j]=Math.min(prev, Math.min(dp[j], dp[j-1]))+1;
maxLen=Math.max(maxLen, dp[j]);
prev=cur;
}
return maxLen*maxLen;
}
tc=(m*n);
sc=0(n);