Find the largest rectangle containing only zeros in the N × N binary matrix

Question

Given the binary matrix NxN (containing only 0 or 1), how can we find the largest rectangle containing all 0?

Example:

I 0 0 0 0 1 0 0 0 1 0 0 1 II->0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 <--IV 0 0 1 0 0 0 IV 

In the above example, this is binary matrix 6 and times; 6. the return value in this case will be cell 1: (2, 1) and cell 2: (4, 4). The resulting sub-matrix can be square or rectangular. The return value may also be the size of the largest submatrix of all 0, in this example 3 × four.

Answer 1

Here is a solution based on the "Biggest Rectangle in a Bar Graph " problem suggested by @j_random_hacker in the comments:

[Algorithm] works by looping through the lines from top to bottom for each line that solves this problem , where the "bars" in the "histogram" consist of all continuous ascending chains of zeros that start from the current line (the column has a height of 0 if it has 1 in the current line )

The input matrix mat can be an arbitrary iteration, for example, a file or a network stream. Only one row should be available at a time.

 #!/usr/bin/env python from collections import namedtuple from operator import mul Info = namedtuple('Info', 'start height') def max_size(mat, value=0): """Find height, width of the largest rectangle containing all 'value''s.""" it = iter(mat) hist = [(el==value) for el in next(it, [])] max_size = max_rectangle_size(hist) for row in it: hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)] max_size = max(max_size, max_rectangle_size(hist), key=area) return max_size def max_rectangle_size(histogram): """Find height, width of the largest rectangle that fits entirely under the histogram. """ stack = [] top = lambda: stack[-1] max_size = (0, 0) # height, width of the largest rectangle pos = 0 # current position in the histogram for pos, height in enumerate(histogram): start = pos # position where rectangle starts while True: if not stack or height > top().height: stack.append(Info(start, height)) # push elif stack and height < top().height: max_size = max(max_size, (top().height, (pos - top().start)), key=area) start, _ = stack.pop() continue break # height == top().height goes here pos += 1 for start, height in stack: max_size = max(max_size, (height, (pos - start)), key=area) return max_size def area(size): return reduce(mul, size) 

The solution is O(N) , where N is the number of elements in the matrix. O(ncols) extra memory is required, where ncols is the number of columns in the matrix.

The latest version with tests is located at https://gist.github.com/776423

Answer 2

Please take a look at Enlarge the rectangular area below the histogram , and then continue to read the solution below.

 Traverse the matrix once and store the following; For x=1 to N and y=1 to NF[x][y] = 1 + F[x][y-1] if A[x][y] is 0 , else 0 Then for each row for x=N to 1 We have F[x] -> array with heights of the histograms with base at x. Use O(N) algorithm to find the largest area of rectangle in this histogram = H[x] From all areas computed, report the largest. 

Time complexity - O (N * N) = O (N²) (for binary matrix NxN)

Example:

 Initial array F[x][y] array 0 0 0 0 1 0 1 1 1 1 0 1 0 0 1 0 0 1 2 2 0 2 1 0 0 0 0 0 0 0 3 3 1 3 2 1 1 0 0 0 0 0 0 4 2 4 3 2 0 0 0 0 0 1 1 5 3 5 4 0 0 0 1 0 0 0 2 6 0 6 5 1 For x = N to 1 H[6] = 2 6 0 6 5 1 -> 10 (5*2) H[5] = 1 5 3 5 4 0 -> 12 (3*4) H[4] = 0 4 2 4 3 2 -> 10 (2*5) H[3] = 3 3 1 3 2 1 -> 6 (3*2) H[2] = 2 2 0 2 1 0 -> 4 (2*2) H[1] = 1 1 1 1 0 1 -> 4 (1*4) The largest area is thus H[5] = 12 

Answer 3

Here is a Python3 solution that returns a position in addition to the area of ​​the largest rectangle:

 #!/usr/bin/env python3 import numpy s = '''0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0''' nrows = 6 ncols = 6 skip = 1 area_max = (0, []) a = numpy.fromstring(s, dtype=int, sep=' ').reshape(nrows, ncols) w = numpy.zeros(dtype=int, shape=a.shape) h = numpy.zeros(dtype=int, shape=a.shape) for r in range(nrows): for c in range(ncols): if a[r][c] == skip: continue if r == 0: h[r][c] = 1 else: h[r][c] = h[r-1][c]+1 if c == 0: w[r][c] = 1 else: w[r][c] = w[r][c-1]+1 minw = w[r][c] for dh in range(h[r][c]): minw = min(minw, w[r-dh][c]) area = (dh+1)*minw if area > area_max[0]: area_max = (area, [(r-dh, c-minw+1, r, c)]) print('area', area_max[0]) for t in area_max[1]: print('Cell 1:({}, {}) and Cell 2:({}, {})'.format(*t)) 

Exit:

 area 12 Cell 1:(2, 1) and Cell 2:(4, 4) 

Answer 4

Here is the JF Sebastians method translated into C #:

 private Vector2 MaxRectSize(int[] histogram) { Vector2 maxSize = Vector2.zero; int maxArea = 0; Stack<Vector2> stack = new Stack<Vector2>(); int x = 0; for (x = 0; x < histogram.Length; x++) { int start = x; int height = histogram[x]; while (true) { if (stack.Count == 0 || height > stack.Peek().y) { stack.Push(new Vector2(start, height)); } else if(height < stack.Peek().y) { int tempArea = (int)(stack.Peek().y * (x - stack.Peek().x)); if(tempArea > maxArea) { maxSize = new Vector2(stack.Peek().y, (x - stack.Peek().x)); maxArea = tempArea; } Vector2 popped = stack.Pop(); start = (int)popped.x; continue; } break; } } foreach (Vector2 data in stack) { int tempArea = (int)(data.y * (x - data.x)); if(tempArea > maxArea) { maxSize = new Vector2(data.y, (x - data.x)); maxArea = tempArea; } } return maxSize; } public Vector2 GetMaximumFreeSpace() { // STEP 1: // build a seed histogram using the first row of grid points // example: [true, true, false, true] = [1,1,0,1] int[] hist = new int[gridSizeY]; for (int y = 0; y < gridSizeY; y++) { if(!invalidPoints[0, y]) { hist[y] = 1; } } // STEP 2: // get a starting max area from the seed histogram we created above. // using the example from above, this value would be [1, 1], as the only valid area is a single point. // another example for [0,0,0,1,0,0] would be [1, 3], because the largest area of contiguous free space is 3. // Note that at this step, the heigh fo the found rectangle will always be 1 because we are operating on // a single row of data. Vector2 maxSize = MaxRectSize(hist); int maxArea = (int)(maxSize.x * maxSize.y); // STEP 3: // build histograms for each additional row, re-testing for new possible max rectangluar areas for (int x = 1; x < gridSizeX; x++) { // build a new histogram for this row. the values of this row are // 0 if the current grid point is occupied; otherwise, it is 1 + the value // of the previously found historgram value for the previous position. // What this does is effectly keep track of the height of continous avilable spaces. // EXAMPLE: // Given the following grid data (where 1 means occupied, and 0 means free; for clairty): // INPUT: OUTPUT: // 1.) [0,0,1,0] = [1,1,0,1] // 2.) [0,0,1,0] = [2,2,0,2] // 3.) [1,1,0,1] = [0,0,1,0] // // As such, you'll notice position 1,0 (row 1, column 0) is 2, because this is the height of contiguous // free space. for (int y = 0; y < gridSizeY; y++) { if(!invalidPoints[x, y]) { hist[y] = 1 + hist[y]; } else { hist[y] = 0; } } // find the maximum size of the current histogram. If it happens to be larger // that the currently recorded max size, then it is the new max size. Vector2 maxSizeTemp = MaxRectSize(hist); int tempArea = (int)(maxSizeTemp.x * maxSizeTemp.y); if (tempArea > maxArea) { maxSize = maxSizeTemp; maxArea = tempArea; } } // at this point, we know the max size return maxSize; } 

A few notes about this:

• This version is intended for use with the Unity API. You can easily make this more general by replacing Vector2 instances with KeyValuePair. Vector2 is used only for a convenient way to store two values.
• invalidPoints [] is a bool array, where true means that the grid point is "used" and false means that it is not.

Answer 5

A solution with spatial complexity O (columns) [Can also be changed to O (rows)] and time complexity O (rows * columns)

 public int maximalRectangle(char[][] matrix) { int m = matrix.length; if (m == 0) return 0; int n = matrix[0].length; int maxArea = 0; int[] aux = new int[n]; for (int i = 0; i < n; i++) { aux[i] = 0; } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { aux[j] = matrix[i][j] - '0' + aux[j]; maxArea = Math.max(maxArea, maxAreaHist(aux)); } } return maxArea; } public int maxAreaHist(int[] heights) { int n = heights.length; Stack<Integer> stack = new Stack<Integer>(); stack.push(0); int maxRect = heights[0]; int top = 0; int leftSideArea = 0; int rightSideArea = heights[0]; for (int i = 1; i < n; i++) { if (stack.isEmpty() || heights[i] >= heights[stack.peek()]) { stack.push(i); } else { while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) { top = stack.pop(); rightSideArea = heights[top] * (i - top); leftSideArea = 0; if (!stack.isEmpty()) { leftSideArea = heights[top] * (top - stack.peek() - 1); } else { leftSideArea = heights[top] * top; } maxRect = Math.max(maxRect, leftSideArea + rightSideArea); } stack.push(i); } } while (!stack.isEmpty()) { top = stack.pop(); rightSideArea = heights[top] * (n - top); leftSideArea = 0; if (!stack.isEmpty()) { leftSideArea = heights[top] * (top - stack.peek() - 1); } else { leftSideArea = heights[top] * top; } maxRect = Math.max(maxRect, leftSideArea + rightSideArea); } return maxRect; } 

But I get Time Limite exceeding excpetion when I try to do this on LeetCode. Is there a less complicated solution?

Answer 6

I suggest the O (nxn) method.

First you can list all the maximum empty rectangles. Empty means that it covers only 0s. The maximum empty rectangle is such that it cannot be expanded in a direction that does not cover (at least) 1.

Paper representing the O (nxn) algorithm for creating such a list can be found at www.ulg.ac.be/telecom/rectangles , as well as the source code (not optimized). There is no need to store the list, just call the callback function every time the algorithm finds a rectangle, and save only the largest one (or choose another criterion if you want).

Note that there is evidence (see article) that the number of largest empty rectangles is limited by the number of pixels in the image (in this case nxn).

Therefore, the choice of the optimal rectangle can be made in O (nxn), and the general method is also O (nxn).

In practice, this method is very fast and is used to analyze the video stream in real time.

Answer 7

Here is the jfs solution version that also provides the largest rectangle position:

 from collections import namedtuple from operator import mul Info = namedtuple('Info', 'start height') def max_rect(mat, value=0): """returns (height, width, left_column, bottom_row) of the largest rectangle containing all 'value''s. Example: [[0, 0, 0, 0, 0, 0, 0, 0, 3, 2], [0, 4, 0, 2, 4, 0, 0, 1, 0, 0], [1, 0, 1, 0, 0, 0, 3, 0, 0, 4], [0, 0, 0, 0, 4, 2, 0, 0, 0, 0], [0, 0, 0, 2, 0, 0, 0, 0, 0, 0], [4, 3, 0, 0, 1, 2, 0, 0, 0, 0], [3, 0, 0, 0, 2, 0, 0, 0, 0, 4], [0, 0, 0, 1, 0, 3, 2, 4, 3, 2], [0, 3, 0, 0, 0, 2, 0, 1, 0, 0]] gives: (3, 4, 6, 5) """ it = iter(mat) hist = [(el==value) for el in next(it, [])] max_rect = max_rectangle_size(hist) + (0,) for irow,row in enumerate(it): hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)] max_rect = max(max_rect, max_rectangle_size(hist) + (irow+1,), key=area) # irow+1, because we already used one row for initializing max_rect return max_rect def max_rectangle_size(histogram): stack = [] top = lambda: stack[-1] max_size = (0, 0, 0) # height, width and start position of the largest rectangle pos = 0 # current position in the histogram for pos, height in enumerate(histogram): start = pos # position where rectangle starts while True: if not stack or height > top().height: stack.append(Info(start, height)) # push elif stack and height < top().height: max_size = max(max_size, (top().height, (pos - top().start), top().start), key=area) start, _ = stack.pop() continue break # height == top().height goes here pos += 1 for start, height in stack: max_size = max(max_size, (height, (pos - start), start), key=area) return max_size def area(size): return size[0] * size[1]