We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
No, the thing is that this problem is "naturally" solved using stack without recursion, in iterative manner: you go linearly over the h[i] and push candidates on the stack and pop them off depending on rise or decrease of height. You can solve it with recursion, but then as it has been said you replace that stack by the recursion stack. (Yet it's not natural, I wonder how you do it correctly, because you may have to "glue together"rectangles of same height from the left and the right, and it might happen than a "left part" and "right part" of a smaller rectangle would have been dropped in the sub-problems but together they give more than the the "larger rectangles" individually...)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Largest Rectangle
You are viewing a single comment's thread. Return to all comments →
No, the thing is that this problem is "naturally" solved using stack without recursion, in iterative manner: you go linearly over the h[i] and push candidates on the stack and pop them off depending on rise or decrease of height. You can solve it with recursion, but then as it has been said you replace that stack by the recursion stack. (Yet it's not natural, I wonder how you do it correctly, because you may have to "glue together"rectangles of same height from the left and the right, and it might happen than a "left part" and "right part" of a smaller rectangle would have been dropped in the sub-problems but together they give more than the the "larger rectangles" individually...)