Tech IndustryFeb 12, 2019
Pingercreate💻

Largest Rectangle in Histogram

If I got this problem in an interview without seeing it before, I am not sure how I would use general approaches to arrive at the stack-based solution for this problem. Even if I knew to iterate through all of the bars and find the largest rectangle using bar[i] as the lowest bar in that rectangle, it's not clear how I would know to use a stack in the way that it is used. In contrast, I have worked on other problems including Trapping Rainwater I & II where the solution seemed intuitive given enough time and familiarity with data structures and recursion/subproblems. Am I missing an easy way to think about this problem? Is the use of a stack in this way useful for solving other LeetCode problems? https://leetcode.com/problems/largest-rectangle-in-histogram/description/

Largest Rectangle in Histogram - LeetCode
Largest Rectangle in Histogram - LeetCode
Leetcode
Add a comment
Amazon zgzgizi Feb 12, 2019

Yes. Applying the stack this way is a common pattern

Amazon zgzgizi Feb 12, 2019

There are other variations (direction change, when to push and pop) that are useful in other scenarios

Pinger create💻 OP Feb 12, 2019

Thanks. Does this concept have a name? Last time I found some obscure approach, it was actually something with its own Wikipedia article.

New
Latka Feb 12, 2019

Why can't you solve this using sliding window approach?

Pinger create💻 OP Feb 12, 2019

It just doesn't work out. If your window is defined by pointers 'leader' and 'follower', then when do you advance the follower? In the below example, the largest rectangle is 1x7. You'd need the window to cover the whole array to consider that. But then how do you consider the 2x3 rectangle if leader is already at the end? [1,1,1,3,3,1,1]

Microsoft Szcz77 Feb 12, 2019

“In contrast, I have worked on other problems including Trapping Rainwater I & II where the solution seemed intuitive given enough time and familiarity with data structures and recursion/subproblems.” This is the problem right here in technical interviews and it is the answer to your question. You feel trapping rainwater 2 is a good challenge which can be solved with intuition and good data structure knowledge. I bet there are enough FNG people here who will ack that it is an unreasonable question to ask in an interview

Pinger create💻 OP Feb 12, 2019

Do you think trapping rainwater II is harder than largest rectangle in histogram, or are they both too much for an interview in your opinion?

Microsoft Szcz77 Feb 12, 2019

I think both are trick questions and doesn’t seem to be good interview question. Also I have interviewed at fang and unicorn, I was never asked these kind of trick questions

Microsoft 👋 hello Feb 12, 2019

Dont feel bad OP. I really dont think this type of question is suitable for interviews. Maybe the interviewer wanted to feel superior and ask this question... interview is all about luck.

New
Latka Feb 12, 2019

I feel like interviewers now expect you to KNOW all solutions leetcode problems. It's not about original solutions, it's about memorizing "ideomatic" solutions.

Facebook 0a00h Feb 16, 2019

No, good candidates will come up to a correct solution on this problem without seeing one before. I haven’t ever seen this and came up with one in minutes.

Facebook 0a00h Feb 16, 2019

For each segment, you need to count surrounding segments bigger than itself. It becomes two pass (starting at 0 and n-1 index) largest increasing subarray, with a twist that you need to update how many elements followed (thus the stack). Then it’s just a trivial math. Problem is hard (for an interview), it took me solid 2 minutes to come up with this. It usually takes me seconds to solve Google/FB interview problems in real life. I don’t think it’s a good problem, because coding is a joke and it doesn’t get enough signal.