85. Maximal Rectangle

package LeetCode_85

/**
 * 85. Maximal Rectangle
 * https://leetcode.com/problems/maximal-rectangle/
 * Given a rows x cols binary matrix filled with 0‘s and 1‘s,find the largest rectangle containing only 1‘s and return its area.
Example 1:
Input: matrix =[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]]
Output: 6
Explanation: The maximal rectangle is shown in the above picture.

Example 2:
Input: matrix = []
Output: 0

Example 3:
Input: matrix = [["0"]]
Output: 0

Example 4:
Input: matrix = [["1"]]
Output: 1

Example 5:
Input: matrix = [["0","0"]]
Output: 0

Constraints:
1. rows == matrix.length
2. cols == matrix.length
3. 0 <= row, cols <= 200
4. matrix[i][j] is ‘0‘ or ‘1‘.
 * */
class Solution {
    /*
    * solution: DP, update height of each columns,
    * Time:O(m*n*m), Space:O(mn)
    * */
    fun maximalRectangle(matrix: Array<CharArray>): Int {
        var result = 0
        val m = matrix.size
        if (m == 0) {
            return 0
        }
        val n = matrix[0].size
        //dp[i][j]: max length of all 1s end with col[j] at row[i]
        val dp = Array(m) { IntArray(n) }
        for (i in matrix.indices) {
            for (j in matrix[i].indices) {
                //set up height array
                dp[i][j] = if (matrix[i][j] == ‘1‘) {
                    if (j == 0) {
                        1
                    } else {
                        dp[i][j - 1] + 1
                    }
                } else {
                    0
                }
            }
        }
        /*
        for example matrix =
        ["1","0","1","0","0"],
        ["1","0","1","1","1"],
        ["1","1","1","1","1"],
        ["1","0","0","1","0"]]
        heights array:
         1,0,1,0,0,
         1,0,1,2,3,
         1,2,3,4,5,
         1,0,0,1,0,
        * */
        for (i in 0 until m) {
            for (j in 0 until n) {
                var height = Int.MAX_VALUE
                //scan current row, find out minimum value
                for (k in i until m) {
                    height = Math.min(height, dp[k][j])
                    //area = height * width
                    result = Math.max(result, height * (k - i + 1))
                }
            }
        }
        return result
    }
}