Problem Statement in English

You’re given a 2D binary grid consisting of 0s and 1s. Your task is to find the minimum area of a rectangle that can cover all the 1s in the grid.

Approach

What we really need to do is figure out the length and breadth of the smallest rectangle possible which can fit all the 1s inside it.

To do this, we can iterate through the grid and keep track of the minimum and maximum row and column indices that contain 1s. The area of the rectangle can then be calculated using these indices.

Solution in Python


class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        # leftmost column
        left = cols
        # rightmost column
        right = 0
        # topmost row
        top = rows
        # bottommost row
        bottom = 0

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

        breadth = right - left + 1
        height = bottom - top + 1

        return breadth * height

Complexity

  • Time: $O(m * n)$
    Where $m$ is the number of rows and $n$ is the number of columns in the grid.

  • Space: $O(1)$
    Since we are using a constant amount of space to store the indices, the space complexity is constant.

And we are done.