Find the Minimum Area to Cover All Ones I

Med

#2838Time: O(M * N), where M is the number of rows and N is the number of columns. The grid is traversed twice, so the total operations are proportional to `2 * M * N`, which simplifies to O(M * N).Space: O(1). We only use a few integer variables to store the boundary coordinates, which is constant extra space.

Data structures

Array Matrix

Prompt

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.
The input is generated such that there is at least one 1 in grid.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach breaks down the problem into two distinct steps: first finding the vertical boundaries (topmost and bottommost rows with a '1') and then finding the horizontal boundaries (leftmost and rightmost columns with a '1'). This is achieved by iterating through the grid multiple times.

Algorithm

Initialize min_row to a very large number and max_row to a very small number.
Iterate through every cell (r, c) of the grid. If grid[r][c] is 1, update min_row = min(min_row, r) and max_row = max(max_row, r).
After the first pass, min_row and max_row will hold the boundaries for the height of the rectangle.
Initialize min_col to a very large number and max_col to a very small number.
Iterate through the grid a second time. If grid[r][c] is 1, update min_col = min(min_col, c) and max_col = max(max_col, c).
After the second pass, min_col and max_col will hold the boundaries for the width.
The height of the rectangle is max_row - min_row + 1, and the width is max_col - min_col + 1.
The final area is the product of the height and width.

Walkthrough

The core idea is to first determine the range of rows that contain at least one '1', and then, in a separate pass, determine the range of columns. While this correctly solves the problem, it's less efficient as it reads every cell in the grid twice.

1class Solution {2    public int minimumArea(int[][] grid) {3        int rows = grid.length;4        int cols = grid[0].length;5        6        int min_row = Integer.MAX_VALUE;7        int max_row = Integer.MIN_VALUE;8        9        // First pass to find row boundaries10        for (int r = 0; r < rows; r++) {11            for (int c = 0; c < cols; c++) {12                if (grid[r][c] == 1) {13                    min_row = Math.min(min_row, r);14                    max_row = Math.max(max_row, r);15                }16            }17        }18        19        int min_col = Integer.MAX_VALUE;20        int max_col = Integer.MIN_VALUE;21        22        // Second pass to find column boundaries23        for (int r = 0; r < rows; r++) {24            for (int c = 0; c < cols; c++) {25                if (grid[r][c] == 1) {26                    min_col = Math.min(min_col, c);27                    max_col = Math.max(max_col, c);28                }29            }30        }31        32        // Since there's at least one '1', we don't need to handle the empty case.33        int height = max_row - min_row + 1;34        int width = max_col - min_col + 1;35        36        return height * width;37    }38}

Complexity

Time

O(M * N), where M is the number of rows and N is the number of columns. The grid is traversed twice, so the total operations are proportional to `2 * M * N`, which simplifies to O(M * N).

Space

O(1). We only use a few integer variables to store the boundary coordinates, which is constant extra space.

Trade-offs

Pros

Conceptually simple as it separates the problem of finding row and column boundaries into two distinct loops.

Cons

Inefficient because it requires traversing the entire grid twice, performing redundant work compared to a single-pass solution.

This is the optimal approach. Instead of iterating through the grid multiple times, we can find all four boundaries (top, bottom, left, right) in a single pass. This minimizes the number of operations required by checking and updating all boundary coordinates simultaneously.

Algorithm

Initialize min_row, min_col to a very large value (e.g., Integer.MAX_VALUE).
Initialize max_row, max_col to a very small value (e.g., Integer.MIN_VALUE).
Iterate through every cell (r, c) of the grid just once.
Whenever a cell grid[r][c] is 1, update all four boundary variables:
- min_row = min(min_row, r)
- max_row = max(max_row, r)
- min_col = min(min_col, c)
- max_col = max(max_col, c)
After the loop, calculate the height as max_row - min_row + 1 and width as max_col - min_col + 1.
Return the product of height and width.

Walkthrough

The most efficient way to solve this problem is to find the minimum and maximum row and column indices of all cells containing a '1' in a single traversal of the grid. We maintain four variables to track the extremities of the '1's. As we iterate, if we find a '1', we update these boundaries. After checking all cells, these four variables will perfectly define the smallest bounding box.

1class Solution {2    public int minimumArea(int[][] grid) {3        int rows = grid.length;4        int cols = grid[0].length;5        6        int min_row = Integer.MAX_VALUE;7        int max_row = Integer.MIN_VALUE;8        int min_col = Integer.MAX_VALUE;9        int max_col = Integer.MIN_VALUE;10        11        for (int r = 0; r < rows; r++) {12            for (int c = 0; c < cols; c++) {13                if (grid[r][c] == 1) {14                    min_row = Math.min(min_row, r);15                    max_row = Math.max(max_row, r);16                    min_col = Math.min(min_col, c);17                    max_col = Math.max(max_col, c);18                }19            }20        }21        22        // The problem guarantees at least one '1', so the initial values will be updated.23        int height = max_row - min_row + 1;24        int width = max_col - min_col + 1;25        26        return height * width;27    }28}

Complexity

Time

O(M * N), where M is the number of rows and N is the number of columns. We traverse the grid exactly once. This is the most efficient time complexity possible as we must inspect every cell in the worst case.

Space

O(1). We only use a constant number of variables to store the boundaries, regardless of the input grid size.

Trade-offs

Pros

Optimal time complexity, as each cell is visited only once.
Optimal space complexity, using only a constant amount of extra space.
Simple and straightforward to implement.

Cons

There are no significant drawbacks to this approach; it is the standard and best solution for this problem.

Solutions

Solution

1class Solution {2public3  int minimumArea(int[][] grid) {4    int m = grid.length, n = grid[0].length;5    int x1 = m, y1 = n;6    int x2 = 0, y2 = 0;7    for (int i = 0; i < m; ++i) {8      for (int j = 0; j < n; ++j) {9        if (grid[i][j] == 1) {10          x1 = Math.min(x1, i);11          y1 = Math.min(y1, j);12          x2 = Math.max(x2, i);13          y2 = Math.max(y2, j);14        }15      }16    }17    return (x2 - x1 + 1) * (y2 - y1 + 1);18  }19}

1class Solution {2public:3  int minimumArea(vector<vector<int>> &grid) {4    int m = grid.size(), n = grid[0].size();5    int x1 = m, y1 = n;6    int x2 = 0, y2 = 0;7    for (int i = 0; i < m; ++i) {8      for (int j = 0; j < n; ++j) {9        if (grid[i][j] == 1) {10          x1 = min(x1, i);11          y1 = min(y1, j);12          x2 = max(x2, i);13          y2 = max(y2, j);14        }15      }16    }17    return (x2 - x1 + 1) * (y2 - y1 + 1);18  }19};

1class Solution:2    def minimumArea(self, grid: List[List[int]]) -> int: x1 = y1 = inf x2 = y2 = - inf for i, row in enumerate(grid): for j, x in enumerate(row): if x == 1: x1 = min(x1, i) y1 = min(y1, j) x2 = max(x2, i) y2 = max(y2, j) return (x2 - x1 + 1) * (y2 - y1 + 1)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem