Leetcode - Largest Rectangle in Histogram (Python)

December 2020 Leetcode Challenge
Leetcode - Largest Rectangle in Histogram # 84

[computefreely]

The bruteforce approach should be n^3 instead of n^2. The min you are calling in heights[i:j+1] will take another n and it is not constant time.

[manoj]

I had seen few videos on this ranging from 20mins to 30mins. This is best of all for me and surprisingly under 10mins.

[fishoil]

In case, anyone is wondering why W = i - stack[-1] - 1 (with minus 1), you can interpret in this way. Index i is the width we came across so far (this width does not include the element that we are iterating now). What is on the stack is the index, if we plus 1, it becomes the width from beginning to that index, let's say our stack has index 0, width will be 1. So, W = i - (stack[-1] + 1) --> i - stack[-1] - 1

[elegentt]

I was stuck at constructing DP, never thought about the sliding window technique. Thanks for bringing it up!

[mouryakillamsetti]

What is the time complexity of the code executed 2 nd time?

[sumansigdel]

I solved it using Nearest smaller to the left and nearest smaller to the right.

[anishbangotra]

Hi, how can I connect to you, I want to learn more about solving problems with python from you