adamcrussell

Largest Rectangle Histogram

Perl Weekly Challenge 075 asks us to find the maximum rectangle of a histogram as follows

You are given an array of positive numbers @A.
Write a script to find the largest rectangle histogram created by the given array.

Looking at the above histogram, the largest rectangle (4 x 3) is formed by columns (4, 5, 3 and 7).
Output: 12

This is a fun sort of problem that seems to be right at home in a programming challenge and seldom seen in more typical scenarios!

My approach to this is as follows:

  1. Compare each value V in the histogram against the others. 
  2. If V is greater than the one being compared against set rectangle size to 0.
  3. If V is less than or equal to the one being compared against increase rectangle by V.
  4. We determine the maximum rectangle size by comparing all the computed rectangle sizes as they are generated.

In code:

ch-2.pl
ch-2.pl

Sample Run

sample output from ch-2.pl
sample output from ch-2.pl


Comments for this post were locked by the author