Smallest Rectangle Enclosing Black Pixels

Navigate to Other Solutions

Problem Description

Ah, the classic “Smallest Rectangle Enclosing Black Pixels” problem! Imagine you’re at a party, and you spot a group of people wearing black shirts (because, of course, they want to look cool). Your mission, should you choose to accept it, is to find the smallest rectangular area that can enclose all these stylish individuals. But wait! You can’t just throw a blanket over them; you need to calculate the exact dimensions of this rectangle.

In the world of LeetCode, this translates to finding the smallest rectangle that can enclose all the ‘1’s (black pixels) in a binary image represented by a 2D array. If only life were as simple as just throwing a blanket over a group of friends!

Code Solution


class Solution {
  public int minArea(char[][] image, int x, int y) {
    final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    final int m = image.length;
    final int n = image[0].length;
    int[] topLeft = {x, y};
    int[] bottomRight = {x, y};
    Queue> q = new ArrayDeque<>(List.of(new Pair<>(x, y)));
    image[x][y] = '2'; // Mark as visited.

    while (!q.isEmpty()) {
      final int i = q.peek().getKey();
      final int j = q.poll().getValue();
      for (int[] dir : dirs) {
        final int r = i + dir[0];
        final int c = j + dir[1];
        if (r < 0 || r == m || c < 0 || c == n)
          continue;
        if (image[r][c] != '1')
          continue;
        topLeft[0] = Math.min(topLeft[0], r);
        topLeft[1] = Math.min(topLeft[1], c);
        bottomRight[0] = Math.max(bottomRight[0], r);
        bottomRight[1] = Math.max(bottomRight[1], c);
        q.offer(new Pair<>(r, c));
        image[r][c] = '2';
      }
    }

    final int width = bottomRight[1] - topLeft[1] + 1;
    final int height = bottomRight[0] - topLeft[0] + 1;
    return width * height;
  }
}

Approach Explanation

The approach taken in this solution is akin to a treasure hunt. We start at the given coordinates (x, y) and explore the surrounding area using a breadth-first search (BFS). As we traverse the image, we keep track of the top-left and bottom-right corners of the rectangle that can enclose all the ‘1’s. By marking visited pixels, we ensure we don’t count them twice. Finally, we calculate the width and height of the rectangle and return the area.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(m * n)
Space Complexity	O(m * n)

Real-World Example

Imagine you’re organizing a concert, and you need to set up a VIP area for all the black-clad fans. You want to ensure that the area is just right—not too big, not too small. By applying the same logic as in the “Smallest Rectangle Enclosing Black Pixels” problem, you can efficiently determine the dimensions of the VIP area based on the location of your fans.