Longest window where prices stay within a band

Question

Find the longest contiguous window of prices whose range (max minus min inside the window) is at most a given limit, a stylized "how long did price stay in a tight band" query.

prices = [1, 5, 3, 4, 8], limit = 3
-> 3        # the window [5, 3, 4] has range 5 - 3 = 2

Return the length of the longest window with (max - min) <= limit, in O(n) time.

Accepted Answer

Slide a window with two monotonic deques: one keeping the current window's maximum at its front (decreasing), one keeping the minimum at its front (increasing). When adding a new price would make the range exceed the limit, advance the left edge and drop any deque front that falls outside the window. The window is always valid after the shrink, so record its length. Tracing [1, 5, 3, 4, 8], limit 3: the window grows to [5, 3, 4] (range 2) for length 3; adding 8 forces the left edge past the small values, dropping back to length 1. Time O(n) (each index enters and leaves each deque once), spac…

Longest window where prices stay within a band

Your answer

More Coding questions