# Largest Rectangle in a Histogram

Given a histogram/bar graph, what is the largest rectangle (area) within?

This can be solved in using a simple stack algorithm.

The gist:
– Scan from left to right.
– Add to the stack when height is going up.
– Otherwise, this marks the end of a (previous) taller rectangle, which is checked for area.

References:
geeksforgeeks.com
Wikipedia

My implementation is in git and below:

# Rectangle Intersections on a Large Scale

I‘ve put together the following C++ code to detect rectangle intersections in time ,

Additionally, I amended to include all touching (edge-to-edge, corner-to-corner), with no change in running time.

The code is in git and below:

# Eat All the Brownies

This post is in reference to SPOJ 17626. Eat all the brownies CUTCAKE.

The question is: to divide a plane into X pieces, how many lines (cuts) are needed? Magically, the answer is found on page 499 of Knuth’s Concrete Mathematics 2nd Ed. (or p485 in this PDF), and is as follows:

N.B. is the binomial coefficient function.

So this solves for regions given the number of cuts. But in this problem we’re to solve it the other way around; this is done via binary search.

My solution is in git and here: