3195. Find the Minimum Area to Cover All Ones I

Posted on Edited on In

3195. Find the Minimum Area to Cover All Ones I

Description

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:

1
2
3
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:

1
2
3
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.

Hints/Notes

  • Weekly Contest 403

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        int minI = INT_MAX, minJ = INT_MAX, maxI = INT_MIN, maxJ = INT_MIN;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == 1) {
                    minI = min(minI, i);
                    minJ = min(minJ, j);
                    maxI = max(maxI, i);
                    maxJ = max(maxJ, j);
                }
            }
        }
        return (maxI - minI + 1) * (maxJ - minJ + 1);
    }
};