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 really enjoyed this problem. I found it quite challenging.
For small arrays, it has a trivial solution: just start from d and loop left and right until you find a price that is out of range. That algorithm is O(n) and times out in 9, 10 and 11. With that algorithm, the worst case scenario is when you have a very large array and you cover it from beginning to end every query.
To solve it, you need to find a way to perform each query in O( log n). To do that, you need to preprocess the list and create a data structure that supports such queries. If you do the right algorithm, then the query that covers the entire list is the best case scenario and can be solved in O(1)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Stock Prediction
You are viewing a single comment's thread. Return to all comments →
I really enjoyed this problem. I found it quite challenging.
For small arrays, it has a trivial solution: just start from d and loop left and right until you find a price that is out of range. That algorithm is O(n) and times out in 9, 10 and 11. With that algorithm, the worst case scenario is when you have a very large array and you cover it from beginning to end every query.
To solve it, you need to find a way to perform each query in O( log n). To do that, you need to preprocess the list and create a data structure that supports such queries. If you do the right algorithm, then the query that covers the entire list is the best case scenario and can be solved in O(1)