Recursive vs. Iterative


  • 0
    D

    I just used two ways to solve this problem, recursive and iterative solution. And both of the two solutions pass the OJ and they cost almost the same time, even the recursive one better.

    So it is not strict with the memory limit, right?


  • 0

    The judge is purposely set to allow a variety of solutions to get accepted. This is so that a reader could explore multiple solutions and experiment with them. If you want the ultimate challenge, try coding a quick sort which is able to pass the judge.


  • 0
    E

    I think sandbox may not be easy to judge on stack usage.. By recursive if you use system stack, it should be fine. (I'm just guessing as I'm not 1337 himself)


  • 0

    No, the judge is able to limit the stack space if I wanted to. For example, if you use the recursive DFS approach for the problem Surrounded Regions, it will result in a Runtime Error.

    I relaxed the stack space requirement for this problem so a user is able to experiment with a variety of algorithmic techniques.


  • 0
    E

    Don't know exactly which sandbox do you use, but in general it's not easy. I understand there're variety of ways of doing so, but none of them should throw "runtime error". "runtime error" may give me a hint that the sandbox tries to set the intial stack size as config and doesn't handle stack overflow exception which result in a AV. Is this the approach? :)
    And my previous answer to that gentleman is tentatively to answer his "memory limit" confuse, which is not seemed resolved in current sandbox as talked above.


  • 0
    R

    It uses the processor stack (or your stack in case of iterative solution) to store temporary variables but what it stores at a time is the path of the tree, a binary tree that is traversed depth-first.

    So the maximum number of nodes you have in memory at a time (a part of the original list) is log(n).

    This means that if you have one million of elements in your list you are going to use only 20*k extra nodes!
    K represents the number of nodes you save per iteration into local variables or the stack.

    In case of a bililon of element the reference value is 30k.

    SUPER CONVENIENT SOLUTION!


  • 0
    R

    The stack is not an issue here because the number of folded recursive calls is log(n).
    So for one billion elements you have only 30 folded calls at once.
    Nothing comparing to N!


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.