DIY: Largest Rectangle in Histogram

Solve the interview question "Largest Rectangle in Histogram" in this lesson.

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}

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.