Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Any rectangle covering every one must reach the topmost, bottommost, leftmost, and rightmost occupied cells. Those four extreme coordinates define a rectangle that already covers all the ones, so there is no reason to extend it farther.

Approach

Scan every grid cell. Whenever a one is found, update the minimum and maximum row indices and the minimum and maximum column indices among all ones seen. Zeros do not affect these boundaries.

After the scan, compute the height as bottom - top + 1 and the width as right - left + 1, then return their product. The additions of one count both boundary rows and columns, including the single-cell case. The problem guarantees at least one one, so all four boundaries are established by the scan.

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        n = len(grid)
        m = len(grid[0])
        top = n
        bottom = 0
        left = m
        right = 0

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    top = min(top, i)
                    bottom = max(bottom, i)
                    left = min(left, j)
                    right = max(right, j)

        return (bottom - top + 1) * (right - left + 1)

Complexity analysis

Let r and c be the grid dimensions. Time: O(r * c). Auxiliary space: O(1).