LeetCode 302: Smallest Rectangle Enclosing Black Pixels Solution in Python – A Step-by-Step Guide

What Is LeetCode 302: Smallest Rectangle Enclosing Black Pixels?

In LeetCode 302: Smallest Rectangle Enclosing Black Pixels, you’re given a 2D binary array image where 0s are white pixels and 1s are black pixels, plus coordinates x and y pointing to one black pixel (1). Your task is to find the area of the smallest rectangle that encloses all black pixels, assuming they’re connected (via up, down, left, right). For example, in [[0,0,1],[0,1,0],[1,0,0]] with x=0, y=2, the rectangle spans rows 0-2 and cols 0-2, area = 3 * 3 = 9. This problem tests your grid search skills, sharing a vibe with LeetCode 200: Number of Islands.

Problem Statement

• Input: A 2D array image (0s and 1s), integers x and y (a black pixel’s location).
• Output: An integer—the area of the smallest enclosing rectangle.
• Rules: Rectangle must contain all 1s; black pixels are connected; use Manhattan moves (no diagonals).

Constraints

• image size: m x n, where 1 ≤ m, n ≤ 50.
• Values: 0 or 1.
• x and y point to a 1; at least one 1 exists.

Examples

• Input: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2
• Output: 6 (2 rows * 3 cols)
• Input: image = [["1"]], x = 0, y = 0
• Output: 1 (1 * 1)
• Input: image = [["0","1"],["1","0"]], x = 0, y = 1
• Output: 4 (2 * 2)

Understanding the Problem: Boxing the Pixels

To solve LeetCode 302: Smallest Rectangle Enclosing Black Pixels in Python, we need to find the smallest rectangle that surrounds all 1s in image, starting from a known black pixel at (x, y). The black pixels are connected (up, down, left, right), so we need the topmost, bottommost, leftmost, and rightmost 1s to define the box. For [[0,0,1],[0,1,0]], we could scan every cell, but that’s slow. Instead, we’ll use:

• Best Solution (Binary Search on Boundaries): O(m log n + n log m) time, O(1) space—fast and sleek.
• Alternative Solution (DFS Traversal): O(m * n) time, O(m * n) space—simpler but slower.

Let’s dive into the binary search solution with a friendly breakdown that’s easy to follow.

Best Solution: Binary Search on Boundaries

Why This Is the Best Solution

The binary search on boundaries approach is the top choice for LeetCode 302 because it’s highly efficient—O(m log n + n log m) time and O(1) space—using binary search to find the edges of the black pixel region instead of checking every cell. It leverages the connectedness of 1s and the given starting point (x, y) to zoom in on the top, bottom, left, and right limits. It’s like using a magnifying glass to find the edges of a shape—quick and precise!

How It Works

Let’s picture this like drawing a box around a blob:

• Step 1: Use Binary Search:
• For rows: Search top (0 to x) and bottom (x to m-1) for first/last 1s.
• For cols: Search left (0 to y) and right (y to n-1) for first/last 1s.
• Step 2: Check Rows and Columns:
• Row check: Scan a row for any 1.
• Col check: Scan a column for any 1.
• Step 3: Find Edges:
• Top: Binary search rows above x until no 1s.
• Bottom: Binary search rows below x until no 1s.
• Left: Binary search cols left of y until no 1s.
• Right: Binary search cols right of y until no 1s.
• Step 4: Calculate Area:
• Area = (bottom - top + 1) * (right - left + 1).
• Step 5: Why It Works:
• Connectedness ensures all 1s are within the rectangle from (x, y).
• Binary search cuts row/col checks from O(m) or O(n) to O(log m) or O(log n).

It’s like zooming in on the edges of a picture frame—fast and neat!

Step-by-Step Example

Example: image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2

• Step 1: Row Check Helper:
• has_one(row): Returns True if row has a 1.
• Top Edge:
• Rows 0 to 0: has_one(0) = True → top = 0.
• Bottom Edge:
• Rows 0 to 2: Binary search:
• Mid = 1: has_one(1) = True, check 2.
• Mid = 2: has_one(2) = True, bottom = 2.
• Column Check Helper:
• has_one(col): Returns True if col has a 1.
• Left Edge:
• Cols 0 to 2: Binary search:
• Mid = 1: has_one(1) = True, check 0.
• Mid = 0: has_one(0) = False, left = 1.
• Right Edge:
• Cols 2 to 3: Binary search:
• Mid = 2: has_one(2) = True, check 3.
• Mid = 3: has_one(3) = False, right = 2.
• Area: (2 - 0 + 1) * (2 - 1 + 1) = 3 * 2 = 6.
• Result: 6.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        # Step 1: Get grid size
        m, n = len(image), len(image[0])

        # Step 2: Helpers to check rows and columns
        def has_one_row(row):
            return '1' in image[row]

        def has_one_col(col):
            return '1' in [image[r][col] for r in range(m)]

        # Step 3: Binary search for top
        top = 0
        left, right = 0, x
        while left < right:
            mid = (left + right) // 2
            if has_one_row(mid):
                right = mid
            else:
                left = mid + 1
        top = left

        # Step 4: Binary search for bottom
        bottom = m - 1
        left, right = x, m - 1
        while left < right:
            mid = (left + right + 1) // 2
            if has_one_row(mid):
                left = mid
            else:
                right = mid - 1
        bottom = left

        # Step 5: Binary search for left
        leftmost = 0
        left, right = 0, y
        while left < right:
            mid = (left + right) // 2
            if has_one_col(mid):
                right = mid
            else:
                left = mid + 1
        leftmost = left

        # Step 6: Binary search for right
        rightmost = n - 1
        left, right = y, n - 1
        while left < right:
            mid = (left + right + 1) // 2
            if has_one_col(mid):
                left = mid
            else:
                right = mid - 1
        rightmost = left

        # Step 7: Calculate area
        return (bottom - top + 1) * (rightmost - leftmost + 1)

• Line 4: Get grid dimensions (m rows, n cols).
• Line 7-10: Helpers:
• has_one_row: True if row has '1'.
• has_one_col: True if col has '1'.
• Line 13-20: Top: Search 0 to x for first row with 1.
• Line 23-30: Bottom: Search x to m-1 for last row with 1 (right adjusted for upper bound).
• Line 33-40: Left: Search 0 to y for first col with 1.
• Line 43-50: Right: Search y to n-1 for last col with 1 (right adjusted).
• Line 52: Area = height * width.

• Time Complexity: O(m log n + n log m)—binary searches on rows and cols.
• Space Complexity: O(1)—no extra space beyond variables.

This is like a quick zoom—find edges fast!

Alternative Solution: DFS Traversal

Why an Alternative Approach?

DFS traversal explores all connected 1s from (x, y)—O(m * n) time, O(m * n) space. It’s simpler but slower, tracking visited cells and updating bounds, like painting the blob to find its edges—intuitive but less efficient.

How It Works

Let’s think of this as exploring a maze:

• Step 1: Start DFS from (x, y).
• Step 2: Track min/max row/col as you visit 1s.
• Step 3: Calculate area from bounds.

It’s like mapping the blob step-by-step!

Step-by-Step Example

Example: image = [["0","0","1"],["0","1","0"]], x = 0, y = 2

• DFS: Start (0,2).
• (0,2): top=0, bottom=0, left=2, right=2.
• Down (1,2): No 1.
• Left (0,1): No 1.
• Down (1,1): (1,1), top=0, bottom=1, left=1, right=2.
• Area: (1 - 0 + 1) * (2 - 1 + 1) = 2 * 2 = 4.
• Result: 4.

Code for DFS Approach

Copy codeclass Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])
        visited = set()

        # Track boundaries
        self.top = x
        self.bottom = x
        self.left = y
        self.right = y

        def dfs(r, c):
            if (r, c) in visited or r < 0 or r >= m or c < 0 or c >= n or image[r][c] == '0':
                return
            visited.add((r, c))
            self.top = min(self.top, r)
            self.bottom = max(self.bottom, r)
            self.left = min(self.left, c)
            self.right = max(self.right, c)
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                dfs(r + dr, c + dc)

        dfs(x, y)
        return (self.bottom - self.top + 1) * (self.right - self.left + 1)

• Time Complexity: O(m * n)—visits each cell once.
• Space Complexity: O(m * n)—visited set.

It’s a full map but slow!

Comparing the Two Solutions

• Binary Search (Best):
• Pros: O(m log n + n log m) time, O(1) space, fast.
• Cons: Binary search logic.
• DFS (Alternative):
• Pros: O(m * n) time, O(m * n) space, simple traversal.
• Cons: Slower, more space.

Binary search wins big.

Additional Examples and Edge Cases

• [["1"]]: 1.
• [["0","1"]]: 2.
• [["1","1"]]: 2.

Binary search is faster.

Complexity Breakdown

• Binary Search: Time O(m log n + n log m), Space O(1).
• DFS: Time O(m * n), Space O(m * n).

Binary search rules.

Key Takeaways

• Binary Search: Zoom to edges—smart!
• DFS: Explore all—clear!
• Grids: Boundaries are key.
• Python Tip: Search rocks—see [Python Basics](/python/basics).

Final Thoughts: Frame Those Pixels

LeetCode 302: Smallest Rectangle Enclosing Black Pixels in Python is a neat grid puzzle. Binary search zips to the edges, while DFS maps it out. Want more? Try LeetCode 200: Number of Islands or LeetCode 286: Walls and Gates. Ready to box? Head to Solve LeetCode 302 on LeetCode and frame those pixels today!