What is Sliding Window

An algorithm that explores subarrays of an array by shifting a "window (subset)".

The window size can be fixed or dynamic.

A practical example is its use in rate limiters.

Implementation

The source code is below.

A function that searches for subarrays whose sum is greater than or equal to N from a given array.

package main

import "fmt"

func SlidingWindow(s []int, sum int) [][]int {
	rslt := [][]int{}
	windowSum := 0
	windowStart := 0

	for windowEnd := 0; windowEnd < len(s); windowEnd++ {
		windowSum += s[windowEnd]

		// Find subarray
		for windowSum >= sum {
			rslt = append(rslt, s[windowStart:windowEnd+1])
			windowSum -= s[windowStart]
			windowStart++
		}
	}

	return rslt
}

func main() {
	s := []int{1, 3, 2, 6, 4, 9, 9, 5}
	sum := 9
	subAry := SlidingWindow(s, sum)
	for _, sa := range subAry {
		fmt.Println(sa)
	}
}

// Output
[1 3 2 6]
[3 2 6]
[2 6 4]
[6 4]
[4 9]
[9]
[9]

The process flow of the SlidingWindow function is as follows.

Place the window from the start of the data to the starting position
Check if the elements within the window meet the condition
If the condition is met, add the subarray within the window to the result
Slide the window one step to the right
Repeat steps 3 to 5 until the window reaches the end of the data

The image of the window sliding is as follows.

[1 3 2 6] ← The first window found that meets the condition
[3 2 6] ← Further exploration within the window that meets the condition

[2 6 4]  ← Shift the starting position to secure the next window
[6 4]   ← Further exploration within the window

Repeat below...
[4 9]
[9]

[9]

It can be applied to problems dealing with arrays.

Although not the optimal solution, leetcode.com - two-sum can also be solved using the sliding window.