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.
What are your measurements of runtime and/or memory for recursive vs stack solution? The stack solution is one single loop, if height increases then you may have to do at most one push (not necessarily: only when there are two consecutive strict increases) and if height goes down you may have to do several pops, but not many: because height of stack = total # pushes - total # pops, so in the mean you do less than 1 push or 1 pop for each i. This is very fast. And you do not need any additional memory. While when you use recursion, and on each level of recursion you have list manipulation and return values are lists, this uses lots of memory. Since you have to access each element at least once, anyway, I don't think this can be faster, and will usually be slower.
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 →
What are your measurements of runtime and/or memory for recursive vs stack solution? The stack solution is one single loop, if height increases then you may have to do at most one push (not necessarily: only when there are two consecutive strict increases) and if height goes down you may have to do several pops, but not many: because height of stack = total # pushes - total # pops, so in the mean you do less than 1 push or 1 pop for each i. This is very fast. And you do not need any additional memory. While when you use recursion, and on each level of recursion you have list manipulation and return values are lists, this uses lots of memory. Since you have to access each element at least once, anyway, I don't think this can be faster, and will usually be slower.