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?
I think duplicating node objects is kind of using extra memory. Especially you duplicate all nodes to construct data struct.
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.
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.