The longest steady stretch
Find the longest stretch of an array whose biggest and smallest values differ by at most a limit, with two deques tracking the maximum and the minimum of the window. About 20 minutes.
Two deques for one window
You grow a window by moving its right edge. To know how spread out the window is, you need its maximum and its minimum. Last step showed a deque that always gives the maximum. A second deque, mirrored, always gives the minimum.
Each time a value is added, update both deques: the max deque drops smaller values from the back, and the min deque drops bigger values from the back.
mx = deque([4, 2]) # 4 is the biggest mn = deque([1, 3]) # 1 is the smallest
The window 8 has spread 0. Length 1.
Shrink while too spread
If the front of the max deque minus the front of the min deque is more than the limit, the window is too spread out. Move the left edge one step to the right. Any deque front that is now left of the window is removed.
Repeat until the window is steady again, then measure its length. The window always contains at least the newest value, so the length is at least 1.
spread = nums[mx[0]] - nums[mn[0]]
The window is too spread out. What do you move?
- AThe left edge, to the right
- BThe right edge, to the left
- CStart again from the right edge
Show the answer
The left edge, to the right. Removing the oldest value is the way to reduce the spread, and a wider window would only be worse.
Longest subarray within a limit
You get a list nums and a number limit. Return the length of the longest run of consecutive values in which any two values differ by at most limit.
nums = [10, 1, 2, 4, 7, 2], limit = 5 → 4
1 ≤ length of nums ≤ 100,000 · 1 ≤ nums[i] ≤ 1,000,000,000 · 0 ≤ limit ≤ 1,000,000,000