> For the complete documentation index, see [llms.txt](https://blog.yushunchen.com/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blog.yushunchen.com/algo/binary-search/smallest-rectangle-enclosing-black-pixels.md).

# Smallest Rectangle Enclosing Black Pixels

{% embed url="<https://www.lintcode.com/problem/600/>" %}

## Solution 1 (Java)

```java
public class Solution {
    /**
     * @param image: a binary matrix with '0' and '1'
     * @param x: the location of one of the black pixels
     * @param y: the location of one of the black pixels
     * @return: an integer
     */
    public int minArea(char[][] image, int x, int y) {
        if (image == null || image.length == 0 || image[0].length == 0) {
            return -1;
        }

        int row = image.length - 1, col = image[0].length - 1;
        int left = findLeftBound(image, 0, y);
        int right = findRightBound(image, y, col);
        int top = findTopBound(image, 0, x);
        int bottom = findBottomBound(image, x, row);

        return (right - left + 1) * (bottom - top + 1);
    }

    private int findLeftBound(char[][] image, int start, int end) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (colHasBlackPixel(image, mid)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (colHasBlackPixel(image, start)) {
            return start;
        }
        return end;
    }

    private int findRightBound(char[][] image, int start, int end) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (colHasBlackPixel(image, mid)) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (colHasBlackPixel(image, end)) {
            return end;
        }
        return start;
    }

    private int findTopBound(char[][] image, int start, int end) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (rowHasBlackPixel(image, mid)) {
                end = mid;
            } else {
                start = mid;
            }
        }
        if (rowHasBlackPixel(image, start)) {
            return start;
        }
        return end;
    }

    private int findBottomBound(char[][] image, int start, int end) {
        while (start + 1 < end) {
            int mid = start + (end - start) / 2;
            if (rowHasBlackPixel(image, mid)) {
                start = mid;
            } else {
                end = mid;
            }
        }
        if (rowHasBlackPixel(image, end)) {
            return end;
        }
        return start;
    }

    private boolean rowHasBlackPixel(char[][] image, int row) {
        for (int i = 0; i < image[0].length; i++) {
            if (image[row][i] == '1') return true;
        }
        return false;
    }
    
    private boolean colHasBlackPixel(char[][] image, int col) {
        for (int i = 0; i < image.length; i++) {
            if (image[i][col] == '1') return true;
        }
        return false;
    }
}
```

### Notes

* We use binary search to find the left, right, top, and bottom boundaries of the black area. Specifically, we are trying to find 1's in these four directions and reduce the range if we cannot.&#x20;


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://blog.yushunchen.com/algo/binary-search/smallest-rectangle-enclosing-black-pixels.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.