DEV Community

Abhishek Chaudhary
Abhishek Chaudhary

Posted on

Largest Rectangle in Histogram

Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.

Example 1:

Input: heights = [2,1,5,6,2,3]
Output: 10
Explanation: The above is a histogram where width of each bar is 1.
The largest rectangle is shown in the red area, which has an area = 10 units.

Example 2:

Input: heights = [2,4]
Output: 4

Constraints:

  • 1 <= heights.length <= 105
  • 0 <= heights[i] <= 104

SOLUTION:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        next_lowest = [n for i in range(n)]
        prev_lowest = [-1 for i in range(n)]
        maxArea = 0
        inc_stack = []
        for i in range(n):
            while len(inc_stack) > 0 and heights[i] < heights[inc_stack[-1]]:
                curr = inc_stack.pop()
                next_lowest[curr] = i
            if len(inc_stack) > 0:
                prev_lowest[i] = inc_stack[-1]
            inc_stack.append(i)
        for i in range(n):
            currArea = (next_lowest[i] - prev_lowest[i] - 1) * heights[i]
            maxArea = max(maxArea, currArea)
        return maxArea

# class Solution:
#     def largestRectangleArea(self, heights: List[int]) -> int:
#         n = len(heights)
#         maxArea = 0
#         for i in range(n):
#             curr = heights[i]
#             left = i
#             right = i
#             while left >= 0 and heights[left] >= curr:
#                 left -= 1
#             left += 1
#             while right < n and heights[right] >= curr:
#                 right += 1
#             right -= 1
#             maxArea = max(maxArea, curr * (right - left + 1))
#         return maxArea

# class Solution:
#     def makeSeg(self, arr, i, j):
#         if (i, j) in self.seg:
#             return self.seg[(i, j)]
#         if i == j:
#             self.seg[(i, j)] = arr[i]
#             return arr[i]
#         mid = (i + j) // 2
#         curr = min(self.makeSeg(arr, i, mid), self.makeSeg(arr, mid + 1, j))
#         self.seg[(i, j)] = curr
#         return curr

#     def getMin(self, arr, i, j, ni, nj):
#         if ni >= i and nj <= j:
#             return self.seg[(ni, nj)]
#         if (ni < i and nj < i) or (ni > j and nj > j):
#             return float('inf')
#         mid = (ni + nj) // 2
#         return min(self.getMin(arr, i, j, ni, mid), self.getMin(arr, i, j, mid + 1, nj))

#     def largestRectangleArea(self, heights: List[int]) -> int:
#         self.seg = {}
#         n = len(heights)
#         if n == 1:
#             return heights[0]
#         self.makeSeg(heights, 0, n - 1)
#         mrec = float('-inf')
#         for i in range(n):
#             for j in range(i, n):
#                 mrec = max(mrec, (j - i + 1) * self.getMin(heights, i, j, 0, n - 1))
#         return mrec

# class Solution:
#     def largestRectangleArea(self, heights: List[int]) -> int:
#         n = len(heights)
#         areas = []
#         maxArea = float('-inf')
#         areas.append((0, heights[0]))
#         for i in range(1, n):
#             if heights[i] < areas[-1][1]:
#                 maxArea = max(maxArea, (i - areas[-1][0]) * areas[-1][1])
#                 areas.pop()
#             areas.append((i, heights[i]))
#         return maxArea
Enter fullscreen mode Exit fullscreen mode

Top comments (0)