DIY: Largest Rectangle in Histogram

Problem statement

We are given an array of n non-negative integers representing the histogram’s bar height where the width of each bar is 1. You have to find the area of the largest rectangle in the histogram.

Input

The input will be an array of integers. The following is an example input:

heights = [2,1,5,6,2,3]