3195. Find the Minimum Area to Cover All Ones I

MediumArrayMatrix

Problem 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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To solve this problem, we need to find the boundaries of a rectangle that encompass all the 1s in the grid. The idea is to traverse the grid and determine the minimum and maximum rows and columns where 1 appears. These boundaries are:

(x1, y1) representing the top-left corner of the rectangle.
(x2, y2) representing the bottom-right corner of the rectangle.

Solution 1: Find Minimum and Maximum Boundaries

We traverse through each element of the grid. For each 1 we encounter:

Update x1 and y1 to be the minimum row and column indices, respectively.
Update x2 and y2 to be the maximum row and column indices, respectively.

Once we have the boundaries, the area of the rectangle can be calculated as:

[ \text{area} = (x2 - x1 + 1) \times (y2 - y1 + 1) ]

This formula accounts for the number of rows and columns covered by the rectangle. By iterating through the grid once, this approach efficiently finds the smallest rectangle encompassing all 1s.

Solution Approach

The implementation of the solution is straightforward. We will use a single pass over the grid to calculate the boundaries of the rectangle.

Initialize x1 and y1 to a very large value (inf in Python) and x2 and y2 to a very small value (-inf in Python). This sets up the initial boundaries.
Iterate over each element in the grid using nested loops. The outer loop iterates over rows with an index i, and the inner loop iterates over columns with an index j.
When a 1 is found at grid[i][j], update the boundaries:
- x1 = min(x1, i): Keep the smallest row index where a 1 appears.
- y1 = min(y1, j): Keep the smallest column index where a 1 appears.
- x2 = max(x2, i): Keep the largest row index where a 1 appears.
- y2 = max(y2, j): Keep the largest column index where a 1 appears.
Once all elements have been processed, calculate the area of the rectangle using the formula:

[ \text{area} = (x2 - x1 + 1) \times (y2 - y1 + 1) ]

The key patterns used here involve:

Initialization for boundary tracking using inf and -inf.
A simple traversal pattern to check each element, updating boundary values accordingly.
Calculation of the area from the derived boundary indices, ensuring all 1s are enclosed.

This approach efficiently finds the minimum possible area containing all 1s using a single traversal of the grid, with a time complexity of O(n * m) where n is the number of rows and m is the number of columns.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example grid:

grid = [
  [0, 0, 1, 0],
  [0, 1, 1, 0],
  [0, 0, 0, 0]
]

To find the smallest rectangle that encompasses all 1s, we initialize our boundary indicators:

x1 = inf, y1 = inf for the top-left corner.
x2 = -inf, y2 = -inf for the bottom-right corner.

Now, let's iterate through the grid to update these boundaries.

Row 0, Column 2: We find a 1.
- Update boundaries:
  - x1 = min(inf, 0) = 0 (smallest row index)
  - y1 = min(inf, 2) = 2 (smallest column index)
  - x2 = max(-inf, 0) = 0 (largest row index)
  - y2 = max(-inf, 2) = 2 (largest column index)
Row 1, Column 1: We find another 1.
- Update boundaries:
  - x1 = min(0, 1) = 0
  - y1 = min(2, 1) = 1
  - x2 = max(0, 1) = 1
  - y2 = max(2, 1) = 2
Row 1, Column 2: Another 1.
- Update boundaries:
  - x1 = min(0, 1) = 0
  - y1 = min(1, 2) = 1
  - x2 = max(1, 1) = 1
  - y2 = max(2, 2) = 2

Once we have completed the grid traversal, the boundaries are fixed: x1 = 0, y1 = 1, x2 = 1, and y2 = 2.

Finally, calculate the area of the rectangle:

[ \text{area} = (x2 - x1 + 1) \times (y2 - y1 + 1) = (1 - 0 + 1) \times (2 - 1 + 1) = 2 \times 2 = 4 ]

Therefore, the minimum possible area of the rectangle that contains all 1s in the grid is 4.

Solution Implementation

1from typing import List
2import math
3
4class Solution:
5    def minimumArea(self, grid: List[List[int]]) -> int:
6        # Initialize the boundary coordinates for the rectangle
7        # Start with `inf` for minimums and `-inf` for maximums
8        x1 = y1 = math.inf
9        x2 = y2 = -math.inf
10
11        # Iterate over each element in the grid
12        for i, row in enumerate(grid):
13            for j, value in enumerate(row):
14                # Check if the current element is 1
15                if value == 1:
16                    # Update the boundary coordinates
17                    x1 = min(x1, i)  # update top boundary
18                    y1 = min(y1, j)  # update left boundary
19                    x2 = max(x2, i)  # update bottom boundary
20                    y2 = max(y2, j)  # update right boundary
21      
22        # Calculate the area of the rectangle defined by the boundaries
23        return (x2 - x1 + 1) * (y2 - y1 + 1)
24

1class Solution {
2    public int minimumArea(int[][] grid) {
3        // Determine dimensions of the grid
4        int rows = grid.length;
5        int cols = grid[0].length;
6      
7        // Initialize boundary coordinates for the smallest rectangle
8        int topBoundary = rows;
9        int leftBoundary = cols;
10        int bottomBoundary = 0;
11        int rightBoundary = 0;
12      
13        // Traverse each cell in the grid
14        for (int i = 0; i < rows; ++i) {
15            for (int j = 0; j < cols; ++j) {
16                // Check if the cell is part of the region (value is 1)
17                if (grid[i][j] == 1) {
18                    // Update the boundaries to include this cell
19                    topBoundary = Math.min(topBoundary, i);
20                    leftBoundary = Math.min(leftBoundary, j);
21                    bottomBoundary = Math.max(bottomBoundary, i);
22                    rightBoundary = Math.max(rightBoundary, j);
23                }
24            }
25        }
26      
27        // Compute the area of the smallest rectangle enclosing all 1s
28        return (bottomBoundary - topBoundary + 1) * (rightBoundary - leftBoundary + 1);
29    }
30}
31

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    int minimumArea(std::vector<std::vector<int>>& grid) {
7        int m = grid.size();     // Rows in the grid
8        int n = grid[0].size();  // Columns in the grid
9
10        // Initialize boundaries for the rectangle
11        int x1 = m, y1 = n;      // Start with maximum values
12        int x2 = 0, y2 = 0;      // Start with minimum values
13
14        // Iterate through grid to find boundary of 1s
15        for (int i = 0; i < m; ++i) {
16            for (int j = 0; j < n; ++j) {
17                if (grid[i][j] == 1) {
18                    // Update the minimum x and y coordinates
19                    x1 = std::min(x1, i);
20                    y1 = std::min(y1, j);
21
22                    // Update the maximum x and y coordinates
23                    x2 = std::max(x2, i);
24                    y2 = std::max(y2, j);
25                }
26            }
27        }
28      
29        // Calculate the area of the rectangle enclosing all 1s
30        return (x2 - x1 + 1) * (y2 - y1 + 1);
31    }
32};
33

1// Function to calculate the minimum area of a rectangle that can enclose all 1s in the grid
2function minimumArea(grid: number[][]): number {
3    // Extract dimensions of the grid
4    const [m, n] = [grid.length, grid[0].length];
5
6    // Initialize boundaries of the rectangle
7    let [x1, y1] = [m, n]; // Upper-left corner
8    let [x2, y2] = [0, 0]; // Lower-right corner
9
10    // Iterate over each cell in the grid
11    for (let row = 0; row < m; ++row) {
12        for (let col = 0; col < n; ++col) {
13            if (grid[row][col] === 1) {
14                // Update boundaries when a '1' is found
15                x1 = Math.min(x1, row); // Update top boundary
16                y1 = Math.min(y1, col); // Update left boundary
17                x2 = Math.max(x2, row); // Update bottom boundary
18                y2 = Math.max(y2, col); // Update right boundary
19            }
20        }
21    }
22
23    // Calculate and return the area of the enclosing rectangle
24    return (x2 - x1 + 1) * (y2 - y1 + 1);
25}
26

Time and Space Complexity

The time complexity of the code is O(m * n), where m is the number of rows and n is the number of columns in grid. This is because the code iterates through each element of the grid once.

The space complexity of the code is O(1) since the space used does not depend on the size of grid and only a constant amount of space is needed for the variables x1, y1, x2, and y2.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

You are given an array of intervals where intervals[i] = [start_i, end_i] represent the start and end of the ith interval. You need to merge all overlapping intervals and return an array of the non-overlapping intervals that cover all the intervals in the input.

Sort the intervals by their start time, then iterate through the sorted intervals, merging any overlapping intervals.

Brute force through all interval combinations and find the answer with the least total intervals.

Iterate through the intervals in their original order, merging any overlapping intervals.

Use a priority queue to keep track of the intervals, merging any overlapping intervals.

I don't know