Longest window with range under a limit

Question

Given a price series and a limit, find the length of the longest contiguous window in which the difference between the highest and lowest price is at most limit.

prices = [8, 2, 4, 7], limit = 4
-> 2           # windows [2,4] and [4,7] each have range <= 4

Return the maximum window length in $O(n)$ .

Accepted Answer

Slide a window with two pointers. Keep a decreasing deque for the running maximum and an increasing deque for the running minimum, both holding indices. After extending the right end, if max - min exceeds the limit, advance the left pointer, discarding any deque front that falls out of the window, until the window is valid again. Track the best length seen. Tracing [8, 2, 4, 7], limit = 4: the window [8,2] has range 6, too wide, so the left pointer moves past the 8. The valid windows top out at length 2 ([2,4] and later [4,7]), so the answer is 2. Both pointers only move forward and each inde…

Longest window with range under a limit

Your answer

More Coding questions