Smallest Rectangle Enclosing Black Pixels

Problem Description

Ah, the classic “Smallest Rectangle Enclosing Black Pixels” problem! Imagine you’re at a pixel party, and all the black pixels are having a great time, while the white pixels are just standing around awkwardly. Your job? To find the smallest rectangle that can enclose all those lively black pixels. It’s like trying to find the smallest box to fit all your friends into for a group photo—except in this case, the friends are black pixels, and the box is a rectangle.

In more technical terms, given a 2D binary image represented as a grid of ‘0’s (white pixels) and ‘1’s (black pixels), you need to find the smallest rectangle that can enclose all the black pixels. You’re given the coordinates of one black pixel, and you need to figure out the dimensions of the rectangle that contains all the black pixels.

Code Solution


class Solution {
 public:
  int minArea(vector>& image, int x, int y) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int m = image.size();
    const int n = image[0].size();
    vector topLeft{x, y};
    vector bottomRight{x, y};
    queue> q{{{x, y}}};
    image[x][y] = '2';  // Mark as visited.

    while (!q.empty()) {
      const auto [i, j] = q.front();
      q.pop();
      for (const auto& [dx, dy] : dirs) {
        const int r = i + dx;
        const int c = j + dy;
        if (r < 0 || r == m || c < 0 || c == n)
          continue;
        if (image[r][c] != '1')
          continue;
        topLeft[0] = min(topLeft[0], r);
        topLeft[1] = min(topLeft[1], c);
        bottomRight[0] = max(bottomRight[0], r);
        bottomRight[1] = max(bottomRight[1], c);
        q.emplace(r, c);
        image[r][c] = '2';
      }
    }

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

Approach

The approach taken in this solution is quite straightforward yet effective. It uses a breadth-first search (BFS) to explore the grid starting from the given black pixel. The algorithm marks visited pixels to avoid counting them multiple times. It keeps track of the top-left and bottom-right corners of the rectangle that encloses all the black pixels. By the end of the BFS, it calculates the width and height of the rectangle and returns 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 stage that fits all the musicians. The black pixels represent the musicians, and your task is to find the smallest stage that can accommodate them all. Just like in our pixel problem, you need to ensure that no musician is left out of the performance!