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.grid.This approach involves iterating through the entire grid to determine the minimum and maximum rows and columns that contain a '1'. By doing this, we can define the top-left and bottom-right corners of the smallest rectangle that can encompass all the '1's. The approach is direct and fairly simple, although it may not be the most efficient for larger grids.
In this C implementation, we scan the entire grid to find the minimum and maximum indices of the rows and columns containing '1's. Once found, we calculate the rectangle's area by using the differences between the maximum and minimum coordinates, plus 1 to account for a zero-based index.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. We traverse each element of the grid once.
Space Complexity: O(1). No additional space is used except for a few integers.
Coordinate Compression is an optimized method where instead of examining the entire matrix, you 'compress' rows and columns by recording only the necessary indices where a '1' appears. This can potentially reduce the runtime when there are sizable sections of zero-filled areas.
This Python solution implements coordinate compression by tracking only those rows and columns which contain '1's. Using list comprehensions and Python's set operations, the coordinates are efficiently assembled, and the enclosing area is calculated based on these condensed results.
Java
Time Complexity: O(n * m), in the worst case when there's a '1' in each row and column, degenerating to complete scan.
Space Complexity: O(n + m) for storing the compressed row and column indices.
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. We traverse each element of the grid once. |
| Coordinate Compression Approach | Time Complexity: O(n * m), in the worst case when there's a '1' in each row and column, degenerating to complete scan. |
How to EASILY solve LeetCode problems • NeetCode • 427,763 views views
Watch 9 more video solutions →Practice Find the Minimum Area to Cover All Ones I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor