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.
For a sufficiently random array the sliding window should be more than adequate (it was for me). You would only expect to compute a new MAX once every d shifts on average.
The worst case would be if the array was sorted in descending order. You would have to recompute the new MAX after every shift which would run in O(d*n) time. The average running time would be between O(n) and O(d*n).
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Queries with Fixed Length
You are viewing a single comment's thread. Return to all comments →
For a sufficiently random array the sliding window should be more than adequate (it was for me). You would only expect to compute a new MAX once every d shifts on average.
The worst case would be if the array was sorted in descending order. You would have to recompute the new MAX after every shift which would run in O(d*n) time. The average running time would be between O(n) and O(d*n).