Recursive method got accepted. Why?


  • 2
    G

    I solved this problem using a recursive method and got accepted. Then I noticed the requirement of constant space. How come a recursive method needs constant space? A bug?


  • 5
    M

    Space complexity and recursive vs iterative are things the programmer needs to do. There is no test by the site for them, and so unless you massively overshoot, the incorrect sizes will still pass.

    Recursive solutions, unless trivial, will take greater than constant space, since the call stack needs room to exist. The common divide and conquer algorithms take O(logn) space. Therefore, for the constant space problems, you typically need to solve it iteratively.

    With this problem, the way to solve it is an O(n) iterative algorithm, using O(1) space. However, like I said earlier, any O(n) time algorithm will likely be accepted.

    EDIT: As tripshock said, O(nlogn) is the actual solution. I got confused between this problem's name and Sort Colors. This problem actually is O(nlogn) using an iterative solution to keep constant space, and any O(nlogn) time solution will likely pass, regardless of space used.


  • 0
    T

    Did you mean O(nlogn)?


  • 0
    M

    Yes, sorry, I was thinking of another one with a similar name.


Log in to reply
 

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