302. Smallest Rectangle Enclosing Black Pixels
Explanation
To find the smallest rectangle enclosing black pixels, we can use binary search on both the rows and columns. We perform four binary searches to find the minimum row, maximum row, minimum column, and maximum column that contain black pixels.
We start by finding the leftmost column with black pixels using binary search. Then, we find the rightmost column with black pixels using binary search. Next, we find the topmost row with black pixels using binary search. Finally, we find the bottommost row with black pixels using binary search. The rectangle enclosing black pixels will be determined by these four boundaries.
Time Complexity
The time complexity of this solution is O(mlog(n) + nlog(m)) where m is the number of rows and n is the number of columns.
Space Complexity
The space complexity is O(1) as we are not using any extra space apart from some variables.
class Solution {
public int minArea(char[][] image, int x, int y) {
int top = binarySearch(image, true, 0, x, true);
int bottom = binarySearch(image, true, x + 1, image.length, false);
int left = binarySearch(image, false, 0, y, true);
int right = binarySearch(image, false, y + 1, image[0].length, false);
return (right - left) * (bottom - top);
}
private int binarySearch(char[][] image, boolean horizontal, int low, int high, boolean lower) {
while (low < high) {
int mid = low + (high - low) / 2;
boolean hasBlackPixel = false;
for (int i = 0; i < (horizontal ? image[0].length : image.length); i++) {
if ((horizontal ? image[mid][i] : image[i][mid]) == '1') {
hasBlackPixel = true;
break;
}
}
if (hasBlackPixel == lower) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
}Code Editor (Testing phase)
Improve Your Solution
Use the editor below to refine the provided solution. Select a programming language and try the following:
- Add import statement if required.
- Optimize the code for better time or space complexity.
- Add test cases to validate edge cases and common scenarios.
- Handle error conditions or invalid inputs gracefully.
- Experiment with alternative approaches to deepen your understanding.
Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.