Constant space memory requirements clarification


  • 0
    M

    Can we use a data structure that links to the node objects without duplicating them? Constant space seems to imply we have to sort in place.For example is it OK to create a tree with links to the nodes or an array with node references?


  • 0
    S

    I think duplicating node objects is kind of using extra memory. Especially you duplicate all nodes to construct data struct.


  • 0
    M

    You are not duplicating a node object if you simple store a reference. You are duplicating a reference.

    This is what I am asking in the question above. Obviously duplicating all nodes would violate the requirement. To do the sort you will need to be able to at least keep 1 temp variable. I am just asking if using a temporary data structure to store references temporarily, like in merge sort, is a violation of the requirement.


  • 2
    W

    I don't think it meets the requirement. The size of the tree is O(n), and O(n) is not constant when n grows, even though the space used by the tree can be far less than that of the original objects.


  • 0
    S

    I think what I mean is same as wolf5x. Even the reference is still grow with N.


  • 0
    M

    thanks for the feeback :)


Log in to reply
 

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