Smallest Rectangle Enclosing Black Pixels in C++

Suppose we have an image and that image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. Here the black pixels are connected, so there is only one black region. Pixels are connected horizontally and vertically. If we have a location (x, y) of one of the black pixels, we have to find the area of the smallest (axis-aligned) rectangle that encloses all black pixels.

So, if the input is like

and x = 0, y = 2, then the output will be 6

To solve this, we will follow these steps −

• Define one 2D array v

• Define a function searchRows(), this will take i, j, left, right, one,

• while i < j, do −

  • mid := i + (j - i) / 2

  • k := left

  • while (k < right and v[mid, k] is same as '0'), do −

    • (increase k by 1)

  • if k <' right is same as one, then −

    • j := mid

  • Otherwise

    • i := mid + 1

• return i

• Define a function searchColumn(), this will take i, j, top, bottom, one,

• while i is not equal to j, do −

  • mid := i + (j - i) / 2

  • k := top

  • while (k < bottom and v[k, mid] is same as '0'), do −

    • (increase k by 1)

  • if k < bottom is same as one, then −

    • j := mid

  • Otherwise

    • i := mid + 1

• return i

• From the main method do the following −

• v := image

• ret := 0

• n := row size of image

• m := col size of image

• top := searchRows(0, x, 0, m, true)

• bottom := searchRows(x + 1, n, 0, m, false)

• left := searchColumn(0, y, top, bottom, true)

• right := searchColumn(y + 1, m, top, bottom, false)

• return (right - left) * (bottom - top)

Example 

Let us see the following implementation to get better understanding −

 Live Demo

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector < vector <char> > v;
   int searchRows(int i, int j, int left, int right, bool one){
      while (i < j) {
         int mid = i + (j - i) / 2;
         int k = left;
         while (k < right && v[mid][k] == '0')
            k++;
         if (k < right == one) {
            j = mid;
         }
         else {
            i = mid + 1;
         }
      }
      return i;
   }
   int searchColumn(int i, int j, int top, int bottom, bool one){
      while (i != j) {
         int mid = i + (j - i) / 2;
         int k = top;
         while (k < bottom && v[k][mid] == '0')
            k++;
         if (k < bottom == one) {
            j = mid;
         }
         else {
            i = mid + 1;
         }
      }
      return i;
   }
   int minArea(vector<vector<char>>& image, int x, int y) {
      v = image;
      int ret = 0;
      int n = image.size();
      int m = image[0].size();
      int top = searchRows(0, x, 0, m, true);
      int bottom = searchRows(x + 1, n, 0, m, false);
      int left = searchColumn(0, y, top, bottom, true);
      int right = searchColumn(y + 1, m, top, bottom, false);
      return (right - left) * (bottom - top);
   }
};
main(){
   Solution ob;
   vector<vector<char>> v =
   {{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}};
   cout << (ob.minArea(v, 0, 2));
}

Input

{{'0','0','1','0'},{'0','1','1','0'},{'0','1','0','0'}}, 0, 2

Output

6