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.
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)"
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Join us
Create a HackerRank account
Be part of a 26 million-strong community of developers
Please signup or login in order to view this challenge
Largest Rectangle
You are viewing a single comment's thread. Return to all comments →
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)"