302. Smallest Rectangle Enclosing Black Pixels

You are given an m x n binary matrix image where 0 represents a white pixel and 1 represents a black pixel.

The black pixels are connected (i.e., there is only one black region). Pixels are connected horizontally and vertically.

Given two integers x and y that represents the location of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

You must write an algorithm with less than O(mn) runtime complexity

• Time : O(nm)
• Space : O(nm)

c++

class Solution {
public:
    int minArea(vector<vector<char>>& image, int y, int x) {
        int miX = x, maX = x, miY = y, maY = y, n = image.size(), m = image[0].size();
        queue<pair<int,int>> q;
        q.push({y,x});
        int dx[4] = {0, 1, 0, -1}, dy[4] = {-1,0,1,0};
        while(!q.empty()) {
            auto [y, x] = q.front(); q.pop();
            for(int i = 0; i < 4; i++) {
                int ny = y + dy[i], nx = x + dx[i];
                if(0 <= nx and nx < m and 0 <= ny and ny < n and image[ny][nx] == '1') {
                    image[ny][nx] = '0';
                    q.push({ny,nx});
                    maX = max(maX, nx);
                    maY = max(maY, ny);
                    miX = min(miX, nx);
                    miY = min(miY, ny);
                }
            }
        }

        return (maX-miX + 1) * (maY - miY + 1);
    }
};