Find the Minimum Area to Cover All Ones I

Find the Minimum Area to Cover All Ones I - Problem

Array Matrix Medium

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.

Input & Output

Example 1 — Basic Case

$ Input: grid = [[0,1,0],[1,1,0]]

› Output: 2

💡 Note: The 1's are at positions (0,1), (1,0), and (1,1). The minimum rectangle covers rows 0-1 and column 1, giving area = 2 * 1 = 2

Example 2 — Single Cell

$ Input: grid = [[1]]

› Output: 1

💡 Note: Only one 1 at position (0,0), so minimum rectangle is 1x1 with area = 1

Example 3 — Scattered 1's

$ Input: grid = [[1,0,0],[0,0,1]]

› Output: 6

💡 Note: 1's at (0,0) and (1,2). Rectangle must cover rows 0-1 and columns 0-2, giving area = 2 * 3 = 6

Constraints

1 ≤ grid.length, grid[i].length ≤ 100
grid[i][j] is 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

Binary grid with 0's and 1's scattered

Find Boundaries

Identify extreme positions of all 1's

Calculate Area

Rectangle area = height × width

Key Takeaway

🎯 Key Insight: Only need the topmost, bottommost, leftmost, and rightmost 1's to define the minimum rectangle

Asked in

G Google 25 a Amazon 20 M Microsoft 15

Find the minimum rectangle that covers all 1's in a binary grid. The key insight is to find the extreme coordinates (min/max row and column) of all 1's, then calculate the area of the bounding rectangle. Best approach uses boundary tracking in O(m×n) time with O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Rectangles	O(n⁴)	O(1)	Try every possible rectangle and check if it contains all 1's
Find Boundary Coordinates	O(m×n)	O(1)	Find the extreme positions of all 1's to determine minimum rectangle

Brute Force - Check All Rectangles — Algorithm Steps

Iterate through all possible top-left corners
For each top-left, try all bottom-right corners
Check if rectangle contains all 1's
Track minimum area found

Visualization

Tap to expand

Step-by-Step Walkthrough

Find 1's

Locate all 1's in the grid

Try Rectangles

Test every possible rectangle

Find Minimum

Return smallest area that covers all 1's

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int solution(int** grid, int gridSize, int* gridColSize) {
    if (gridSize == 0 || gridColSize[0] == 0) return 0;
    
    int m = gridSize, n = gridColSize[0];
    int ones[1000][2]; // Assuming max 1000 ones
    int oneCount = 0;
    
    // Find all 1's positions
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 1) {
                ones[oneCount][0] = i;
                ones[oneCount][1] = j;
                oneCount++;
            }
        }
    }
    
    if (oneCount == 0) return 0;
    
    int minArea = INT_MAX;
    
    // Try all possible rectangles
    for (int top = 0; top < m; top++) {
        for (int left = 0; left < n; left++) {
            for (int bottom = top; bottom < m; bottom++) {
                for (int right = left; right < n; right++) {
                    // Check if this rectangle contains all 1's
                    int valid = 1;
                    for (int k = 0; k < oneCount; k++) {
                        if (ones[k][0] < top || ones[k][0] > bottom || 
                            ones[k][1] < left || ones[k][1] > right) {
                            valid = 0;
                            break;
                        }
                    }
                    
                    if (valid) {
                        int area = (bottom - top + 1) * (right - left + 1);
                        if (area < minArea) {
                            minArea = area;
                        }
                    }
                }
            }
        }
    }
    
    return minArea;
}

int main() {
    // Simple parsing for demo - assumes small grid
    int grid[10][10];
    int* gridPtrs[10];
    int gridColSize[10];
    
    // Read basic 2x2 example
    int gridSize = 2;
    gridColSize[0] = gridColSize[1] = 2;
    
    for (int i = 0; i < gridSize; i++) {
        gridPtrs[i] = grid[i];
    }
    
    // Example input parsing (simplified)
    grid[0][0] = 0; grid[0][1] = 1;
    grid[1][0] = 1; grid[1][1] = 1;
    
    printf("%d\n", solution(gridPtrs, gridSize, gridColSize));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n⁴)

Four nested loops: two for rectangle corners and two to verify all 1's are inside

✓ Linear Growth

Space Complexity

O(1)

Only using variables to track coordinates and minimum area

✓ Linear Space

23.1K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Rectangles — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler