Skip to main content
Definition Website Computer and Technology

Sliding Window Technique

Subject: Computer and Technology noun /ˈslaɪ.dɪŋ ˈwɪn.doʊ tɛkˈniːk/ 1 definition

  1. Definition (noun)

    Entry #291 · Updated

    The 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 left and right pointers 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-force O(n * k) or O(n^2) scans to linear O(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 k elements by advancing both boundaries together one index per step, adding the incoming element and subtracting the outgoing element to compute rolling averages, maximum k-element subarray sums, or fixed-length anagram matches in O(n) time.

    • Variable-Size (Dynamic) Sliding Window: Expands the right boundary to admit elements until a condition holds or breaks, then contracts the left boundary 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 initial k = 5 window across indices 0 through 4 (6400 bytes). As the window slides one slot to indices 1 through 5, it updates window_sum += bytes[5] - bytes[0] (+ 1400 - 1200) to compute 6600 bytes in O(1) time instead of resumming five elements on every tick.