# Largest rectangle covering set bits in a bitmap

I have a 2D bitmap with various shapes (each pixel is either 1 or 0).

How can I find the largest axis-aligned rectangle that covers only set pixels?

• What do you mean by largest? In terms of area? Dec 3, 2021 at 19:58
• @YuvalFilmus yes, largest area Dec 3, 2021 at 19:59
• @PålGD 1D is easy, you can just do it in a single O(n) swipe left to right Dec 3, 2021 at 20:00
• Are you ok with an approximation? Dec 3, 2021 at 20:04
• You can in linear time compute the number of zeros in the rectangle (0,0) to (i,j). You can use this to query whether (up,left),(down,right) defines a valid rectangle in constant time. Dec 3, 2021 at 20:15

It can be done in $$O(n^3)$$ time, for a $$n\times n$$ bitmap.

Let $$A$$ denote the image, so $$A[i,j]$$ is the pixel at coordinates $$(i,j)$$.

For each pixel $$(i,j)$$, let $$H[i,j]$$ denote the height of the column of all-1 pixels below it, i.e., the largest $$h$$ such that $$A[i',j]=1$$ for all $$i' \in [i,i+h-1]$$.

For each pixel $$(i,j)$$ and each height $$h$$, let $$W[i,j,h]$$ denote the width of the rectangle of height $$h$$ with upper-left corner at $$(i,j)$$ that has covers only set pixels, i.e., the largest $$w$$ such that $$H[i,j'] \ge h$$ for all $$j' \in [j,j+w-1]$$.

You can compute each element of $$H$$ in $$O(1)$$ time using dynamic programming (fill them in from the bottom up). Also, once you have $$H$$, you can compute each element of $$W$$ in $$O(1)$$ time using dynamic programming (fill them in the right to left).

Finally, once you have $$W$$, it is trivial to find the largest rectangle, by scanning all of its elements.

In other words, if you have a $$n\times n$$ bitmap, you can fill in $$H$$ in $$O(n^2)$$ time and fill in $$W$$ in $$O(n^3)$$ time, and then you can find the largest rectangle in $$O(n^3)$$ time. So, this gives an $$O(n^3)$$ time algorithm. That is an improvement over Pål GD's algorithm, which takes $$O(n^4)$$ time.

If the bitmap is rectangular rather than square, you can use the same algorithm. I suggest you transpose it first if it is taller than it is wide; that way you will have fewer values of $$h$$ to iterate over. In this way, if you have a $$m\times n$$ bitmap, the running time will be $$O(\min(mn^2,m^2n))$$.