Obtain location of largest rectangle

Question

I'm trying to follow the code in the answer here: Find largest rectangle containing only zeros in an N×N binary matrix

I'm having difficulty understanding how to find the origin (x,y) of the largest rectangle found by the algorithm.

from collections

import namedtuple
from operator import mul
import numpy as np
import functools

x = np.zeros(shape=(4,5))
x[0][0] = 1
x[0][1] = 1
x[0][2] = 1
x[0][3] = 1
x[1][0] = 1
x[1][1] = 1
x[1][2] = 1
x[1][3] = 1
print(x)
print(max_size(x))

Info = namedtuple('Info', 'start height')

def find_maximum_frame(mat, value=1):
    """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)
    old_size = (0,0)
    coordinates = None
    for y,row in enumerate(it):
        hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
        new_rect, c = max_rectangle_size(hist)
        max_size = max(max_size, new_rect, key=area)
        if max_size[0]*max_size[1] > old_size[0]*old_size[1]:
            coordinates = [c[0], (y+2)-max_size[0]]
        old_size = max_size
    return [max_size, coordinates]

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
                print(stack)
            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
    coordinates = [0,0]
    old_size = (0,0)
    for start, height in stack:
        max_size = max(max_size, (height, (pos - start)), key=area)
        if max_size[0]*max_size[1] > old_size[0]*old_size[1]:
            coordinates = [start,height]
        old_size = max_size
    return [max_size, coordinates]

def area(size):
    return functools.reduce(mul, size)

The above code seems to work to in my example to find the upper left-hand corner of the rectangle, but when I try it on a larger image it's breaking down and I can't debug why.

Answer 1

Here a solution that modifies the Gist version of J.F. Sebastian's answer:

from collections import namedtuple

Info = namedtuple('Info', 'start height')

# returns height, width, and position of the top left corner of the largest
#  rectangle with the given value in mat
def max_size(mat, value=0):
    it = iter(mat)
    hist = [(el==value) for el in next(it, [])]
    max_size_start, start_row = max_rectangle_size(hist), 0
    for i, row in enumerate(it):
        hist = [(1+h) if el == value else 0 for h, el in zip(hist, row)]
        mss = max_rectangle_size(hist)
        if area(mss) > area(max_size_start):
            max_size_start, start_row = mss, i+2-mss[0]
    return max_size_start[:2], (start_row, max_size_start[2])

# returns height, width, and start column of the largest rectangle that
#  fits entirely under the histogram
def max_rectangle_size(histogram):
    stack = []
    top = lambda: stack[-1]
    max_size_start = (0, 0, 0) # height, width, start 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_start = max(
                    max_size_start,
                    (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_start = max(max_size_start, (height, pos - start, start),
            key=area)

    return max_size_start

def area(size): return size[0]*size[1]

The code passes all tests from the Gist version once the positions are added to the tests. Here, e.g., the first test:

    self.assertEqual(max_size(self.__s2m("""
    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""")), ((3, 4), (2, 1)))

The rectangle of size (3, 4) is at position (2, 1).

Answer 2

Here is the solution to the same problem of hackerrank...

public static long largestRectangle(List<Integer> h) {
// Write your code here
Stack<Integer> st1 = new Stack<>();
int i = 0;
int topIndex = 0;
long area;
long finalArea=0;
while(i<h.size()){
  if(st1.isEmpty() || h.get(st1.peek()) <= h.get(i)){
    st1.push(i++);
  }else{
    topIndex = st1.peek();
    st1.pop();
    
    area = h.get(topIndex) * (st1.isEmpty() ? i : i-1-st1.peek());
    if(area > finalArea ){
      finalArea = area;
    }
  }
}
while(st1.isEmpty()==false){
  topIndex = st1.peek();
  st1.pop();
  area = h.get(topIndex) * (st1.isEmpty() ? i : i-1-st1.peek());
    if(area > finalArea ){
      finalArea = area;
    }
}
return finalArea;

}