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.
Thank you very much for your code! Two comments here:
1) your time of execution will depend on the input, If for each h, both next smaller and previous smaller elements are not far, it may be O(n). But in the opposite extreme case, e.g. when H is sorted, it will be O(n^2)
2) Still why stacks? Why not find next smaller and previous smaller for each element naively? (see e.g. solution by faisalalotibi98). It would be the same running time
Largest Rectangle
You are viewing a single comment's thread. Return to all comments →
Thank you very much for your code! Two comments here: 1) your time of execution will depend on the input, If for each h, both next smaller and previous smaller elements are not far, it may be O(n). But in the opposite extreme case, e.g. when H is sorted, it will be O(n^2) 2) Still why stacks? Why not find next smaller and previous smaller for each element naively? (see e.g. solution by faisalalotibi98). It would be the same running time