Sliding window

Answer 'longest or shortest contiguous range such that…' in one pass by growing a window on the right and shrinking it on the left.

Fixed-size windows#

"Maximum sum of any k consecutive elements." The first window is nums[0..k-1]. To slide by one, add the element entering on the right and subtract the one leaving on the left:

Trace nums = [2, 1, 5, 1, 3, 2], k = 3:

window	enters	leaves	sum	best
[2 1 5]			8	8
[1 5 1]	1	2	7	8
[5 1 3]	3	1	9	9
[1 3 2]	2	5	6	9

Each slide is O(1), so the total is O(n) instead of O(n·k).

Run the trace

fixed_trace.go

package main
 
import "fmt"
 
func main() {
	nums, k := []int{2, 1, 5, 1, 3, 2}, 3
	sum := 0
	for _, n := range nums[:k] {
		sum += n
	}
	best := sum
	fmt.Printf("window %v sum=%d best=%d\n", nums[:k], sum, best)
	for right := k; right < len(nums); right++ {
		left := right - k // the element leaving the window
		sum += nums[right] - nums[left]
		best = max(best, sum)
		fmt.Printf("window %v +%d -%d sum=%d best=%d\n", nums[left+1:right+1], nums[right], nums[left], sum, best)
	}
}

Output

window [2 1 5] sum=8 best=8
window [1 5 1] +1 -2 sum=7 best=8
window [5 1 3] +3 -1 sum=9 best=9
window [1 3 2] +2 -5 sum=6 best=9

Step through it

InteractiveSliding window: max sum of k in a rowSlide a window of size k: add the element entering on the right, subtract the one leaving on the left.

window [0, 2]sum 8best 8

02left

25right

First window: 2 + 1 + 5 = 8.

1 / 7

Variable-size windows#

The general template:

left := 0
for right := 0; right < len(s); right++ {
	// 1. add s[right] to the window's state
	for /* window is invalid (or: while still valid, for "shortest") */ {
		// 2. remove s[left] from the state
		left++
	}
	// 3. update the answer using right-left+1
}

Two flavors:

Goal	Shrink when	Record answer
longest valid window	the window becomes invalid	after shrinking (window is valid again)
shortest valid window	the window is valid	inside the shrink loop, before each shrink

Longest substring without repeating characters

The window is valid while every character appears once. Store, for each byte, one past the index where it last appeared. When s[right] was last seen inside the window, jump left past it.

Trace s = "abcabcbb":

right	char	last[char] before	left after	window	best
0	a	0	0	a	1
1	b	0	0	ab	2
2	c	0	0	abc	3
3	a	1	1	bca	3
4	b	2	2	cab	3
5	c	3	3	abc	3
6	b	5	5	cb	3
7	b	7	7	b	3

Storing index + 1 means the zero value 0 already means "never seen", so the array needs no initialization, and max(left, last[c]) ignores old positions that are already outside the window.

Run the trace

longest_trace.go

package main
 
import "fmt"
 
func main() {
	s := "abcabcbb"
	var last [128]int // last[c] = 1 + index where c was last seen; 0 = never
	left, best := 0, 0
	for right := 0; right < len(s); right++ {
		c := s[right]
		before := last[c]
		left = max(left, last[c]) // jump past the previous copy if it is inside the window
		last[c] = right + 1
		best = max(best, right-left+1)
		fmt.Printf("right=%d char=%c last=%d left=%d window=%-3s best=%d\n", right, c, before, left, s[left:right+1], best)
	}
}

Output

right=0 char=a last=0 left=0 window=a   best=1
right=1 char=b last=0 left=0 window=ab  best=2
right=2 char=c last=0 left=0 window=abc best=3
right=3 char=a last=1 left=1 window=bca best=3
right=4 char=b last=2 left=2 window=cab best=3
right=5 char=c last=3 left=3 window=abc best=3
right=6 char=b last=5 left=5 window=cb  best=3
right=7 char=b last=7 left=7 window=b   best=3

Step through it

InteractiveSliding window: longest substring without repeatsGrow the window on the right; when a character repeats, jump the left edge past its previous copy.

left 0right 0best 1

0aleft/right

'a' is new to the window. Window "a" has length 1.

1 / 9

Shortest subarray with sum at least target

Valid means sum >= target. As soon as it is valid, record the length and shrink to look for something shorter. This only works when all numbers are positive, because then adding always grows the sum and removing always shrinks it.

Run the trace

Valid windows are recorded inside the shrink loop, before each shrink, exactly as the "shortest" row of the template table says:

shortest_trace.go

package main
 
import "fmt"
 
func main() {
	nums, target := []int{2, 3, 1, 2, 4, 3}, 7
	left, sum, best := 0, 0, len(nums)+1
	for right, n := range nums {
		sum += n
		fmt.Printf("add %d   window %v sum=%d\n", n, nums[left:right+1], sum)
		for sum >= target {
			best = min(best, right-left+1)
			fmt.Printf("  valid, length %d recorded; drop %d\n", right-left+1, nums[left])
			sum -= nums[left]
			left++
		}
	}
	fmt.Println("shortest:", best)
}

Output

add 2   window [2] sum=2
add 3   window [2 3] sum=5
add 1   window [2 3 1] sum=6
add 2   window [2 3 1 2] sum=8
  valid, length 4 recorded; drop 2
add 4   window [3 1 2 4] sum=10
  valid, length 4 recorded; drop 3
  valid, length 3 recorded; drop 1
add 3   window [2 4 3] sum=9
  valid, length 3 recorded; drop 2
  valid, length 2 recorded; drop 4
shortest: 2

The full program#

window.go

package main
 
import (
	"fmt"
	"math"
)
 
func maxSumK(nums []int, k int) int {
	sum := 0
	for i := range k {
		sum += nums[i]
	}
	best := sum
	for i := k; i < len(nums); i++ {
		sum += nums[i] - nums[i-k] // enter right, leave left
		best = max(best, sum)
	}
	return best
}
 
func lengthOfLongestSubstring(s string) int {
	var last [128]int // last index + 1 of each ASCII byte
	best, left := 0, 0
	for right := 0; right < len(s); right++ {
		c := s[right]
		left = max(left, last[c])
		last[c] = right + 1
		best = max(best, right-left+1)
	}
	return best
}
 
func minSubArrayLen(target int, nums []int) int {
	best, sum, left := math.MaxInt, 0, 0
	for right, n := range nums {
		sum += n
		for sum >= target {
			best = min(best, right-left+1)
			sum -= nums[left]
			left++
		}
	}
	if best == math.MaxInt {
		return 0
	}
	return best
}
 
func checkInclusion(s1, s2 string) bool {
	if len(s1) > len(s2) {
		return false
	}
	var need, have [26]int
	for i := 0; i < len(s1); i++ {
		need[s1[i]-'a']++
		have[s2[i]-'a']++
	}
	for i := len(s1); ; i++ {
		if need == have { // arrays compare element by element
			return true
		}
		if i == len(s2) {
			return false
		}
		have[s2[i]-'a']++
		have[s2[i-len(s1)]-'a']--
	}
}
 
func maxProfit(prices []int) int {
	minPrice, best := math.MaxInt, 0
	for _, p := range prices {
		minPrice = min(minPrice, p)
		best = max(best, p-minPrice)
	}
	return best
}
 
func main() {
	fmt.Println(maxSumK([]int{2, 1, 5, 1, 3, 2}, 3))
	fmt.Println(lengthOfLongestSubstring("abcabcbb"), lengthOfLongestSubstring("pwwkew"), lengthOfLongestSubstring(""))
	fmt.Println(minSubArrayLen(7, []int{2, 3, 1, 2, 4, 3}), minSubArrayLen(100, []int{1, 2}))
	fmt.Println(checkInclusion("ab", "eidbaooo"), checkInclusion("ab", "eidboaoo"))
	fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
}

Output

9
3 3 0
2 0
true false
5

Complexity#

Problem	Time	Space
fixed window max sum	O(n)	O(1)
longest substring without repeats	O(n)	O(1) (128 counters)
shortest subarray with sum ≥ target	O(n)	O(1)
permutation in string	O(n)	O(1) (two arrays of 26)

Recognizing the pattern#

The words contiguous, substring or subarray, combined with longest, shortest, maximum or at most k distinct, almost always mean a sliding window. If the condition can break and recover as numbers change sign, use prefix sums instead.

Summary#

A window is a contiguous range whose edges only move forward: O(n) overall.
Fixed windows: add the entering element, subtract the leaving one.
Variable windows: expand right; shrink left while invalid (longest) or while valid (shortest).
Track window contents with counters ([128]int, [26]int) or maps.
Sum-based windows require non-negative numbers.

Fixed-size windows#

Run the trace

Step through it

Variable-size windows#

Longest substring without repeating characters

Run the trace

Step through it

Shortest subarray with sum at least target

Run the trace

The full program#

Complexity#

Recognizing the pattern#

Summary#

Check your understanding

Practice in Go