dp[i][j] represents the side length of the largest square ending at (i,j). if matrix[i][j] is 1, dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1.
the min ensures we only extend squares that can form a valid larger square. track the maximum side length seen during the dp process.
dp state
dp[i][j] = largest square side ending at (i,j). depends on top, left, and top-left neighbors. only extend if all three allow it.
complexity
O(mn) time and space where m and n are matrix dimensions. can be optimized to O(n) space by using only previous row.