Easy to understand python solution, the first-go-to algorithm


  • 0
    N

    I think this algorithm works fine with a particular kind of data set i.e., but if the data is sorted, then it takes the worst time, which is why this particular solution fails for Testcase #95 and #96 where the dataset is huge and sorted. Run time is pretty good for other tests. Please reply if you know exactly what the average run time is in Big-O notation
    But it's a simple idea with no stack involved

    1. find the bar with minimum height and split the histogram into parts at the minimum (excluding the minimum height bar)
    2. On each part, recursively run LargestRectangleArea
    3. Get the maximum value of each part and compare it with the height of the minimum bar times the length of that part of the histogram. i.e. max(LargestRectangleArea(on each sub part), minHeight*Length(histogram part))

    On a side note: Anyone has a better way of splitting the given histogram based on minInd, please feel free to post it. Also please let me know if you could get this algorithm to run with the test cases 95 and 96

     def largestRectangleArea(self, heights):
        
        minInd = [i for i in range(len(heights)) if heights[i] == min(heights)]
        if len(heights) == 1:
            return heights[0]
        elif len(heights) == 0:
            return 0
        elif len(minInd) == len(heights):
            return min(heights)*len(heights)
        
        splitParts = []
        sol = []
        for i in range(len(heights)):
            if i in minInd:
                if len(sol) != 0:
                    splitParts.append(sol)
                    sol =[]
            else:
                sol.append(heights[i])
        if len(sol)!=0:
            splitParts.append(sol)
              
        d = map(self.largestRectangleArea, splitParts)
        minVal = min(heights)
        maxRectangle = max(minVal*len(heights), max(d))
        
        return maxRectangle

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.