The largest rectangular problem

Find the largest rectangular area possible in a given histogram where the largest rectangle can be made of a number of contiguous bars. For simplicity, assume that all bars have same width and the width is 1 unit.

Solution:

This is one particular manifestation of the all nearest smaller values (ANSV) (AllNearestSmallerValue) problem. For each bar in the histogram, we want to find the nearest bar on the left which is shorter, and the nearest bar on the right which is shorter—because they determine how far left and how far right we can extend a rectangle with the current bar’s full height. Use the O(n) stack-based algorithm for ANSV, and the problem becomes trivial.

Algorithm:

• Take 2 arrays (one-one for left and right width of a bar ) and one stack to hold index to calculate ANSV.
• Now calculate left width
  • Push 0 in add stack
  • Set left[0] = 0
  • Iterate given histogram array from index 1 to n
    • If histogram[stack.top] >= histogram[i] && stack is not empty then
      • stack.pop
    • If stack is empty then,
      • left[i] = i + 1
    • Else
      • left[i] = i - stack.top()
    • stack.push(i)
• Populate right[i] same way as we did for left area but from nth to 0th index of histogram
• Now calculate Area
  • Set MaxArea = 0
  • Iterate given histogram array from index 0 to n
    • width = left[i] + right[i] - 1
    • Set area = width * histogram[i]
    • If MaxArea < area then
      • Set MaxArea = area
• Return MaxArea

Largest Rectangular

Latest Source Code:
Github: LargestRectangle.java

Output:

Largest Rectangle Area: 12
Largest Rectangle Area: 8