We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
I ended up using a TreeMap. Since there can only be 400K inflection points max, it seemed wasteful to create an array of 10M values and then traverse the 10M values to compute a result. So this results in a time of O(M log M). As others have mentioned, the additional constant time is much higher than long[], so it's hard to estimate the actual performance difference. This would really win if M was small (and N large), and is time/space independent of N. (The code reads and discards N.)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Array Manipulation
You are viewing a single comment's thread. Return to all comments →
I ended up using a TreeMap. Since there can only be 400K inflection points max, it seemed wasteful to create an array of 10M values and then traverse the 10M values to compute a result. So this results in a time of O(M log M). As others have mentioned, the additional constant time is much higher than
long[], so it's hard to estimate the actual performance difference. This would really win if M was small (and N large), and is time/space independent of N. (The code reads and discards N.)