# Find the Minimum Area to Cover All Ones I
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-the-minimum-area-to-cover-all-ones-i)
Canonical: https://scaleengineer.com/dsa/problems/find-the-minimum-area-to-cover-all-ones-i
**Data structures:** Array, Matrix
---
## Problem
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:**

![](https://assets.glich.co/dsa/find-the-minimum-area-to-cover-all-ones-i/image0.png)

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:**

![](https://assets.glich.co/dsa/find-the-minimum-area-to-cover-all-ones-i/image1.png)

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
## Multiple Passes
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### 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.

## Single Pass Iteration
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.
**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.
**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.
### Explanation
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.

```java
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;
        int min_col = Integer.MAX_VALUE;
        int max_col = Integer.MIN_VALUE;
        
        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);
                    min_col = Math.min(min_col, c);
                    max_col = Math.max(max_col, c);
                }
            }
        }
        
        // The problem guarantees at least one '1', so the initial values will be updated.
        int height = max_row - min_row + 1;
        int width = max_col - min_col + 1;
        
        return height * width;
    }
}
```
### 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.

# Solutions
### Java

```java
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);
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minimumArea(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    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 = min(x1, i);
          y1 = min(y1, j);
          x2 = max(x2, i);
          y2 = max(y2, j);
        }
      }
    }
    return (x2 - x1 + 1) * (y2 - y1 + 1);
  }
};

```

### Python

```python
class Solution:
    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)

```