Smallest Rectangle Enclosing Black Pixels

update Aug 17,2017 17:20

LeetCode

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.

Basic Idea:

思路 1：二分法 上下左右分别搜索，时间复杂度应该是 O(mlogn + nlogm).

思路 2：BFS 或者 DFS 时间复杂度为O(Number of black pixels) == O(mn).

Python Code:

二分法：

    class Solution(object):
        def minArea(self, image, x, y):
            """
            :type image: List[List[str]]
            :type x: int
            :type y: int
            :rtype: int
            """
            up = self.searchUp(image, x)
            down = self.searchDown(image, x)
            left = self.searchLeft(image, y)
            right = self.searchRight(image, y)

            print (up, down, left, right)

            return (down - up + 1) * (right - left + 1)


        def searchCol(self, image, col):
            for i in range(len(image)):
                if image[i][col] == '1':
                    return True
            return False

        def searchRow(self, image, row):
            for i in range(len(image[0])):
                if image[row][i] == '1':
                    return True
            return False

        def searchUp(self, image, row):
            p, r = 0, row
            while p + 1 < r:
                q = (p + r) / 2
                if self.searchRow(image, q):
                    r = q
                else:
                    p = q
            if self.searchRow(image, p):
                return p
            else:
                return r

        def searchDown(self, image, row):
            p, r = row, len(image) - 1
            while p + 1 < r:
                q = (p + r) / 2
                if self.searchRow(image, q):
                    p = q
                else:
                    r = q
            if self.searchRow(image, r):
                return r
            else:
                return p

        def searchLeft(self, image, col):
            p, r = 0, col
            while p + 1 < r:
                q = (p + r) / 2
                if self.searchCol(image, q):
                    r = q
                else:
                    p = q
            if self.searchCol(image, p):
                return p
            else:
                return r

        def searchRight(self, image, col):
            p, r = col, len(image[0]) - 1
            while p + 1 < r:
                q = (p + r) / 2
                if self.searchCol(image, q):
                    p = q
                else:
                    r = q
            if self.searchCol(image, r):
                return r
            else:
                return p

Java Code：

DFS：

    // dfs solution
    public class Solution {
        private int[] dr = null;
        private int[] dc = null;
        private int up;
        private int down;
        private int left;
        private int right;
        public int minArea(char[][] image, int x, int y) {
            dr = new int[] {0, 1, 0, -1};
            dc = new int[] {1, 0, -1, 0};
            up = down = x;
            left = right = y;
            dfs(image, x, y);
            return (right - left + 1) * (down - up + 1);
        }

        private void dfs(char[][] image, int r, int c) {
            if (! isValid(image, r, c) || image[r][c] == '0') return;
            image[r][c] = '0';
            if (r < up) up = r;
            if (r > down) down = r;
            if (c < left) left = c;
            if (c > right) right = c;
            for (int i = 0; i < dr.length; ++i) {
                dfs(image, r + dr[i], c + dc[i]);
            }
        }

        private boolean isValid(char[][] image, int r, int c) {
            if (r < 0 || c < 0 || r >= image.length || c >= image[0].length) 
                return false;
            return true;
        }
    }

BFS:

    // bfs solution
    public class Solution {
        private class Coord {
            int r;
            int c;
            public Coord(int r, int c) {
                this.r = r;
                this.c = c;
            }
        }

        private int[] dr = null;
        private int[] dc = null;
        private int up;
        private int down;
        private int left;
        private int right;
        public int minArea(char[][] image, int x, int y) {
            dr = new int[] {0, 1, 0, -1};
            dc = new int[] {1, 0, -1, 0};
            up = down = x;
            left = right = y;
            bfs(image, x, y);
            return (right - left + 1) * (down - up + 1);
        }
        private void bfs(char[][] image, int r, int c) {
            Deque<Coord> queue = new LinkedList<>();
            queue.addFirst(new Coord(r, c));
            while (! queue.isEmpty()) {
                Coord coord = queue.removeLast();
                r = coord.r;
                c = coord.c;
                image[r][c] = '0';
                if (r < up) up = r;
                if (r > down) down = r;
                if (c < left) left = c;
                if (c > right) right = c;
                for (int i = 0; i < dc.length; ++i) {
                    int nr = r + dr[i];
                    int nc = c + dc[i];
                    if (isValid(image, nr, nc) && image[nr][nc] == '1') {
                        queue.addFirst(new Coord(nr, nc));
                    }

                }
            }
        }
        private boolean isValid(char[][] image, int r, int c) {
            if (r < 0 || c < 0 || r >= image.length || c >= image[0].length) 
                return false;
            return true;
        }
    }

update Dec 16, 2017

Python BFS solution

    # bfs solution
    class Solution:
        def minArea(self, image, x, y):
            """
            :type image: List[List[str]]
            :type x: int
            :type y: int
            :rtype: int
            """
            def isValid(x, y):
                if x < 0 or x >= len(image) or y < 0 or y >= len(image[0]):
                    return False
                return True

            dx = (0, -1, 0, 1)
            dy = (1, 0, -1, 0)
            up, down = x, x
            left, right = y, y
            queue = collections.deque()
            queue.appendleft((x, y))
            while queue:
                r, c = queue.pop()
                if not isValid(r, c) or image[r][c] == '0': 
                    continue
                image[r][c] = '0'
                up = min(up, r)
                down = max(down, r)
                left = min(left, c)
                right = max(right, c)
                for i in range(4):
                    queue.appendleft((r + dx[i], c + dy[i]));
            return (down - up + 1) * (right - left + 1)