Day 27 of 30 days Leetcode Challenge - Maximal Square

Maximal Square

Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Solution

DP with formula : dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1])) when its value is "1"

class Solution {
    func maximalSquare(_ matrix: [[Character]]) -> Int {
        if matrix.count == 0 { return 0 }
        
        var dp = Array(repeating: Array(repeating: 0, count: matrix[0].count), count: matrix.count)
        var result = 0
         
        for i in 0..<matrix.count {
            for j in 0..<matrix[0].count {
                if matrix[i][j] == "1" {
                    
                    if i == 0 || j == 0 {
                        dp[i][j] = 1
                    }else{
                        dp[i][j] = 1 + min(dp[i-1][j-1], min(dp[i-1][j], dp[i][j-1]))   
                    }

                    result = max(result, dp[i][j])
                }
            }
        }
        
        return result * result
    }
}