3195. Find the Minimum Area to Cover All Ones I

Intuition

The intuition behind solving this problem involves finding the smallest rectangle (in terms of area) that can encompass all the '1's in a given 2D binary grid. This rectangle must have its sides aligned horizontally and vertically.

Approach

To achieve the solution:

1. Initialization: Start by initializing variables ra, rb, ca, and cb to extreme values (ra = 1000, rb = 0, ca = 1000, cb = 0). These variables will track the boundaries of the rectangle that will cover all '1's in the grid.
2. Iterate through the Grid: Use nested loops to iterate through each element in the grid: - If grid[i][j] equals 1, update ra, rb, ca, and cb to adjust the boundaries of the rectangle: - ra (minimum row index containing '1') - rb (maximum row index containing '1') - ca (minimum column index containing '1') - cb (maximum column index containing '1')
3. Calculate Area: Once the iteration is complete, calculate the area of the smallest rectangle that encompasses all '1's: - Width of the rectangle: (rb - ra + 1) - Height of the rectangle: (cb - ca + 1) - Area of the rectangle: (rb - ra + 1) * (cb - ca + 1)
4. Return Result: Return the calculated area as the minimum possible area that covers all '1's in the grid.

Complexity

• Time Complexity: O(m * n), where m is the number of rows and n is the number of columns in the grid. This is because we iterate through the entire grid to find the boundaries of the rectangle.
• Space Complexity: O(1). We use only a constant amount of extra space for the variables ra, rb, ca, and cb, regardless of the size of the input grid.

Code

C++

class Solution {
public:
    int minimumArea(vector>& grid) {
        int ra = 1000, rb = 0;
        int ca = 1000, cb = 0;

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j] == 1) {
                    if (i < ra) ra = i;
                    if (i > rb) rb = i;
                    if (j < ca) ca = j;
                    if (j > cb) cb = j;
                }
            }
        }

        return (rb - ra + 1) * (cb - ca + 1);
    }
};

Python

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        ra, rb = 1000, 0
        ca, cb = 1000, 0

        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if grid[i][j] == 1:
                    if i < ra: ra = i
                    if i > rb: rb = i
                    if j < ca: ca = j
                    if j > cb: cb = j

        return (rb - ra + 1) * (cb - ca + 1)

Java

class Solution {
    public int minimumArea(int[][] grid) {
        int ra = 1000, rb = 0;
        int ca = 1000, cb = 0;

        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == 1) {
                    if (i < ra) ra = i;
                    if (i > rb) rb = i;
                    if (j < ca) ca = j;
                    if (j > cb) cb = j;
                }
            }
        }

        return (rb - ra + 1) * (cb - ca + 1);
    }
}

JavaScript

/**
 * @param {number[][]} grid
 * @return {number}
 */
var minimumArea = function(grid) {
    let ra = 1000, rb = 0;
    let ca = 1000, cb = 0;

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (grid[i][j]) {
                if (i < ra) ra = i;
                if (i > rb) rb = i;
                if (j < ca) ca = j;
                if (j > cb) cb = j;
            }
        }
    }

    return (rb - ra + 1) * (cb - ca + 1);
};

Go

func minimumArea(grid [][]int) int {
	ra, rb := 1000, 0
	ca, cb := 1000, 0

	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[i]); j++ {
			if grid[i][j] == 1 {
				if i < ra {
					ra = i
				}
				if i > rb {
					rb = i
				}
				if j < ca {
					ca = j
				}
				if j > cb {
					cb = j
				}
			}
		}
	}

	return (rb - ra + 1) * (cb - ca + 1)
}

C#

public class Solution {
    public int MinimumArea(int[][] grid) {
        int ra = 1000, rb = 0;
        int ca = 1000, cb = 0;

        for (int i = 0; i < grid.Length; i++) {
            for (int j = 0; j < grid[i].Length; j++) {
                if (grid[i][j] == 1) {
                    if (i < ra) ra = i;
                    if (i > rb) rb = i;
                    if (j < ca) ca = j;
                    if (j > cb) cb = j;
                }
            }
        }

        return (rb - ra + 1) * (cb - ca + 1);
    }
}