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

Comments

Post a Comment

Popular posts from this blog

Encrypt and Decrypt Strings

You are given a character array keys containing unique characters and a string array values containing strings of length 2. You are also given another string array dictionary that contains all permitted original strings after decryption. You should implement a data structure that can encrypt or decrypt a 0-indexed string. A string is encrypted with the following process: For each character c in the string, we find the index i satisfying keys[i] == c in keys . Replace c with values[i] in the string. Note that in case a character of the string is not present in keys , the encryption process cannot be carried out, and an empty string "" is returned. A string is decrypted with the following process: For each substring s of length 2 occurring at an even index in the string, we find an i such that values[i] == s . If there are multiple valid i , we choose any one of them. This means a string could have multiple possible strings it can decrypt t...
Read more

Degree of an Array

Given a non-empty array of non-negative integers nums , the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums , that has the same degree as nums .   Example 1: Input: nums = [1,2,2,3,1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. Of the subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2. Example 2: Input: nums = [1,2,2,3,1,4,2] Output: 6 Explanation: The degree is 3 because the element 2 is repeated 3 times. So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.   Constraints: nums.length will be between 1 and 50,000. nums[i] will be an integer between 0 and 49,999. SOLUTION: from collections import defaultdict class Solution : def findShortestSubArr...
Read more

Minimum Sum of Four Digit Number After Splitting Digits

You are given a positive integer num consisting of exactly four digits. Split num into two new integers new1 and new2 by using the digits found in num . Leading zeros are allowed in new1 and new2 , and all the digits found in num must be used. For example, given num = 2932 , you have the following digits: two 2 's, one 9 and one 3 . Some of the possible pairs [new1, new2] are [22, 93] , [23, 92] , [223, 9] and [2, 329] . Return the minimum possible sum of new1 and new2 .   Example 1: Input: num = 2932 Output: 52 Explanation: Some possible pairs [new1, new2] are [29, 23], [223, 9], etc. The minimum sum can be obtained by the pair [29, 23]: 29 + 23 = 52. Example 2: Input: num = 4009 Output: 13 Explanation: Some possible pairs [new1, new2] are [0, 49], [490, 0], etc. The minimum sum can be obtained by the pair [4, 9]: 4 + 9 = 13.   Constraints: 1000 <= num <= 9999 SOLUTION: class Solution : def minimumSum ( self,...
Read more