Leetcode 84: Largest rectangle in histogram

January 18, 2018

Introduction

It is the hard level algorithm and it can be solved used stack to achieve the optimal time complexity O(N) where N is the array's length. The algorithm is called largest rectangle in histogram.

On January 17, 2018, I had a mock interview and I was asked to work on the algorithm. I went through the brute force solution first, but I did not come out the optimal solution to lower the time complexity to O(N).

One more practice 

What I like to do is to study one blog I like in June 2015, and then rewrite the notes and also write the C# code as well. It is very easy to look up past practice, here is my blog to document the practice in June 2015. At that time, I was shy and did not write down my thinking process to learn to solve the problem.

Right now, I think that it is very important to write down thinking process and also the idea to break through the hurdles in the problem solving. I think that it is more important to build up some new habit to learn to solve a problem. Write down the constraints, write down the problem, difficult issues, concerns, and then ideas to solve the problem, or ideas to solve partial solution. 

First, I rewrote the note to make it more readable, and then saved a gist. Here is the gist. 

Analysis of the algorithm

Most of important is to write down the analysis, and that is something lasting longer than coding itself. Specially if I draw something to highlight the main design ideas and it will be extremely helpful to bring back the memory.

This time I drew one to help myself learn the design using stack, check upward and downward.

The main idea is very simple to explain in Chinese, let us take a look at notes in Chinese first, and then I quickly explain them in English.

Going upward

When the graph is going upward, in detail, current index is i, next step is i + 1, and height[i] < height[i + 1], there is no need to calculate the area. Since it is getting bigger value when i moves to next value.

Going downward

When the graph is going downward, in detail, current index is i, next step is i + 1, and height[i] > height[i + 1]. it is time to calculate the current rectangle's area.

Get help from a stack 

At the current index i, only right end's index is known, how to get the left end's index? So in order to iterate the array, a stack is need to maintain the backtracking history.

How to design a stack?

In this stack the right end's index is saved to the stack, but when is time to push into stack? Every time there is element in the array which is bigger than the top of the stack, push the index to the stack. Otherwise it is time to calculate the current rectangle's area and compare to the largest area.

Every algorithm will become one of your valuable weapons 

until you teach some one and show him/ her how it work.