Problem of The Day: Find the Minimum Area to Cover All Ones I

Problem Statement

leetcode problem link

Brute Force Approach [Accepted]

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        res = 0
        ROWS = len(grid)
        COLS = len(grid[0])
        rows = set()
        cols = set()
        for row in range(ROWS):
            for col in range(COLS):
                if grid[row][col] == 1:
                    rows.add(row)
                    cols.add(col)

        smallest_row = min(rows)
        smallest_col = min(cols)
        largest_row = max(rows)
        largest_col = max(cols)

        for row in range(smallest_row, largest_row + 1):
            for col in range(smallest_col, largest_col + 1):
                res += 1

        return res

Editorial

Approach: One-time Traversal

class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        n, m = len(grid), len(grid[0])
        min_i, max_i = n, 0
        min_j, max_j = m, 0

        for i in range(n):
            for j in range(m):
                if grid[i][j] == 1:
                    min_i = min(min_i, i)
                    max_i = max(max_i, i)
                    min_j = min(min_j, j)
                    max_j = max(max_j, j)

        return (max_i - min_i + 1) * (max_j - min_j + 1)