Sliding Window Technique
Subject: Computer and Technology noun /ˈslaɪ.dɪŋ ˈwɪn.doʊ tɛkˈniːk/ 1 definition
- algorithm-design
- data-structures
- computational-complexity
- computer-science
-
Definition (noun)
Entry #291 · UpdatedThe Sliding Window Technique is an algorithmic optimization pattern for linear sequences—such as arrays, strings, and sequential data streams—that inspects contiguous subranges within a single traversal. Rather than recalculating a metric from scratch over every overlapping slice, the algorithm tracks a window bounded by
leftandrightpointers and incrementally updates auxiliary state—such as a running sum, frequency map, or monotonic deque—as elements enter the leading edge and leave the trailing edge. Reusing shared computation across adjacent windows reduces brute-forceO(n * k)orO(n^2)scans to linearO(n)time while keeping memory overhead bounded by the active window or alphabet size. Because it relies on contiguous boundaries and incrementally maintainable or monotonic window conditions, the technique cannot handle non-contiguous subsequences or non-monotonic constraints—such as variable-size target sums containing negative numbers—where prefix-sum hash maps or dynamic programming are required instead.Common Forms
Fixed-Size Sliding Window: Maintains a constant span of
kelements by advancing both boundaries together one index per step, adding the incoming element and subtracting the outgoing element to compute rolling averages, maximumk-element subarray sums, or fixed-length anagram matches inO(n)time.Variable-Size (Dynamic) Sliding Window: Expands the
rightboundary to admit elements until a condition holds or breaks, then contracts theleftboundary to restore validity or shrink the range, ideal for finding the longest duplicate-free substring or shortest subarray meeting a target sum.Monotonic Queue Sliding Window: Augments the moving boundaries with a double-ended queue ordered monotonically (increasing or decreasing), evicting expired indices from the front and dominated candidates from the back to query sliding window extrema in
O(n)total time.Time-Based Stream Window: Defines window boundaries over logical or wall-clock timestamps rather than array indices, expiring stale events from ring buffers, event logs, or weighted buckets in stream-processing engines, metrics aggregators, and API rate limiters.
Example
A network telemetry daemon computes 5-second rolling throughput over packet byte counts
[1200, 800, 1500, 2000, 900, 1400, 1100]by summing the initialk = 5window across indices0through4(6400bytes). As the window slides one slot to indices1through5, it updateswindow_sum += bytes[5] - bytes[0](+ 1400 - 1200) to compute6600bytes inO(1)time instead of resumming five elements on every tick.