0084-largest-rectangle-in-histogram

Try it on leetcode

Description

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(Python)

class Solution:
    """
    for calculating a rectangle we need both width and height 
    the width of the rectangle will be the difference of index positions
    and height will be the corresponding values
    
    Constraints:
        * 1 <= heights.length <= 10^5
        * 0 <= heights[i] <= 10^4
    
    1.Bruteforce:
        *we can start from every possible recatngles that can be formed from the given 
         array
        *with respect to width we can make upto n^2 possible 
        *while considering the height choose the rectangle with less height
      Implementation:
        maxRectangleArea
        for i in n:
            for j in n:
                maxRectangleArea = max(maxRectangleArea, (j-i+1) * min(arr[i],arr[j]) )
      Analysis:
        Time Complexity: O(n^2)
        Space Complexity: O(1)
        
    2. presum:
       Idea:
            bruteforcs can be written as
            
            for each index:
                maxarea = max(height[index]*(leftindex[i] - rightindex[i]))
            with precached the leftsmallest index and right smallest index
            we can optmize the bruteforce method
            
            for leftsmallest index move until we hit the smallest height
            similary for right smallest index repeat the process
       
       Analysis:
        Time Complexity: O(n)
        Space Complexity: O(n)    
    
    3. stacks:
        in presum technique we only cache the information of bars in increaing heights
        
        instead of using two separate arrays to store it's value
        
        we can use a stack of bars we identified so far with only bars greater than current bar
      Analysis:
        Time Complexity: O(n)
        Space Complexity: O(n)    
    
    """
    def largestRectangleArea(self, heights: List[int]) -> int:
        return self.stack(heights)
        
    def bruteforce(self, heights: List[int]) -> int:
        n = len(heights)
        maxRec = float('-INF')
        for i in range(n):
            curHeight = heights[i]
            for j in range(i,n):
                curHeight = min(curHeight,heights[j])
                maxRec = max(maxRec,abs(j-i+1)*curHeight)

        return maxRec
    
    def presum(self, heights: List[int]) -> int:
        n = len(heights)
        
        left = [0]*n
        right = [0]*n
        
        left[0] = -1
        right[n-1] = n
        
        for i in range(1,n):
            curr = i-1
            while curr >= 0 and heights[i] <= heights[curr]:
                curr = left[curr]
            left[i] = curr
            
        for i in range(n-2,-1,-1):
            curr = i +1
            while curr <= n -1 and heights[i] <= heights[curr]:
                curr = right[curr]
            right[i] = curr
            
        maxRec = float('-INF')
        for i in range(n):
            maxRec = max(maxRec,heights[i]*(right[i]-left[i]-1))
        return maxRec
            
    def stack(self, heights: List[int]) -> int:
        heights.append(0)
        stack = []
        maxRec =  0
        n = len(heights)
        for i in range(n):
            height = heights[i]
            while stack and heights[stack[-1]] >= height:
                H = heights[stack.pop()]
                W = i if not stack else i-stack[-1]-1
                maxRec = max(maxRec, H*W)
            stack.append(i)
        return maxRec