Medium
You are given a 2D binary array grid
. Find a rectangle with horizontal and vertical sides with the smallest area, such that all the 1’s in grid
lie inside this rectangle.
Return the minimum possible area of the rectangle.
Example 1:
Input: grid = [[0,1,0],[1,0,1]]
Output: 6
Explanation:
The smallest rectangle has a height of 2 and a width of 3, so it has an area of 2 * 3 = 6
.
Example 2:
Input: grid = [[1,0],[0,0]]
Output: 1
Explanation:
The smallest rectangle has both height and width 1, so its area is 1 * 1 = 1
.
Constraints:
1 <= grid.length, grid[i].length <= 1000
grid[i][j]
is either 0 or 1.grid
.import kotlin.math.max
import kotlin.math.min
class Solution {
fun minimumArea(grid: Array<IntArray>): Int {
var xmin = Int.MAX_VALUE
var xmax = -1
var ymin = Int.MAX_VALUE
var ymax = -1
var i = 0
val m = grid.size
val n = grid[0].size
while (i < m) {
for (j in 0 until n) {
if (grid[i][j] == 1) {
xmin = min(xmin, i)
xmax = max(xmax, i)
ymin = min(ymin, j)
ymax = max(ymax, j)
}
}
i++
}
return (xmax - xmin + 1) * (ymax - ymin + 1)
}
}