SAMSUNG 49-Inch Odyssey G9

Because earth is not flat

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<vector<int>>& 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);
    }
}