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.Problem Overview: You are given a binary grid and need the smallest axis-aligned rectangle that covers every cell containing 1. The rectangle must include all rows and columns where a 1 appears, and the result is the area of that rectangle.
Approach 1: Brute Force Rectangle Search (O(m3 * n3) time, O(1) space)
The brute force idea checks every possible rectangle in the grid and verifies whether it covers all the 1 cells. You iterate over all pairs of top/bottom rows and left/right columns, then scan the rectangle to confirm whether every 1 lies inside it. This method uses nested loops over the grid dimensions and repeated validation scans. It works but quickly becomes impractical as the grid grows. This approach mainly demonstrates the baseline reasoning before optimizing with better observations about the distribution of 1s in the matrix.
Approach 2: Coordinate Compression / Bounding Box (O(m * n) time, O(1) space)
The key observation: the smallest rectangle covering all 1s is defined by the extreme coordinates where 1 appears. While scanning the grid once, track four values: minRow, maxRow, minCol, and maxCol. Each time you encounter a 1, update these boundaries. After the scan, the rectangle height is maxRow - minRow + 1 and the width is maxCol - minCol + 1. Multiplying them gives the minimum area. The idea resembles coordinate compression because you reduce the relevant search space to the coordinates containing 1. This single pass solution leverages simple iteration over the array-based grid and avoids storing extra structures.
Recommended for interviews: Interviewers expect the bounding box scan. It shows you can translate a spatial constraint into tracked boundaries while iterating through a grid. Mentioning the brute force rectangle enumeration shows you understand the naive search space, but recognizing that only the extreme coordinates matter demonstrates stronger algorithmic thinking.
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.
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.
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.
We can traverse grid, finding the minimum boundary of all 1s, denoted as (x_1, y_1), and the maximum boundary, denoted as (x_2, y_2). Then, the area of the minimum rectangle is (x_2 - x_1 + 1) times (y_2 - y_1 + 1).
The time complexity is O(m times n), where m and n are the number of rows and columns in grid, respectively. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
C#
| 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. |
| Find Minimum and Maximum Boundaries | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Rectangle Search | O(m^3 * n^3) | O(1) | Useful for understanding the full search space of possible rectangles or when explaining the naive baseline in interviews. |
| Coordinate Compression / Bounding Box Scan | O(m * n) | O(1) | Best general solution. Single pass over the grid to track extreme rows and columns containing 1s. |
Find the Minimum Area to Cover All Ones I | Simple Explanation | Leetcode 3195 | codestorywithMIK • codestorywithMIK • 5,913 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