Solution to upsilon2012 (Cartesian-Sequence) by codility

17 Feb

Question: https://codility.com/demo/take-sample-test/cartesian_sequence

Question Name: upsilon2012 or CartesianSequence

A straightforward solution would be construct the Cartesian tree, compute its height, and return the height plus one. But any left sub-tree would never be accessed or changed after its construction. And so is their height information. In other words, the height information only needs possible update, when the nodes are on the path from the last node to the root. To improve the performance, we could compute the height while constructing the tree.

Leave a Reply

Your email address will not be published. Required fields are marked *