Arrays and searching 0/120

Sliding window · 1 of 2

Sliding window technique

Keep a running summary of a subarray while its ends move forward, for windows of fixed length and windows that grow and shrink.

3,974 words · 18 min read

Part 1 of 8 A window of fixed length

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 nn integers and a length kk. Among all runs of exactly kk consecutive elements, find the largest average and return it. Answers within 10−510^{-5} of the true value are accepted.

Constraints

  • 1≤k≤n≤1051 \le k \le n \le 10^5
  • −104≤-10^4 \le nums[i] ≤104\le 10^4

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 kk 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 42

A 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 51/4=12.7551 / 4 = 12.75. From here on we look for the largest sum and divide by kk once at the end.

The direct method adds up every subarray of length kk separately. An array of nn values has n−k+1n - k + 1 of them, one for each starting position from 0 to n−kn - k, and adding up each one reads kk values. The total number of reads is largest when kk is about half of nn. The problem allows n=105n = 10^5, and with k=50,000k = 50{,}000 the direct method makes

(n−k+1)×k=50,001×50,000=2,500,050,000 reads,\begin{aligned} (n - k + 1) \times k &= 50{,}001 \times 50{,}000 \\ &= 2{,}500{,}050{,}000 \text{ reads}, \end{aligned}

which at the usual budget of about 10810^8 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:

2+50−1=512 + 50 - 1 = 51

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 kk additions it takes to add up the window again.

Each slide adds the value that enters and subtracts the one that leaves. The best window, sum 51, is the second.

In code, total is the sum of the current window and best is the largest sum seen:

Sign up to run
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 4−4=04 - 4 = 0 leaves.

The first window costs kk additions, and each of the other n−kn - k windows costs one addition and one subtraction. That is k+2(n−k)k + 2(n - k) steps, which is less than 2n2n. At n=105n = 10^5 the scan takes under 200,000 steps. Adding up every window took 2.5 billion.