What does constant extra space mean?


  • 0
    B

    Hello, I've solve the problem using hashmap (level of depth, TreeLinkNode). It got accepted, but i am not sure what constant extra space meant. I can also solve the problem using ArrayList instead of hashmap (a little less memory) using the same concept, keep the tail of each level and update to whatever comes next. If the solution is a tree with 5 levels, I would have 5 copies of tail for each level. Would this count as constant extra space?

    I would be happy to share my solution, if anyone want to see.


  • 1
    S

    'Constant extra space' usually means the solution containing several variables, the amount of them is not depend on what the input is.

    You mentioned, you are using 'hashmap'. I would say this solution probably is not a constant extra space one.

    Here is a flashstone's post, which presented how they make it O(1) space.


  • 1
    Y

    It means the space you need doesn't grow when you have more levels.

    If your tree with 5 levels needs 5 tails and with 1000 levels you need 1000 tails, that's not constant.

    Constant means that you only need 5, no matter if its 5 levels or 1000 levels.


Log in to reply
 

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