/**
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
For example, given the following image:
[
"0010",
"0110",
"0100"
]
and x = 0, y = 2, Return 6.
*/
public class SmallestRectangleEnclosingBlackPixels{
/**
Sol1: use two nested loops and keep track the the leftmost col, upmost row, rightmost col, and bottommost row where we find 1. Use these four points to find the area
O(m*n), O(1)
*/
public int minArea1(char[][] image, int x, int y) {
int top = x, bottom = x;
int left = y, right = y;
for (x = 0; x < image.length; ++x) {
for (y = 0; y < image[0].length; ++y) {
if (image[x][y] == '1') {
top = Math.min(top, x);
bottom = Math.max(bottom, x + 1);
left = Math.min(left, y);
right = Math.max(right, y + 1);
}
}
}
return (right - left) * (bottom - top);
}
/**
Solution2:
Intuition
Explore all the connected black pixel from the given pixel and update the boundaries.
Algorithm
The naive approach did not use the condition that all the black pixels are connected and that one of the black pixels is given.
A simple way to use these facts is to do an exhaustive search starting from the given pixel. Since all the black pixels are connected, DFS or BFS will visit all of them starting from the given black pixel. The idea is similar to what we did for 200. Number of Island. Instead of many islands, we have only one island here, and we know one pixel of it.
*/
private int top, bottom, left, right;
public int minArea2(char[][] image, int x, int y) {
if(image.length == 0 || image[0].length == 0) return 0;
top = bottom = x;
left = right = y;
dfs(image, x, y);
return (right - left) * (bottom - top);
}
private void dfs(char[][] image, int x, int y){
if(x < 0 || y < 0 || x >= image.length || y >= image[0].length ||
image[x][y] == '0')
return;
image[x][y] = '0'; // mark visited black pixel as white
top = Math.min(top, x);
bottom = Math.max(bottom, x + 1);
left = Math.min(left, y);
right = Math.max(right, y + 1);
dfs(image, x + 1, y);
dfs(image, x - 1, y);
dfs(image, x, y - 1);
dfs(image, x, y + 1);
}
/**
Solution3:
Intuition
Project the 2D image into a 1D array and use binary search to find the boundaries.
Algorithm
matrix projection
*Figure 1. Illustration of image projection.
Suppose we have a image as shown in figure 1, if we project each column of the image into an entry of row vector v with the following rule:
v[i] = 1 if exists x such that image[x][i] = 1
v[i] = 0 otherwise
That is
If a column has any black pixel it's projection is black otherwise white.
Similarly, we can do the same for the rows, and project the image into a 1D column vector. The two projected vectors are shown in figure 1.
Now, we claim the following lemma:
Lemma
If there are only one black pixel region, then in a projected 1D array all the black pixels are connected.
Proof by contradiction
Assume to the contrary that there are disconnected black pixels at i and j where i < j in the 1D projection array. Thus, there exists one column k, k in (i, j) and the column k in the 2D array has no black pixel. Therefore, in the 2D array there exist at least two black pixel regions separated by column k which contradicting the condition of "only one black pixel region". Therefore, we conclude that all the black pixels in the 1D projection array are connected.
With this lemma, we have the following algorithm:
Project the 2D array into a column array and a row array
Binary search to find left in the row array within [0, y)
Binary search to find right in the row array within [y + 1, n)
Binary search to find top in the column array within [0, x)
Binary search to find bottom in the column array within [x + 1, m)
Return (right - left) * (bottom - top)
However, the projection step cost time which dominates the entire algorithm.If so, we gain nothing comparing with previous approaches.
The trick is that we do not need to do the projection step as a preprocess. We can do it on the fly, i.e. "don't project the column/row unless needed".
Recall the binary search algorithm in a 1D array, each time we only check one element, the pivot, to decide which half we go next.
In a 2D array, we can do something similar. The only difference here is that the element is not a number but a vector. For example, a m by n matrix can be seen as n column vectors.
In these n elements/vectors, we do a binary search to find left or right. Each time we only check one element/vector, the pivot, to decide which half we go next. In total it checks vectors, and each check is (we simply traverse all the m entries of the pivot vector).
So it costs to find left and right. Similarly it costs to find top and bottom.
To find the left boundary, do the binary search in the [0, y) range and find the first column vector who has any black pixel.
To determine if a column vector has a black pixel is O(m) so the search in total is O(m log n)
We can do the same for the other boundaries. The area is then calculated by the boundaries. Thus the algorithm runs in O(m log n + n log m)
*/
private char[][] image;
public int minArea3(char[][] iImage, int x, int y) {
image = iImage;
int m = image.length, n = image[0].length;
//search for colstart, colend, rowstart, rowend
int left = searchColumns(0, y, 0, m, true);
int right = searchColumns(y + 1, n, 0, m, false);
//search for rowstart, row end, colstart, colend
int top = searchRows(0, x, left, right, true);
//search for rowstart, row end, colstart, colend
int bottom = searchRows(x + 1, m, left, right, false);
return (right - left) * (bottom - top);
}
private int searchColumns(int i, int j, int top, int bottom, boolean whiteToBlack) {
while (i != j) {
int k = top, mid = (i + j) / 2;
//traverse the rows for this column that has zeros
while (k < bottom && image[k][mid] == '0') k++;
//if couldn't reach the last row and opted then next iteration only searches till this col
if (k < bottom == whiteToBlack)
j = mid;
else//if not opted or could reach last row, start from mid onwards
i = mid + 1;
}
return i;
}
private int searchRows(int i, int j, int left, int right, boolean whiteToBlack) {
while (i != j) {
int k = left, mid = (i + j) / 2;
while (k < right && image[mid][k] == '0') ++k;
if (k < right == whiteToBlack)
j = mid;
else
i = mid + 1;
}
return i;
}
}
An image is represented by a binary matrix with 0 as a white pixel and 1 as a black pixel. The black pixels are connected, i.e., there is only one black region. Pixels are connected horizontally and vertically. Given the location (x, y) of one of the black pixels, return the area of the smallest (axis-aligned) rectangle that encloses all black pixels.
For example, given the following image:
[
"0010",
"0110",
"0100"
]
and x = 0, y = 2, Return 6.
*/
public class SmallestRectangleEnclosingBlackPixels{
/**
Sol1: use two nested loops and keep track the the leftmost col, upmost row, rightmost col, and bottommost row where we find 1. Use these four points to find the area
O(m*n), O(1)
*/
public int minArea1(char[][] image, int x, int y) {
int top = x, bottom = x;
int left = y, right = y;
for (x = 0; x < image.length; ++x) {
for (y = 0; y < image[0].length; ++y) {
if (image[x][y] == '1') {
top = Math.min(top, x);
bottom = Math.max(bottom, x + 1);
left = Math.min(left, y);
right = Math.max(right, y + 1);
}
}
}
return (right - left) * (bottom - top);
}
/**
Solution2:
Intuition
Explore all the connected black pixel from the given pixel and update the boundaries.
Algorithm
The naive approach did not use the condition that all the black pixels are connected and that one of the black pixels is given.
A simple way to use these facts is to do an exhaustive search starting from the given pixel. Since all the black pixels are connected, DFS or BFS will visit all of them starting from the given black pixel. The idea is similar to what we did for 200. Number of Island. Instead of many islands, we have only one island here, and we know one pixel of it.
*/
private int top, bottom, left, right;
public int minArea2(char[][] image, int x, int y) {
if(image.length == 0 || image[0].length == 0) return 0;
top = bottom = x;
left = right = y;
dfs(image, x, y);
return (right - left) * (bottom - top);
}
private void dfs(char[][] image, int x, int y){
if(x < 0 || y < 0 || x >= image.length || y >= image[0].length ||
image[x][y] == '0')
return;
image[x][y] = '0'; // mark visited black pixel as white
top = Math.min(top, x);
bottom = Math.max(bottom, x + 1);
left = Math.min(left, y);
right = Math.max(right, y + 1);
dfs(image, x + 1, y);
dfs(image, x - 1, y);
dfs(image, x, y - 1);
dfs(image, x, y + 1);
}
/**
Solution3:
Intuition
Project the 2D image into a 1D array and use binary search to find the boundaries.
Algorithm
matrix projection
*Figure 1. Illustration of image projection.
Suppose we have a image as shown in figure 1, if we project each column of the image into an entry of row vector v with the following rule:
v[i] = 1 if exists x such that image[x][i] = 1
v[i] = 0 otherwise
That is
If a column has any black pixel it's projection is black otherwise white.
Similarly, we can do the same for the rows, and project the image into a 1D column vector. The two projected vectors are shown in figure 1.
Now, we claim the following lemma:
Lemma
If there are only one black pixel region, then in a projected 1D array all the black pixels are connected.
Proof by contradiction
Assume to the contrary that there are disconnected black pixels at i and j where i < j in the 1D projection array. Thus, there exists one column k, k in (i, j) and the column k in the 2D array has no black pixel. Therefore, in the 2D array there exist at least two black pixel regions separated by column k which contradicting the condition of "only one black pixel region". Therefore, we conclude that all the black pixels in the 1D projection array are connected.
With this lemma, we have the following algorithm:
Project the 2D array into a column array and a row array
Binary search to find left in the row array within [0, y)
Binary search to find right in the row array within [y + 1, n)
Binary search to find top in the column array within [0, x)
Binary search to find bottom in the column array within [x + 1, m)
Return (right - left) * (bottom - top)
However, the projection step cost time which dominates the entire algorithm.If so, we gain nothing comparing with previous approaches.
The trick is that we do not need to do the projection step as a preprocess. We can do it on the fly, i.e. "don't project the column/row unless needed".
Recall the binary search algorithm in a 1D array, each time we only check one element, the pivot, to decide which half we go next.
In a 2D array, we can do something similar. The only difference here is that the element is not a number but a vector. For example, a m by n matrix can be seen as n column vectors.
In these n elements/vectors, we do a binary search to find left or right. Each time we only check one element/vector, the pivot, to decide which half we go next. In total it checks vectors, and each check is (we simply traverse all the m entries of the pivot vector).
So it costs to find left and right. Similarly it costs to find top and bottom.
To find the left boundary, do the binary search in the [0, y) range and find the first column vector who has any black pixel.
To determine if a column vector has a black pixel is O(m) so the search in total is O(m log n)
We can do the same for the other boundaries. The area is then calculated by the boundaries. Thus the algorithm runs in O(m log n + n log m)
*/
private char[][] image;
public int minArea3(char[][] iImage, int x, int y) {
image = iImage;
int m = image.length, n = image[0].length;
//search for colstart, colend, rowstart, rowend
int left = searchColumns(0, y, 0, m, true);
int right = searchColumns(y + 1, n, 0, m, false);
//search for rowstart, row end, colstart, colend
int top = searchRows(0, x, left, right, true);
//search for rowstart, row end, colstart, colend
int bottom = searchRows(x + 1, m, left, right, false);
return (right - left) * (bottom - top);
}
private int searchColumns(int i, int j, int top, int bottom, boolean whiteToBlack) {
while (i != j) {
int k = top, mid = (i + j) / 2;
//traverse the rows for this column that has zeros
while (k < bottom && image[k][mid] == '0') k++;
//if couldn't reach the last row and opted then next iteration only searches till this col
if (k < bottom == whiteToBlack)
j = mid;
else//if not opted or could reach last row, start from mid onwards
i = mid + 1;
}
return i;
}
private int searchRows(int i, int j, int left, int right, boolean whiteToBlack) {
while (i != j) {
int k = left, mid = (i + j) / 2;
while (k < right && image[mid][k] == '0') ++k;
if (k < right == whiteToBlack)
j = mid;
else
i = mid + 1;
}
return i;
}
}
No comments:
Post a Comment