Company: Visa Iitp
Difficulty: hard
Largest Rectangle in Histogram A histogram is drawn from an array heights of n non-negative integers. Bar i stands on the interval from x = i to x = i + 1 , so every bar is exactly 1 unit wide , and bar i rises to height heights[i] . Find the axis-aligned rectangle of the largest possible area that fits entirely inside the shaded region of the histogram, and report that area. Such a rectangle always spans a contiguous block of bars l, l + 1, ..., r and its height cannot exceed the shortest bar in that block, so its area is (r - l + 1) * min(heights[l], heights[l + 1], ..., heights[r]) Report the largest value this expression takes over all choices of l <= r . Input Format A single line containing the array heights written as a bracketed, comma-separated list, for example [2,1,5,6,2,3] . Output Format Print a single integer — the area of the largest rectangle in the histogram. Constraints 1 <= heights.length <= 10^5 0 <= heights[i] <= 10^4 The answer is at most 10^5 10^4