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 the same width and the width is 1 unit.
For example, consider the following histogram with 7 bars of heights {6, 2, 5, 4, 5, 1, 6}. The largest possible rectangle possible is 12 (see the below figure, the max area rectangle is highlighted in red)
Approach:
- For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. We will find the index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and the index of first smaller bar on right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively.
- Multiply ‘x’ with “right_index-left_index-1” and store it in area
- Return max area
Below is the implementation of the above approach.
index.js
<script> function getMaxArea(arr, n) { var area = 0; for (var i = 0; i < n; i++) { var left_index; var right_index; for (var j = i; j >= 0; j--) { if (arr[j] < arr[i]) { left_index = j; break; } } left_index = j; for (var j = i; j < n; j++) { if (arr[j] < arr[i]) { right_index = j; break; } } right_index = j; area = Math.max(area, arr[i] * (right_index - left_index - 1)); } return area; } var array = [6, 2, 5, 4, 5, 1, 6]; document.write(getMaxArea(array, 5)); </script> |
Output:
12
Complexity: We are using linear search to find the minimum value, then the worst-case time complexity of this algorithm becomes O(n^2).
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
