# The largest rectangular problem

### 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:

##### 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`

Latest Source Code:
Github: LargestRectangle.java

Output:

```Largest Rectangle Area: 12
Largest Rectangle Area: 8
```
Author: