Smallest Rectangle Enclosing Black Pixels

Problem#

Given a black-and-white image ('1' is black, '0' is white) and the coordinates (x, y) of one black pixel, return the area of the smallest axis-aligned rectangle that contains all black pixels. All black pixels are connected.

Examples#

image = [["0","0","1","0"],["0","1","1","0"],["0","1","0","0"]], x = 0, y = 2 → 6
image = [["1"]], x = 0, y = 0 → 1

Constraints#

1 <= m, n <= 100, at least one black pixel exists.

Approach#

For each of the four boundaries, define a monotone predicate “this row/column contains a black pixel” and binary search the extreme row/column. Connectivity guarantees the predicate flips exactly once on each side of (x, y).

Solution#

class Solution {
public:
    int minArea(vector<vector<char>>& image, int x, int y) {
        int m = image.size(), n = image[0].size();
        auto rowHasBlack = [&](int r) {
            for (int j = 0; j < n; ++j) if (image[r][j] == '1') return true;
            return false;
        };
        auto colHasBlack = [&](int c) {
            for (int i = 0; i < m; ++i) if (image[i][c] == '1') return true;
            return false;
        };
        int top = bsearch(0, x, true, rowHasBlack);
        int bottom = bsearch(x + 1, m, false, rowHasBlack);
        int left = bsearch(0, y, true, colHasBlack);
        int right = bsearch(y + 1, n, false, colHasBlack);
        return (bottom - top) * (right - left);
    }
private:
    template<class F>
    int bsearch(int lo, int hi, bool findFirstTrue, F pred) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (findFirstTrue) {
                if (pred(mid)) hi = mid;
                else lo = mid + 1;
            } else {
                if (pred(mid)) lo = mid + 1;
                else hi = mid;
            }
        }
        return lo;
    }
};

func minArea(image [][]byte, x int, y int) int {
    m, n := len(image), len(image[0])
    rowHasBlack := func(r int) bool {
        for j := 0; j < n; j++ {
            if image[r][j] == '1' {
                return true
            }
        }
        return false
    }
    colHasBlack := func(c int) bool {
        for i := 0; i < m; i++ {
            if image[i][c] == '1' {
                return true
            }
        }
        return false
    }
    bsearch := func(lo, hi int, findFirstTrue bool, pred func(int) bool) int {
        for lo < hi {
            mid := lo + (hi-lo)/2
            if findFirstTrue {
                if pred(mid) {
                    hi = mid
                } else {
                    lo = mid + 1
                }
            } else {
                if pred(mid) {
                    lo = mid + 1
                } else {
                    hi = mid
                }
            }
        }
        return lo
    }
    top := bsearch(0, x, true, rowHasBlack)
    bottom := bsearch(x+1, m, false, rowHasBlack)
    left := bsearch(0, y, true, colHasBlack)
    right := bsearch(y+1, n, false, colHasBlack)
    return (bottom - top) * (right - left)
}

from typing import Callable, List

class Solution:
    def minArea(self, image: List[List[str]], x: int, y: int) -> int:
        m, n = len(image), len(image[0])

        def row_has_black(r: int) -> bool:
            return any(image[r][j] == '1' for j in range(n))

        def col_has_black(c: int) -> bool:
            return any(image[i][c] == '1' for i in range(m))

        def bsearch(lo: int, hi: int, find_first_true: bool, pred: Callable[[int], bool]) -> int:
            while lo < hi:
                mid = lo + (hi - lo) // 2
                if find_first_true:
                    if pred(mid):
                        hi = mid
                    else:
                        lo = mid + 1
                else:
                    if pred(mid):
                        lo = mid + 1
                    else:
                        hi = mid
            return lo

        top = bsearch(0, x, True, row_has_black)
        bottom = bsearch(x + 1, m, False, row_has_black)
        left = bsearch(0, y, True, col_has_black)
        right = bsearch(y + 1, n, False, col_has_black)
        return (bottom - top) * (right - left)

function minArea(image, x, y) {
    const m = image.length, n = image[0].length;
    const rowHasBlack = (r) => {
        for (let j = 0; j < n; j++) if (image[r][j] === '1') return true;
        return false;
    };
    const colHasBlack = (c) => {
        for (let i = 0; i < m; i++) if (image[i][c] === '1') return true;
        return false;
    };
    const bsearch = (lo, hi, findFirstTrue, pred) => {
        while (lo < hi) {
            const mid = lo + ((hi - lo) >> 1);
            if (findFirstTrue) {
                if (pred(mid)) hi = mid;
                else lo = mid + 1;
            } else {
                if (pred(mid)) lo = mid + 1;
                else hi = mid;
            }
        }
        return lo;
    };
    const top = bsearch(0, x, true, rowHasBlack);
    const bottom = bsearch(x + 1, m, false, rowHasBlack);
    const left = bsearch(0, y, true, colHasBlack);
    const right = bsearch(y + 1, n, false, colHasBlack);
    return (bottom - top) * (right - left);
}

class Solution {
    private char[][] image;
    private int m, n;

    private boolean rowHasBlack(int r) {
        for (int j = 0; j < n; j++) if (image[r][j] == '1') return true;
        return false;
    }

    private boolean colHasBlack(int c) {
        for (int i = 0; i < m; i++) if (image[i][c] == '1') return true;
        return false;
    }

    private int bsearchRow(int lo, int hi, boolean findFirstTrue) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (findFirstTrue) {
                if (rowHasBlack(mid)) hi = mid;
                else lo = mid + 1;
            } else {
                if (rowHasBlack(mid)) lo = mid + 1;
                else hi = mid;
            }
        }
        return lo;
    }

    private int bsearchCol(int lo, int hi, boolean findFirstTrue) {
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (findFirstTrue) {
                if (colHasBlack(mid)) hi = mid;
                else lo = mid + 1;
            } else {
                if (colHasBlack(mid)) lo = mid + 1;
                else hi = mid;
            }
        }
        return lo;
    }

    public int minArea(char[][] image, int x, int y) {
        this.image = image;
        this.m = image.length;
        this.n = image[0].length;
        int top = bsearchRow(0, x, true);
        int bottom = bsearchRow(x + 1, m, false);
        int left = bsearchCol(0, y, true);
        int right = bsearchCol(y + 1, n, false);
        return (bottom - top) * (right - left);
    }
}

function minArea(image: string[][], x: number, y: number): number {
    const m = image.length, n = image[0].length;
    const rowHasBlack = (r: number): boolean => {
        for (let j = 0; j < n; j++) if (image[r][j] === '1') return true;
        return false;
    };
    const colHasBlack = (c: number): boolean => {
        for (let i = 0; i < m; i++) if (image[i][c] === '1') return true;
        return false;
    };
    const bsearch = (lo: number, hi: number, findFirstTrue: boolean, pred: (i: number) => boolean): number => {
        while (lo < hi) {
            const mid = lo + ((hi - lo) >> 1);
            if (findFirstTrue) {
                if (pred(mid)) hi = mid;
                else lo = mid + 1;
            } else {
                if (pred(mid)) lo = mid + 1;
                else hi = mid;
            }
        }
        return lo;
    };
    const top = bsearch(0, x, true, rowHasBlack);
    const bottom = bsearch(x + 1, m, false, rowHasBlack);
    const left = bsearch(0, y, true, colHasBlack);
    const right = bsearch(y + 1, n, false, colHasBlack);
    return (bottom - top) * (right - left);
}

Editorial#

Each binary search runs O(log dimension) iterations and each iteration scans an entire row or column in linear time. The connectivity of black pixels makes the predicate monotone on either side of the given point — that’s what unlocks binary search over a 2D image.

Complexity#

Time: O(m log n + n log m).
Space: O(1).

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Examples#

Constraints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#