The example problem
Given a list of numbers and a window size k, find the largest sum of k neighbouring numbers.
Input: [2, 1, 5, 1, 3, 2, 4, 1, 2], k = 3 Output: 9 (5 + 1 + 3, or 3 + 2 + 4)
Picture it
Picture riding a train past a row of houses; the window always shows exactly k houses, and each house has some lit windows. Instead of recounting all k houses at every stop, when the train moves one house forward we add the house that appears and subtract the one that disappears.
The key idea
Fixed-size sliding window: update the sum by +new − old. O(n) instead of O(n × k).
Python
def max_window(lit, k):
total = sum(lit[:k])
best = total
for i in range(k, len(lit)):
total += lit[i] - lit[i - k]
best = max(best, total)
return bestPractise sliding window
NeetCode 150 problems that use it
Sliding Window ·
- LeetCode 121 · EasyBest Time to Buy and Sell StockBuying the dip on a price chart
- LeetCode 3 · MediumLongest Substring Without Repeating CharactersA train window over shop signs
- LeetCode 424 · MediumLongest Repeating Character ReplacementRepainting a few fence planks
- LeetCode 567 · MediumPermutation in StringA letter stencil sliding along a strip
- LeetCode 76 · HardMinimum Window SubstringThe smallest net that catches every fish
- LeetCode 239 · HardSliding Window MaximumThe tallest tower in view from a train