Find the Minimum Area to Cover All Ones I solution and explanation
Google
9 more videos on this problem
Find the Minimum Area to Cover All Ones I | Simple Explanation | Leetcode 3195 | codestorywithMIKcodestorywithMIK · 12:11 · 6K views
Find the Minimum Area to Cover All Ones I | Leetcode 3195 | MatrixTechdose · 12:42 · 1K views
3195. Find the Minimum Area to Cover All Ones I | Leetcode Daily - PythonLeetcode Daily · 5:13 · 271 views
Find the Minimum Area to Cover All Ones I | LeetCode 3195 | Array | Matrix | Google SalesforceCode Harmony · 15:36 · 205 views
Find the Minimum Area to Cover All Ones I | LeetCode 3195 - Pythonimpoldev · 6:50 · 195 views
Leetcode 3195 🔥 Find the Minimum Area to Cover All Ones I | DCC Solution + O(mn) Logic Study Placement · 10:37 · 152 views
3195 Find the Minimum Area to Cover All Ones I | Leetcode | Solution | JavaV-Solve · 10:37 · 103 views
LeetCode 3195: Find the Minimum Area to Cover All Ones I | Java Solution | Grid TraversalCode Scribbler · 6:49 · 50 views
3195 Find the Minimum Area to Cover All Ones I | Leetcode Daily | GridTechBits by Vismay · 7:42 · 49 views
Day 733 | Leetcode 3195 | Find the Minimum Area to Cover All Ones I - Clear thought processCode with AR · 13:53 · 44 views
The 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:
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.- The input is generated such that there is at least one 1 in
grid.
Approach overview
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.
Approach 1: Brute Force Approach
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.
def minArea(grid):
min_row, max_row = len(grid), -1
min_col, max_col = len(grid[0]), -1
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == 1:
min_row = min(min_row, i)
max_row = max(max_row, i)
min_col = min(min_col, j)
max_col = max(max_col, j)
return (max_row - min_row + 1) * (max_col - min_col + 1)class Solution {
public int minArea(int[][] grid) {
int minRow = grid.length, maxRow = -1;
int minCol = grid[0].length, maxCol = -1;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
minRow = Math.min(minRow, i);
maxRow = Math.max(maxRow, i);
minCol = Math.min(minCol, j);
maxCol = Math.max(maxCol, j);
}
}
}
return (maxRow - minRow + 1) * (maxCol - minCol + 1);
}
}#include <vector>
using namespace std;
int minArea(vector<vector<int>>& grid) {
int minRow = grid.size(), maxRow = -1;
int minCol = grid[0].size(), maxCol = -1;
for (int i = 0; i < grid.size(); ++i) {
for (int j = 0; j < grid[i].size(); ++j) {
if (grid[i][j] == 1) {
minRow = min(minRow, i);
maxRow = max(maxRow, i);
minCol = min(minCol, j);
maxCol = max(maxCol, j);
}
}
}
return (maxRow - minRow + 1) * (maxCol - minCol + 1);
}function minArea(grid) {
let minRow = grid.length, maxRow = -1;
let minCol = grid[0].length, maxCol = -1;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
if (grid[i][j] === 1) {
minRow = Math.min(minRow, i);
maxRow = Math.max(maxRow, i);
minCol = Math.min(minCol, j);
maxCol = Math.max(maxCol, j);
}
}
}
return (maxRow - minRow + 1) * (maxCol - minCol + 1);
}#include <stdio.h>
int minArea(int** grid, int gridSize, int* gridColSize) {
int minRow = gridSize, maxRow = -1;
int minCol = *gridColSize, maxCol = -1;
for (int i = 0; i < gridSize; ++i) {
for (int j = 0; j < *gridColSize; ++j) {
if (grid[i][j] == 1) {
if (i < minRow) minRow = i;
if (i > maxRow) maxRow = i;
if (j < minCol) minCol = j;
if (j > maxCol) maxCol = j;
}
}
}
return (maxRow - minRow + 1) * (maxCol - minCol + 1);
}public class Solution {
public int MinArea(int[][] grid) {
int minRow = grid.Length, maxRow = -1;
int minCol = grid[0].Length, maxCol = -1;
for (int i = 0; i < grid.Length; i++) {
for (int j = 0; j < grid[i].Length; j++) {
if (grid[i][j] == 1) {
minRow = Math.Min(minRow, i);
maxRow = Math.Max(maxRow, i);
minCol = Math.Min(minCol, j);
maxCol = Math.Max(maxCol, j);
}
}
}
return (maxRow - minRow + 1) * (maxCol - minCol + 1);
}
}The Python version follows the same logic as the previous implementations. It utilizes Python's built-in min and max functions to update the min and max row and column indices based on the positions of '1's. The calculated area given by the span of these indices provides the solution.
Time Complexity: O(n * m), since both dimensions of the grid are explored.
Space Complexity: O(1), using only a few variables for tracking indices.
Approach 2: Coordinate Compression Approach
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.
def minArea(grid):
rows = [i for i, row in enumerate(grid) if 1 in row]
cols = [j for j in range(len(grid[0])) if any(grid[i][j] == 1 for i in range(len(grid)))]
return (max(rows) - min(rows) + 1) * (max(cols) - min(cols) + 1)class Solution {
public int minArea(int[][] grid) {
ArrayList<Integer> rows = new ArrayList<>();
ArrayList<Integer> cols = new ArrayList<>();
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[i].length; j++) {
if (grid[i][j] == 1) {
rows.add(i);
cols.add(j);
}
}
}
return (Collections.max(rows) - Collections.min(rows) + 1) * (Collections.max(cols) - Collections.min(cols) + 1);
}
}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.
Approach 3: Find Minimum and Maximum Boundaries
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).
function minimumArea(grid: number[][]): number {
const [m, n] = [grid.length, grid[0].length];
let [x1, y1] = [m, n];
let [x2, y2] = [0, 0];
for (let i = 0; i < m; ++i) {
for (let 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);
}func minimumArea(grid [][]int) int {
x1, y1 := len(grid), len(grid[0])
x2, y2 := 0, 0
for i, row := range grid {
for j, x := range row {
if x == 1 {
x1, y1 = min(x1, i), min(y1, j)
x2, y2 = max(x2, i), max(y2, j)
}
}
}
return (x2 - x1 + 1) * (y2 - y1 + 1)
}impl Solution {
pub fn minimum_area(grid: Vec<Vec<i32>>) -> i32 {
let m = grid.len();
let n = grid[0].len();
let mut x1 = m as i32;
let mut y1 = n as i32;
let mut x2 = 0i32;
let mut y2 = 0i32;
for i in 0..m {
for j in 0..n {
if grid[i][j] == 1 {
x1 = x1.min(i as i32);
y1 = y1.min(j as i32);
x2 = x2.max(i as i32);
y2 = y2.max(j as i32);
}
}
}
(x2 - x1 + 1) * (y2 - y1 + 1)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n * m), since both dimensions of the grid are explored. |
| 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 | – |
Complexity analysis
| 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. |
Frequently asked questions
Is Find the Minimum Area to Cover All Ones I easy or hard?
The problem is usually classified as Medium difficulty because it requires recognizing that only the extreme coordinates of 1s matter. The implementation itself is straightforward once that insight is clear, involving a single pass over the matrix.
Find the Minimum Area to Cover All Ones I Python/Java solution
The typical Python or Java implementation iterates through the grid using nested loops. Whenever a cell with value 1 is found, update minRow, maxRow, minCol, and maxCol. After traversal, compute the area using the bounding rectangle formula. This implementation runs in O(m*n) time and O(1) space.
How to solve Find the Minimum Area to Cover All Ones I in O(n)?
Treat the grid as m*n cells and perform a single scan. Track the minimum and maximum row and column indices where a 1 appears. After finishing the scan, compute the rectangle area as (maxRow - minRow + 1) * (maxCol - minCol + 1). This linear scan over the matrix achieves O(m*n) time.
What is the best approach for Find the Minimum Area to Cover All Ones I?
The optimal approach scans the grid once and tracks the extreme coordinates where a 1 appears. Maintain minRow, maxRow, minCol, and maxCol while iterating through the matrix. The rectangle defined by these boundaries is the smallest possible area covering all ones. This runs in O(m*n) time and O(1) extra space.
Is Find the Minimum Area to Cover All Ones I asked at Google/Amazon/Meta?
Matrix scanning and bounding box style problems frequently appear in interviews at companies like Amazon, Google, and Meta. The exact problem may vary, but identifying extreme coordinates of elements in a grid is a common pattern tested in array and matrix interview questions.
What data structure is used in Find the Minimum Area to Cover All Ones I?
The solution primarily uses a 2D array (matrix) traversal. Instead of additional data structures, it keeps four integer variables to track the minimum and maximum row and column indices where a 1 occurs.
What is the time complexity of Find the Minimum Area to Cover All Ones I?
The optimal solution runs in O(m*n) time because every cell of the grid is visited exactly once. Only four boundary variables are updated when a 1 is encountered. Space complexity is O(1) since no additional data structures proportional to the grid size are required.