## Find largest rectangle containing only zeros in an N×N binary matrix

Given an NxN binary matrix (containing only 0's or 1's), how can we go about finding largest rectangle containing all 0's?

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

For the above example, it is a 6×6 binary matrix. 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 can also be the size of the largest sub-matrix of all 0's, in this example 3 × 4.

Here's a solution based on the "Largest Rectangle in a Histogram" problem suggested by @j_random_hacker in the comments:

[Algorithm] works by iterating through rows from top to bottom, for each row solving this problem, where the "bars" in the "histogram" consist of all unbroken upward trails of zeros that start at the current row (a column has height 0 if it has a 1 in the current row).

The input matrix `mat`

may be an arbitrary iterable e.g., a file or a network stream. Only one row is required to 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 a matrix. It requires `O(ncols)`

additional memory, where `ncols`

is the number of columns in a matrix.

Latest version with tests is at https://gist.github.com/776423

**Maximum size rectangle binary sub-matrix with all 1s,** Given a 2D matrix of 0s and 1s, find maximum size rectangle of all 1s in this matrix.Duration: 6:55
Posted: May 14, 2015 It is the same problem that Find largest rectangle containing only zeros in an N×N binary matrix but in an upper dimension. Also, in my case, the largest rectangle can "cross the edge" of the array i.e. the space is like a torus for a 2D matrix. For a 2D array, if the entry is : 00111 00111 11000 00000 00111 the solution depicted by 'X' is

Please take a look at Maximize the rectangular area under Histogram and then continue reading the solution below.

Traverse the matrix once and store the following; For x=1 to N and y=1 to N F[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 is O(N*N) = O(N²) (for an NxN binary matrix)

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

**Maximum Size Rectangle of All 1's Dynamic Programming,** Maximal Rectangle. Hard. 2452 62. Add to List Share. Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its Find largest rectangle containing only zeros in an N×N binary matrix 1117 Easy interview question got harder: given numbers 1..100, find the missing number(s) given exactly k are missing

Here is a Python3 solution, which returns the 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))

Output:

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

**Maximal Rectangle,** You are given a matrix with n rows and m columns. Find the largest submatrix consisting of only zeros (a submatrix is a rectangular area of the matrix). Intersecting rectangle when bottom-left and top-right corners of two rectangles are given; Number of unique rectangles formed using N unit squares; Count the number of rectangles such that ratio of sides lies in the range [a,b] Largest subset of rectangles such that no rectangle fit in any other rectangle; Find sub-matrix with the given sum

Here is J.F. 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 things to note about this:

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

**Finding the largest zero submatrix,** Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle 0 : matrix[0].length; int[][] height = new int[m][n + 1]; int maxArea = 0; for (int i = 0; i < m; Maximal Rectangle Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area. Raw. maximalRectangle.cc.

Solution with space complexity O(columns) [Can be modified to O(rows) also] 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 exceeded excpetion when I try this on LeetCode. Is there any less complex solution?

**LeetCode – Maximal Rectangle (Java),** Thus, some overloaded machines cannot share their load with the other The first stage aims at finding all the maximum rectangles of zeros in Q,. be a configuration and v a speed matrix having n rows and m columns. lk denotes a subset The Cartesian product lk >< Jk is a rectangle of zeros in 0 if and only if: (20,1): 0 Find if there is a rectangle in binary matrix with corners as 1 Sliding Window Maximum (Maximum of all subarrays of size k) using stack in O(n) time Sliding Window Maximum (Maximum of all subarrays of size k)

**Flexibility and Robustness in Scheduling,** The time complexity of above solution is O(M x N) and auxiliary space used by the program is O(M x N). Exercise: Find the size of largest rectangular sub-matrix of We can use Hashing to find maximum length of sub-array in 1-D array in O(n) time. We fix the left and right columns one by one and find the largest sub-array with 0 sum contiguous rows for every left and right column pair.

**Find size of largest square sub-matrix of 1's present in given binary ,** Originally Answered: Given an N*M matrix of zeroes and ones, how can you find the biggest sub-rectangle in it which contains only ones? Process the lines in Given: A two-dimensional array b (M rows, N columns) of Boolean values ("0" and "1"). Required: Find the largest (most elements) rectangular subarray containing all ones. Figure 1 illustrates a possible input array and the corresponding solution. (I'll often refer to a rectangular subarray as simply a "rectangle.")

**What is the algorithmic approach to find the size of the maximum ,** Find the maximum among all instances of the largest rectangle. for (int i = 0; The largest square 2D subarray containing only 1s can be computed similarly, with a minor by the frequency of a character which is a number between zero and one. Hint: Reduce the problem from n characters to one on n − 1 characters. Given an array containing only 0s and 1s, find the largest subarray which contain equal no of 0s and 1s. Expected time complexity is O (n). A simple method is to use two nested loops. The outer loop picks a starting point i. The inner loop considers all subarrays starting from i. If size of a subarray is greater than maximum size so far, then