A window of fixed length
Two pointers can start at opposite ends of a sorted array and move toward each other. On this page both pointers move in the same direction, from left to right, and each problem asks something about the stretch of the array from one pointer to the other, such as the sum of its values or which characters it holds. We start with the simplest case, where that stretch always has the same length.
You get an array nums of integers and a length . Among all runs of exactly consecutive elements, find the largest average and return it. Answers within of the true value are accepted.
Constraints
-
nums[i]
Sample 1 · Input
nums = [1,12,-5,-6,50,3], k = 4
Output
12.75000
Sample 2 · Input
nums = [5], k = 1
Output
5.00000
In the first sample is 4, and the array has three runs of four consecutive values:
positions 0 to 3 1 12 -5 -6 sum 2positions 1 to 4 12 -5 -6 50 sum 51positions 2 to 5 -5 -6 50 3 sum 42A run of consecutive values like these is a subarray. All three have the same length, so the one with the largest sum also has the largest average, and the answer is . From here on we look for the largest sum and divide by once at the end.
The direct method adds up every subarray of length separately. An array of values has of them, one for each starting position from 0 to , and adding up each one reads values. The total number of reads is largest when is about half of . The problem allows , and with the direct method makes
which at the usual budget of about simple operations a second is 25 seconds of work.
Slide the window one position at a time
Most of those reads are repeated, because neighbouring subarrays overlap. Positions 0 to 3 hold 1, 12, -5, -6 and positions 1 to 4 hold 12, -5, -6, 50, so three of the four values are in both. We do not need to add four values again to get the second sum. We take the first sum, add the 50 that came in on the right and subtract the 1 that went out on the left:
A sliding window is a range of consecutive positions that moves through an array from left to right. As it moves, we keep a summary of the values inside it, and here the summary is their sum. Each time the window moves, we correct the summary for the one value that enters and the one that leaves. For a sum, the correction is one addition and one subtraction instead of the additions it takes to add up the window again.
In code, total is the sum of the current window and best is the largest sum seen:
def find_max_average(nums, k):
total = sum(nums[:k])
best = total
for i in range(k, len(nums)):
total += nums[i] - nums[i - k]
best = max(best, total)
return best / k
print(find_max_average([1, 12, -5, -6, 50, 3], 4))
print(find_max_average([5], 1))In the loop, i is the position that enters the window, so the position that leaves is i - k. When the 50 enters at position 4, the value at position leaves.
The first window costs additions, and each of the other windows costs one addition and one subtraction. That is steps, which is less than . At the scan takes under 200,000 steps. Adding up every window took 2.5 billion.
Let the window grow and shrink
A window of fixed length answers questions about subarrays of one given length. Many problems leave the length open and ask for the longest subarray that satisfies a condition. Here is one: given an array nums of nonnegative numbers and a limit, find the length of the longest subarray whose sum is at most the limit. We will use the array [2, 1, 3, 1] with a limit of 4. The subarrays [2, 1], [1, 3] and [3, 1] are within the limit, while the two subarrays of length 3, [2, 1, 3] and [1, 3, 1], sum to 6 and 5, and the whole array to 7, all over 4. So the answer is 2.
Checking every subarray is too slow for a long array. An array of values has subarrays that start at position 0, that start at position 1, and so on down to the one that starts at the last position, which makes in all. Even at one operation per subarray, means 50 seconds of work at operations a second:
A window finds the answer in one pass. We keep two positions, left and right, the first and last positions of the window, and total, the sum of the values from left to right. We move right forward one position at a time and add each new value to total. Whenever total goes over the limit, we subtract nums[left] from it and move left forward by one, and we repeat that until the window is within the limit again. Then we compare the length of the window, right - left + 1, with the longest seen so far.
Moving left forward gives up on a starting position for good, so we need a reason why that loses nothing. Take the moment when [2, 1, 3] goes over the limit with a sum of 6. Any longer window that starts at the 2 contains these three values and more, and the extra values are not negative, so its sum is at least 6 as well. No window that starts at position 0 and ends at position 2 or later can be within the limit. The shorter ones, [2] and [2, 1], were measured at earlier steps, so we are done with position 0 as a start. The same reasoning applies every time left moves.
So when the removals stop, the window is the longest one within the limit that ends at right. The answer is the longest of these windows over every position of right.
Run the window by hand
Here is the scan on our array. Each row adds one value on the right, then removes values from the left while the sum is over 4.
| Value added | Window and sum | Removed | Window kept | Longest so far |
|---|---|---|---|---|
| 2 | [2], sum 2 | nothing | [2] | 1 |
| 1 | [2, 1], sum 3 | nothing | [2, 1] | 2 |
| 3 | [2, 1, 3], sum 6 | the 2 at position 0 | [1, 3], sum 4 | 2 |
| 1 | [1, 3, 1], sum 5 | the 1 at position 1 | [3, 1], sum 4 | 2 |
Choose each move yourself
Now choose the moves yourself. The array is [2, 1, 3, 1] with three more values, 1, 1, 4, added at the end, and the limit is still 4. At each step, extend the window on the right or shrink it on the left. If you pick a move the loop would not make, the widget explains why and leaves the window as it is. The dashed outline marks the longest window so far, and the two counters show how many times each end has moved.
The longest window is [1, 1, 1], positions 3 to 5. When the 4 arrives, the sum jumps to 7, and all three 1s have to leave before the window is within the limit again. Over the whole run, right moves 7 times and left 6 times. Neither counter can pass 7, the length of the array.
Write the window as two loops
In code, the outer loop moves right across the array, and the inner loop moves left until the window is within the limit again. The length is recorded after the inner loop, so only windows within the limit are measured.
def longest_within(nums, limit):
left = total = best = 0
for right, value in enumerate(nums):
total += value
while total > limit:
total -= nums[left]
left += 1
best = max(best, right - left + 1)
return best
print(longest_within([2, 1, 3, 1], 4))
print(longest_within([2, 1, 3, 1, 1, 1, 4], 4))The inner loop is a while and not an if because one arriving value can push out several, as the 4 did in the widget. Inside it, nums[left] is subtracted before left increases, so the value subtracted is the one that leaves the window.
The two calls at the end run the table's array and the widget's array, and print 2 and 3.
A value that is larger than the limit by itself needs no special case. The inner loop removes everything up to and including it, which leaves left equal to right + 1. That is an empty window: its total is 0, its length right - left + 1 is 0, and the next value starts a new window.
Cost of a window
- Checking every subarray
time - subarrays to check.
- Fixed-length window
time, extra memory - One addition and one subtraction per position after the first window.
- Growing and shrinking window
time, extra memory rightmoves times andleftat most times.
A loop inside a loop often means quadratic time. To see whether it does here, count the inner loop's steps over the whole run instead of for one value of right. Each step of the inner loop moves left forward by one. left never moves back, and it stops at right + 1 at the latest, so the inner loop takes at most steps in the whole run. Together with the steps of the outer loop, that is at most steps, or 200,000 for an array of 100,000 values.
So each value of right has an amortized cost of . An amortized cost bounds the average over a whole run of operations: here values take at most steps in all. A single value can take more than its share. The value 4 in the widget took four steps, one to add it and three to remove the 1s before it, but the average over the whole scan is still at most 2.
Worked example
Trace the window step by step
The trace runs the same loop one step at a time on [2, 1, 3, 1]. The other three inputs are edge cases. In the first, one value removes three. In the second, a value is larger than the limit by itself and empties the window. The third is an array of zeros with a limit of 0, where the window keeps every value.
The current interval is empty. Nonnegative values make shrinking a valid repair for an excessive sum.
- sum
- 0
- best
- 0
Change the example input
Current result: 2
Negative values and the shrinking window
The argument for giving up on a start used one fact about the array: its values are not negative, so the sum of a window cannot go down when the window is extended. With a negative value in the array, that is no longer true. Run the same loop on [5, -4, 3] with a limit of 4. The 5 is over the limit by itself, so the window drops it. The loop then measures [-4] and [-4, 3], and returns 2. But the whole array sums to , which is within the limit, so the right answer is 3.
The loop gave up on position 0 when [5] went over the limit. Dropping position 0 is safe only if every longer window that starts there is over the limit too. Here the brought the next window's sum down to 1, and the whole array, with sum 4, was within the limit.
So the shrinking loop depends on a property of the condition: once a window breaks it, every longer window that contains that window breaks it too. A limit on a sum has this property when the values are nonnegative.
The rest of this page uses the same loop with other conditions, and for each one we check this property first. For sums over an array that can hold negative values, the shrinking window does not work, and the next lesson, Prefix sums, has a method that does.
Find the shortest window that reaches a target
The longest-window loop shrinks a window that has become invalid. The next problem asks for the opposite kind of answer, the shortest subarray whose sum is large enough:
You get an array nums of positive integers and a positive integer target. Return the length of the shortest subarray whose sum is at least target, or 0 if no subarray reaches it.
Constraints
-
target -
len(nums) -
nums[i]
Sample 1 · Input
target = 7, nums = [2,3,1,2,4,3]
Output
2
Sample 2 · Input
target = 4, nums = [1,4,4]
Output
1
Sample 3 · Input
target = 11, nums = [1,1,1,1,1,1,1,1]
Output
0
In the first sample, [4, 3] sums to 7 and no single value reaches 7, so the answer is 2. Here a window is valid when its sum has reached the target. The values are positive, so extending a valid window keeps it valid. In the longest-window problem it was the invalid windows that stayed invalid when extended.
The loop changes to match: we still add one value on the right at each step, but now we shrink while the window is valid, and we record its length before each removal, because every window on the way down reaches the target and each is shorter than the one before. The inner loop stops when the sum falls below the target.
Here is the loop on the first sample:
| Values added | Windows recorded | Window left after shrinking | Shortest so far |
|---|---|---|---|
| 2, 3, 1 | none: the sums 2, 5 and 6 are below 7 | [2, 3, 1] | none |
| 2 | [2, 3, 1, 2], sum 8 | [3, 1, 2], sum 6 | 4 |
| 4 | [3, 1, 2, 4], sum 10, then [1, 2, 4], sum 7 | [2, 4], sum 6 | 3 |
| 3 | [2, 4, 3], sum 9, then [4, 3], sum 7 | [3] | 2 |
def min_sub_array_len(target, nums):
left = total = 0
best = len(nums) + 1
for right, value in enumerate(nums):
total += value
while total >= target:
best = min(best, right - left + 1)
total -= nums[left]
left += 1
return 0 if best == len(nums) + 1 else best
print(min_sub_array_len(7, [2, 3, 1, 2, 4, 3]))
print(min_sub_array_len(4, [1, 4, 4]))
print(min_sub_array_len(11, [1] * 8))Dropping a start is safe here for a different reason. When the inner loop finds the window from left to right valid, no shorter valid window starts at left. A shorter one would end before right, so it would lie inside the window left over from the previous step, which was below the target. The values are positive, so a window inside it has a sum no larger, and it is below the target too.
In the sample, [3, 1, 2, 4] becomes valid when the 4 arrives. Every shorter window that starts at the 3 lies inside [3, 1, 2], whose sum is 6. Windows from left that end after right are longer, so once the length is recorded, no better window can start at left, and we can drop it.
best starts at , a length no window can have. If it still has that value at the end, no subarray reached the target and the function returns 0, as in the third sample.
Count the subarrays that satisfy a condition
A window can also count subarrays. Counting takes the longest-window loop and one more line.
You get an array nums of positive integers and an integer k. Count the subarrays whose product is strictly less than k.
Constraints
-
len(nums) -
nums[i]
Sample 1 · Input
nums = [10,5,2,6], k = 100
Output
8
Sample 2 · Input
nums = [1,2,3], k = 0
Output
0
In the first sample, the eight subarrays are the four single values, [10, 5], [5, 2], [2, 6] and [5, 2, 6]. The subarray [10, 5, 2] is not counted, because its product is exactly 100. Testing every subarray would take products, which is 450,015,000 for the largest array the problem allows, about 4.5 seconds of work.
Every value is at least 1, so a product cannot get smaller when the window is extended. A window whose product has reached stays at or above when it is extended, which is the property we need. The loop is the longest-window loop with a product in place of the sum: it multiplies in the value at right, then divides out values at left while the product is or more. The division is exact, because the product was built from those values.
The new line comes after the inner loop. At that point, the window from left to right is the longest one that ends at right and has a product below . Every shorter subarray that ends at right lies inside it, so its product is below as well. Every longer one starts before left, and those starts have been ruled out. So exactly right - left + 1 of the subarrays that end at right should be counted, one for each start from left to right. Adding that number at every step counts each subarray once, at the step where right is its last position.
right = 3 the window is [5, 2, 6]. Each subarray that ends at the 6 and starts inside the window has a product below 100, so this step adds to the count.def num_subarray_product_less_than_k(nums, k):
if k <= 1:
return 0
left = count = 0
product = 1
for right, value in enumerate(nums):
product *= value
while product >= k:
product //= nums[left]
left += 1
count += right - left + 1
return count
print(num_subarray_product_less_than_k([10, 5, 2, 6], 100))
print(num_subarray_product_less_than_k([1, 2, 3], 0))On the sample, the four steps add .
The function returns 0 at once when is 1 or less. No product of positive integers is below 1, so 0 is the right answer. Without that check the loop gets this case wrong. An empty window has the product 1, which is not below , so the inner loop keeps going: left moves past right, and the loop divides by values that were never multiplied in. Without the check, the function returns 2 on the first sample's array with , and with it reads past the end of the array.
Keep a count of each character in the window
In every window so far, the summary was one number. The summary can also be a small table. The next problem needs to know which characters the window holds:
You get a string s. Return the length of its longest substring in which no character appears twice.
Constraints
-
len(s) sholds English letters, digits, symbols and spaces
Sample 1 · Input
s = "abcabcbb"
Output
3
Sample 2 · Input
s = "bbbbb"
Output
1
Sample 3 · Input
s = "pwwkew"
Output
3
A substring is a subarray of a string. In the three samples the longest substrings without a repeat are "abc", "b" and "wke". A window is valid here when no character occurs in it twice, and to test that we keep a count of how many times each character occurs in the window.
The counts go in a dictionary from each character to its count. It holds at most one entry for each character the problem allows, however long the string is.
When a character arrives, we add 1 to its count. If the count is now 2, the window holds that character twice. We then remove characters from the left, taking 1 off the count of each, until the count of the new character is back to 1. The window was valid before the arrival, so the arriving character is the only one that can be repeated, and the inner loop tests only its count.
The property holds here too. A window with a repeated character still has the repeat however far it is extended, so a start that has been dropped cannot begin a valid window later.
def length_of_longest_substring(s):
count = {}
left = best = 0
for right, ch in enumerate(s):
count[ch] = count.get(ch, 0) + 1
while count[ch] > 1:
count[s[left]] -= 1
left += 1
best = max(best, right - left + 1)
return best
for s in ["abcabcbb", "bbbbb", "pwwkew"]:
print(length_of_longest_substring(s))On "abcabcbb", the window grows to "abc". The second a arrives at position 3 and raises the count of a to 2. The first a leaves, and the window is "bca", still of length 3.
Deeper read: the shortest window that contains every character of another string
The hard problem in this lesson's practice list combines two parts of this page: the shortest-window loop and the counts per character.
You get strings s and t. Return the shortest substring of s that contains every character of t, with repeats counted: if t has two as, the window needs two. Return the empty string if no substring works. The tests guarantee the answer is unique.
Constraints
-
len(s),len(t) sandthold uppercase and lowercase English letters
Sample 1 · Input
s = "ADOBECODEBANC", t = "ABC"
Output
"BANC"
Sample 2 · Input
s = "a", t = "a"
Output
"a"
Sample 3 · Input
s = "a", t = "aa"
Output
""
A window is valid when it holds every character of t at least as many times as t does. Extending a valid window keeps it valid, so the shortest-window loop applies: add a character on the right, and while the window is valid, record it and remove a character on the left.
The new part is the test for a valid window. Comparing the count of every character with t at each step would work, but two small pieces of bookkeeping make the test a single comparison. For each character, need[ch] is how many more copies of ch the window has to take in. It starts as the number of times ch occurs in t and goes down by 1 whenever a ch enters the window. A value below 0 counts spare copies in the window. The number missing is how many characters of t, counting repeats, the window still lacks. It starts at the length of t, and the window is valid exactly when it is 0.
The two are updated together. A character that enters while its need is above 0 was wanted, so missing goes down by 1. When a spare copy enters, missing does not change. A character that leaves raises its need by 1, and if need is then above 0, the window has lost a copy it required, so missing goes up by 1 and the inner loop stops.
def min_window(s, t):
need = {}
for ch in t:
need[ch] = need.get(ch, 0) + 1
missing = len(t)
left = 0
best_len, best_start = len(s) + 1, 0
for right, ch in enumerate(s):
if need.get(ch, 0) > 0:
missing -= 1
need[ch] = need.get(ch, 0) - 1
while missing == 0:
if right - left + 1 < best_len:
best_len, best_start = right - left + 1, left
need[s[left]] += 1
if need[s[left]] > 0:
missing += 1
left += 1
if best_len == len(s) + 1:
return ""
return s[best_start:best_start + best_len]
print([min_window("ADOBECODEBANC", "ABC"), min_window("a", "a"), min_window("a", "aa")])On the first sample, the window is first valid at "ADOBEC", of length 6. Removing the A makes it invalid, and it stays invalid until the next A arrives at position 10. The window is then "DOBECODEBA", and the loop shrinks it down to "CODEBA", also of length 6, before removing the C. The last C of s makes the window, now "ODEBANC", valid once more. The shrinking ends at "BANC", of length 4, which is the answer.
Common sliding-window mistakes
Recording the window's length before the window has been shrunk.
- Where it breaks
- On
[2, 1, 3, 1]with a limit of 4, recording right after adding the 3 measures[2, 1, 3], whose sum is 6, and the function returns3instead of2. - The fix
- For a longest window, shrink first and record after the
whileloop.
Shrinking with
ifinstead ofwhilein the character-count loop.- Where it breaks
- On
"abcbd", the secondbremoves only thea, so the window"bcb"still holds twobs. Thedthen extends it to"bcbd", and the function returns4instead of3. - The fix
- Use
while, so that characters keep leaving until the window is valid again.
Recall The longest-window loop records the length after its inner loop, and the shortest-window loop records it inside the inner loop. Why?
In the longest-window loop, the window is over the limit while the inner loop runs, so the first window that may be measured is the one that remains when the loop ends.
In the shortest-window loop, the window reaches the target while the inner loop runs and gets shorter with each removal, so each of those windows is a candidate. When the loop ends, the window is below the target and must not be measured.