Find the Minimum Area to Cover All Ones I
MedPrompt
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 <= 1000grid[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_rowto a very large number andmax_rowto a very small number. - Iterate through every cell
(r, c)of the grid. Ifgrid[r][c]is 1, updatemin_row = min(min_row, r)andmax_row = max(max_row, r). - After the first pass,
min_rowandmax_rowwill hold the boundaries for the height of the rectangle. - Initialize
min_colto a very large number andmax_colto a very small number. - Iterate through the grid a second time. If
grid[r][c]is 1, updatemin_col = min(min_col, c)andmax_col = max(max_col, c). - After the second pass,
min_colandmax_colwill hold the boundaries for the width. - The height of the rectangle is
max_row - min_row + 1, and the width ismax_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.
class Solution { public int minimumArea(int[][] grid) { int rows = grid.length; int cols = grid[0].length; int min_row = Integer.MAX_VALUE; int max_row = Integer.MIN_VALUE; // First pass to find row boundaries for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == 1) { min_row = Math.min(min_row, r); max_row = Math.max(max_row, r); } } } int min_col = Integer.MAX_VALUE; int max_col = Integer.MIN_VALUE; // Second pass to find column boundaries for (int r = 0; r < rows; r++) { for (int c = 0; c < cols; c++) { if (grid[r][c] == 1) { min_col = Math.min(min_col, c); max_col = Math.max(max_col, c); } } } // Since there's at least one '1', we don't need to handle the empty case. int height = max_row - min_row + 1; int width = max_col - min_col + 1; return height * width; }}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.
Solutions
Solution
class Solution {public int minimumArea(int[][] grid) { int m = grid.length, n = grid[0].length; int x1 = m, y1 = n; int x2 = 0, y2 = 0; for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { if (grid[i][j] == 1) { x1 = Math.min(x1, i); y1 = Math.min(y1, j); x2 = Math.max(x2, i); y2 = Math.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.