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
it does appear to be O(n^2) on 1st glance, that's wat i thought too when i first saw it. the naive way really takes O(n^2), the stack is there to guarantee O(n)
but every number in H is pushed onto the stack exactly once, and is removed at most once, so the inner while loop add up to a maximum of 2n operations for all iterations of i
i learned this algo from copilot, u should ask it, it'll explain to u in detail why its O(n) and not O(n^2). just type "c++ explain the previous smaller element algorithm and why its O(n)"
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
it does appear to be O(n^2) on 1st glance, that's wat i thought too when i first saw it. the naive way really takes O(n^2), the stack is there to guarantee O(n)
but every number in H is pushed onto the stack exactly once, and is removed at most once, so the inner while loop add up to a maximum of 2n operations for all iterations of i
i learned this algo from copilot, u should ask it, it'll explain to u in detail why its O(n) and not O(n^2). just type "c++ explain the previous smaller element algorithm and why its O(n)"