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/
Why can't you solve this using sliding window approach?
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]
“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
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?
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
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.
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.
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.
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.
Tech Industry
Yesterday
1201
Do you really think Amazon is that bad
Health & Wellness
7h
731
How can I find success dating in NYC
Tech Industry
Yesterday
2298
I paid 250 for a Google Referral and got Scammed
Layoffs
1h
242
If new employer revokes offer when you already resigned at current company
India
Yesterday
1826
Slavery has REVERSED! the US is the slave!!! Check out this dude who pays a personal trainer in India
Yes. Applying the stack this way is a common pattern
There are other variations (direction change, when to push and pop) that are useful in other scenarios
Thanks. Does this concept have a name? Last time I found some obscure approach, it was actually something with its own Wikipedia article.