Problem

You are given a 2D binary array grid. Find a rectangle with horizontal and vertical sides with thesmallest area, such that all the 1’s in grid lie inside this rectangle.

Return the minimum possible area of the rectangle.

Examples

Example 1

$$ \Huge \begin{array}{|c|c|c|} \hline \colorbox{pink} 0 & \colorbox{pink} 1 & \colorbox{pink} 0 \\ \hline \colorbox{pink} 1 & \colorbox{pink} 0 & \colorbox{pink} 1 \\ \hline \end{array} $$

1
2
3
4

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

$$ \Huge \begin{array}{|c|c|} \hline \colorbox{pink} 1 & 0 \\ \hline 0 & 0 \\ \hline \end{array} $$

1
2
3
4

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.

Solution

Method 1 – Bounding Rectangle

Intuition

To cover all 1’s in the grid with the smallest rectangle, we need to find the minimum and maximum row and column indices where a 1 appears. The rectangle defined by these bounds will cover all 1’s, and its area is simply the product of its height and width.

Approach

  1. Initialize min_row, max_row, min_col, and max_col to extreme values.
  2. Iterate through the grid:
    • For each cell with value 1, update the min/max row and column indices.
  3. If no 1’s are found, return 0.
  4. Otherwise, the area is (max_row - min_row + 1) * (max_col - min_col + 1).

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

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

func minimumArea(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    minr, maxr, minc, maxc := m, -1, n, -1
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                if i < minr { minr = i }
                if i > maxr { maxr = i }
                if j < minc { minc = j }
                if j > maxc { maxc = j }
            }
        }
    }
    if minr > maxr { return 0 }
    return (maxr-minr+1)*(maxc-minc+1)
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int minimumArea(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int minr = m, maxr = -1, minc = n, maxc = -1;
        for(int i=0;i<m;++i) for(int j=0;j<n;++j) if(grid[i][j]==1) {
            minr = Math.min(minr, i); maxr = Math.max(maxr, i);
            minc = Math.min(minc, j); maxc = Math.max(maxc, j);
        }
        if(minr>maxr) return 0;
        return (maxr-minr+1)*(maxc-minc+1);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    fun minimumArea(grid: Array<IntArray>): Int {
        val m = grid.size; val n = grid[0].size
        var minr = m; var maxr = -1; var minc = n; var maxc = -1
        for (i in 0 until m) for (j in 0 until n) if (grid[i][j]==1) {
            minr = minOf(minr, i); maxr = maxOf(maxr, i)
            minc = minOf(minc, j); maxc = maxOf(maxc, j)
        }
        if (minr > maxr) return 0
        return (maxr-minr+1)*(maxc-minc+1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def minimumArea(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        minr, maxr, minc, maxc = m, -1, n, -1
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    minr = min(minr, i)
                    maxr = max(maxr, i)
                    minc = min(minc, j)
                    maxc = max(maxc, j)
        if minr > maxr:
            return 0
        return (maxr-minr+1)*(maxc-minc+1)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn minimum_area(grid: Vec<Vec<i32>>) -> i32 {
        let m = grid.len(); let n = grid[0].len();
        let (mut minr, mut maxr, mut minc, mut maxc) = (m as i32, -1, n as i32, -1);
        for i in 0..m {
            for j in 0..n {
                if grid[i][j]==1 {
                    minr = minr.min(i as i32); maxr = maxr.max(i as i32);
                    minc = minc.min(j as i32); maxc = maxc.max(j as i32);
                }
            }
        }
        if minr > maxr { return 0; }
        (maxr-minr+1)*(maxc-minc+1)
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    minimumArea(grid: number[][]): number {
        const m = grid.length, n = grid[0].length;
        let minr = m, maxr = -1, minc = n, maxc = -1;
        for(let i=0;i<m;++i) for(let j=0;j<n;++j) if(grid[i][j]===1) {
            minr = Math.min(minr, i); maxr = Math.max(maxr, i);
            minc = Math.min(minc, j); maxc = Math.max(maxc, j);
        }
        if(minr>maxr) return 0;
        return (maxr-minr+1)*(maxc-minc+1);
    }
}

Complexity

  • ⏰ Time complexity: O(m*n), where m and n are the grid dimensions.
  • 🧺 Space complexity: O(1), only a few variables are used.