Find the smallest axis-aligned rectangle that contains every cell with value 1 in a binary grid.
Given a binary matrix, determine the minimum area of an axis-aligned rectangle that covers all cells containing 1.
You may choose any rectangle whose sides are parallel to the axes. The rectangle must include every cell with value 1 in the grid, and its area is measured as height × width in cell units.
Your task is to return the minimum possible area of such a rectangle.
Input Format
- A binary matrix
gridof sizem x n. - Each cell contains either
0or1.
Output Format
- Return a single integer: the minimum area of an axis-aligned rectangle covering all
1cells.
Constraints
1 <= m, n- The matrix contains at least one
1. - Cells are indexed by row and column.
- The rectangle must be aligned with the grid axes.
Example 1
Input
grid = [[0,0,1],[0,1,0],[0,0,0]]
Output
4
Explanation
The 1 cells are at positions (0,2) and (1,1). The smallest covering rectangle spans rows 0..1 and columns 1..2, so its area is 2 × 2 = 4.
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.