LeetCode 302: Smallest Rectangle Enclosing Black Pixels Solution

Master LeetCode problem 302 (Smallest Rectangle Enclosing Black Pixels), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

302. Smallest Rectangle Enclosing Black Pixels

Hard

Array Binary Search Depth-First Search Breadth-First Search Matrix

Problem Explanation

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.

Solution Code

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;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 302 (Smallest Rectangle Enclosing Black Pixels)?

This page provides optimized solutions for LeetCode problem 302 (Smallest Rectangle Enclosing Black Pixels) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 302 (Smallest Rectangle Enclosing Black Pixels)?

The time complexity for LeetCode 302 (Smallest Rectangle Enclosing Black Pixels) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 302 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 302 in Java, C++, or Python.

Back to LeetCode Solutions