A window that needs its largest and smallest values
A window's sum, product or count can be corrected when a value leaves: subtract the value from the sum, divide it out of the product, take 1 off the count. A window's maximum cannot be corrected that way. Take the window [10, 1, 2], whose maximum is 10. When the 10 leaves, the new maximum is 2, and knowing the old maximum does not help us find it. We would have to look through everything that is still in the window. The next problem needs both the maximum and the minimum of a window whose two ends move:
You get an array nums and an integer limit. Return the length of the longest nonempty subarray in which every two elements differ by at most limit.
Constraints
-
len(nums) -
nums[i] -
limit
Sample 1 · Input
nums = [8,2,4,7], limit = 4
Output
2
Sample 2 · Input
nums = [10,1,2,4,7,2], limit = 5
Output
4
Sample 3 · Input
nums = [4,2,2,2,4,4,2,2], limit = 0
Output
3
No two values in a subarray are further apart than its largest and smallest values. So a subarray is valid exactly when its maximum minus its minimum is at most limit. In the second sample, [2, 4, 7, 2] has and is valid. Extended one position to the left, [1, 2, 4, 7, 2] has , which is over the limit of 5.
Extending a window can raise its maximum or lower its minimum but cannot do the reverse, so a window that is over the limit stays over it when extended. That is the property the growing and shrinking window needs, so the same loop works: right moves forward one position at a time, and left moves forward while the window is over the limit. The loop also needs the window's maximum and minimum at every step, and reading through the window to find them is too slow. A window can hold values, and there are steps:
That is 100 seconds at operations a second.
Keep only the values that can still be the maximum
We will keep the window's maximum in a deque of array indices, a queue that also lets us remove items from its back. Let's build it on the second sample, [10, 1, 2, 4, 7, 2], and add the minimum afterwards.
Some values in a window cannot be its maximum, now or later. Suppose the window holds 1, 2, 4 and the 7 arrives. The 1, the 2 and the 4 are smaller than the 7 and entered before it, so they will leave before it, because left only moves to the right. From now on, every window that contains one of them contains the 7 as well, and none of the three can be the maximum again. We can forget them.
So the deque holds only the indices that can still become the maximum, in the order they arrived. When a new index arrives, we remove indices from the back while their values are smaller than the new value, then add the new index at the back. A smaller value is removed as soon as a larger one arrives after it, so the values in the deque never increase from front to back. That is also why the removals can stop at the first value at least as large as the new one: every value in front of it is at least as large too.
This puts the window's maximum at the front. If a value in the window is not in the deque, it was removed when a larger value arrived after it, so it is not the maximum. The maximum is one of the values left in the deque, and the largest of those is at the front.
The front has to be removed once it is outside the window. The window starts at left, so the test is whether the front index is less than left. This is why the deque stores indices and not values: an index can be compared with left, and a value does not say where it sits in the array. The same deque keeps the maximum of a window of fixed length , with a different test: when the window ends at index i, the front is outside it once its index is i - k or less.
Definition
A monotonic queue is a deque of indices whose array values stay in sorted order from front to back. When the values never increase, the front is the window's maximum. When they never decrease, the front is its minimum.
Add a second deque for the minimum
The minimum needs the same structure with the comparison reversed. When the 2 at index 5 arrives, the 4 and the 7 before it are larger and will leave the window sooner, so neither can be the minimum again. The second deque removes from its back every index whose value is larger than the new value. Its values never decrease from front to back, and its front is the smallest value in the window.
right = 5. The arriving 2 removes the 4 and the 7 from the back of the min deque. The two fronts give .With both deques, the test in the shrinking loop is one subtraction: the value at the front of the max deque minus the value at the front of the min deque.
Run the scan on the second sample
Each step of the scan does three things in order. The arriving index updates both deques. The window shrinks while the two fronts differ by more than the limit. Then the length is recorded. Here is the second sample, with a limit of 5. The second column lists every value that leaves a deque during the step. A value leaves from the back when the arriving value removes it, and from the front when left moves past it:
| Value arriving | Leaves a deque | Max deque | Min deque | Window, length |
|---|---|---|---|---|
| 10 | nothing | 10 | 10 | [10], 1 |
| 1 | 10, from the back of the min deque; then 10, from the front of the max deque | 1 | 1 | [1], 1 |
| 2 | 1, from the back of the max deque | 2 | 1, 2 | [1, 2], 2 |
| 4 | 2, from the back of the max deque | 4 | 1, 2, 4 | [1, 2, 4], 3 |
| 7 | 4, from the back of the max deque; then 1, from the front of the min deque | 7 | 2, 4, 7 | [2, 4, 7], 3 |
| 2 | 7 and then 4, from the back of the min deque | 7, 2 | 2, 2 | [2, 4, 7, 2], 4 |
The window shrank twice. When the 1 arrived, the fronts were 10 and 1, which differ by 9, so left moved to index 1 and the 10 expired. When the 7 arrived, the fronts were 7 and 1, which differ by 6, so left moved to index 2 and the 1 expired.
def longest_subarray(nums, limit):
high = deque() # indices; values never increase front to back
low = deque() # indices; values never decrease front to back
left = best = 0
for right, x in enumerate(nums):
while high and nums[high[-1]] < x:
high.pop()
high.append(right)
while low and nums[low[-1]] > x:
low.pop()
low.append(right)
while nums[high[0]] - nums[low[0]] > limit:
left += 1
if high[0] < left:
high.popleft()
if low[0] < left:
low.popleft()
best = max(best, right - left + 1)
return best
print(longest_subarray([8, 2, 4, 7], 4))
print(longest_subarray([10, 1, 2, 4, 7, 2], 5))
print(longest_subarray([4, 2, 2, 2, 4, 4, 2, 2], 0))Each pass of the shrinking loop moves left one position, so one index leaves the window: the one left has just passed. If that index is still in a deque, it is at the front, because the indices in a deque increase from front to back. So one if for each deque is enough, and it removes the front only when the front index is now less than left.
One front can stay while the other leaves, as the 7 did when the 1 expired. The loop cannot empty the window: if left reaches right, the arriving index is the front of both deques, so the two front values are equal, their difference of 0 is within the limit, and the shrinking stops.
Cost of the scan
- Reading through the window at each step
time - Up to reads at each of steps, in all.
- Two monotonic queues
time, extra memory - Each index enters each deque once and leaves it at most once.
An index is added to each deque once and can be removed from each at most once, from the back or from the front. That is at most 4 deque operations per index and for the whole scan, in addition to the moves of right and at most moves of left. On the second sample the scan makes 20 deque operations, under the bound of .
Step through the two deques
The widget runs the same scan one operation at a time. Each step is one of four things:
- an index leaves the back of a deque
- an index joins the back of a deque
leftmoves, and a front expires if it was the indexleftpassed- the length of the window is recorded
It starts on the second sample. The other two examples are an array of 4s and 2s with a limit of 0, and an increasing array whose window never shrinks.
In the increasing array, each arrival removes the previous index from the max deque, which holds one index throughout. The min deque keeps every index, because no arriving value is smaller than the ones before it. In the array with a limit of 0, a valid window can only hold copies of one value. Equal values stay side by side in both deques, because the max deque removes only values strictly smaller than the arriving one, and the min deque only values strictly larger.
Deeper read: other ways to keep a window's maximum
Three other structures can keep the maximum of a moving window.
A sorted container holds the window's values in order, so the smallest and largest are at its two ends. Python has none built in; the third-party sortedcontainers package provides SortedList. Adding and removing a value take about each, so the scan takes .
A heap, which keeps its largest value at the top, can be used with lazy deletion: expired indices stay inside, and one is removed only when it reaches the top. This also takes .
A queue built from two stacks, where each stack stores beside every value the maximum of that value and everything below it, gives the maximum in amortized time per operation. It can also keep summaries that a monotonic deque cannot, for any associative operation, one that gives the same result however its inputs are grouped. The greatest common divisor is one: a window's gcd depends on all of its values, so no single value at a deque's front gives it, but each stack can store beside every value the gcd of that value and everything below it. The cp-algorithms page in Further reading builds this queue.
Common monotonic queue mistakes
Removing both deque fronts on every move of
left.- Where it breaks
- On
[10, 1, 2, 4, 7, 2]with a limit of 5,leftmoves to 1 and the min deque loses index 1, whose value 1 is still in the window. The min deque is now empty, and the next test of the loop reads the front of an empty deque. - The fix
- Remove a front only when its index is less than
left.
Copying the max deque's loop for the min deque without reversing the comparison.
- Where it breaks
- Both deques then hold the same indices, the two fronts are always equal, and the window never shrinks. On
[8, 2, 4, 7]with a limit of 4 the function returns4instead of2. - The fix
- The max deque removes smaller values from its back, and the min deque removes larger ones.
Recall In the second sample, why may the min deque throw away the 7 at index 4 when the 2 at index 5 arrives?
Any later window that contains index 4 also contains index 5, because left only moves right. The minimum of that window is at most 2, so the 7 can never be a minimum again.