Longest stretch of prices within a band

Question

You want the longest calm stretch of the tape. Given prices and a band width B, find the length of the longest contiguous run in which the maximum price minus the minimum price never exceeds B.

prices = [1, 3, 2, 4, 5], B = 2
-> 3            # the run [1, 3, 2] has range 2

Return the length of the longest run with range at most B. Aim for $O(n)$ .

Accepted Answer

Grow a variable window on the right while tracking its running max and min with two monotonic deques (a decreasing deque for the max, an increasing one for the min). After each extension, if the current range exceeds B, advance the left edge, evicting any deque front that falls behind it, until the range is legal again. Record the best window length seen. Tracing [1, 3, 2, 4, 5] with B = 2: the window [1, 3, 2] has range 2 (length 3); extending to 4 forces the left edge to advance, and no later window beats 3. Time O(n), each index enters and leaves both deques once, and space O(n). The subtl…

Longest stretch of prices within a band

Your answer

More Coding questions