✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-223

Sliding Window Technique

The Sliding Window Technique processes a continuous section of an array or string while moving its boundaries, reducing repeated calculations in many subarray and substring problems.

Explanation

Overview

A sliding window is a maintained range of consecutive elements within a sequence. Instead of recalculating information for every possible range from scratch, the algorithm updates the current window as its left or right boundary moves.

How it works

Initialize the left and right boundaries of the window.; Expand the right boundary to include new elements.; Update the information maintained for the current window.; If the window violates the required condition, move the left boundary forward.; Record the answer whenever the current window satisfies the problem's requirements.; Continue until every relevant position has been processed.

Key concepts

Contiguous subarrays; Substrings; Window boundaries; Fixed-size windows; Variable-size windows; Window expansion

Types

name: Fixed-Size Window; description: The window always contains a specified number of elements.; examples: Maximum sum of any subarray of size k; Average of consecutive elements; name: Variable-Size Window; description: The window expands or contracts according to a condition.; examples: Longest substring without repeating characters; Smallest subarray with a target sum under suitable input conditions

Time complexity

operation: Fixed-size window traversal; complexity: O(n); operation: Variable-size window traversal; complexity: Often O(n) when each boundary moves only forward

Space complexity

O(1) auxiliary space for a window that maintains only a fixed number of aggregate values. Additional data structures may require more space.

Example

array: 2; 1; windowSize: 3; problem: Find the maximum sum of a consecutive subarray of length 3.; windows: elements: 2; 1; sum: 8; elements: 1; 5; sum: 7; result: maximumSum: 9; subarray: 5; 1

Example or application

Array

  • 2

  • 1

  • 5

  • 1

  • 3

  • 2

Window Size

3

Problem

Find the maximum sum of a consecutive subarray of length 3.

Windows

ElementsSum
  • 2

  • 1

  • 5

8

  • 1

  • 5

  • 1

7

  • 5

  • 1

  • 3

9

  • 1

  • 3

  • 2

6

Result

Maximum Sum

9

Subarray

  • 5

  • 1

  • 3

Definition

A sliding window is a maintained range of consecutive elements within a sequence. Instead of recalculating information for every possible range from scratch, the algorithm updates the current window as its left or right boundary moves.

Types

NameDescriptionExamples

Fixed-Size Window

The window always contains a specified number of elements.

  • Maximum sum of any subarray of size k

  • Average of consecutive elements

  • Maximum value in each fixed-length interval

Variable-Size Window

The window expands or contracts according to a condition.

  • Longest substring without repeating characters

  • Smallest subarray with a target sum under suitable input conditions

  • Longest subarray satisfying a constraint

How It Works

  • Initialize the left and right boundaries of the window.

  • Expand the right boundary to include new elements.

  • Update the information maintained for the current window.

  • If the window violates the required condition, move the left boundary forward.

  • Record the answer whenever the current window satisfies the problem's requirements.

  • Continue until every relevant position has been processed.

Implementation

Language

Pseudocode

Code

  • function maxSumFixedWindow(array, k):

  • windowSum = 0

  • best = negativeInfinity

  • for right from 0 to length(array) - 1:

  • windowSum += array[right]

  • if right >= k - 1:

  • best = max(best, windowSum)

  • windowSum -= array[right - k + 1]

  • return best

Time Complexity

OperationComplexity

Fixed-size window traversal

O(n)

Variable-size window traversal

Often O(n) when each boundary moves only forward

Space Complexity

O(1) auxiliary space for a window that maintains only a fixed number of aggregate values. Additional data structures may require more space.

Key Concepts

  • Contiguous subarrays

  • Substrings

  • Window boundaries

  • Fixed-size windows

  • Variable-size windows

  • Window expansion

  • Window contraction

  • Maintained state

Advantages

  • Avoids recalculating every window from scratch.

  • Can reduce many O(nk) solutions to O(n).

  • Works well for contiguous sequence problems.

  • Can maintain sums, frequencies, counts, and other window information.

Limitations

  • The technique generally applies to contiguous ranges rather than arbitrary subsets.

  • Variable-size window conditions must support safe expansion and contraction.

  • Some sum-based approaches require non-negative values or additional reasoning.

  • Complex window conditions may need frequency maps, deques, or other supporting structures.

Applications

  • Maximum and minimum subarray problems

  • Longest substring without repeating characters

  • Smallest valid subarray

  • Average of consecutive elements

  • Frequency counting in substrings

  • Sliding-window maximum and minimum

Related Topics

  • Two-Pointer Technique

  • Monotonic Queues

  • Deques for Sliding Window Problems

  • Prefix Sums

  • String Algorithms

Practice Questions

QuestionAnswer

What does a sliding window represent?

A continuous range of elements inside an array or string.

What is the difference between fixed-size and variable-size windows?

A fixed-size window has a constant length, while a variable-size window changes according to a condition.

Why can sliding windows reduce repeated computation?

The algorithm updates the current window using the elements entering and leaving it instead of recalculating everything.

What is the typical complexity of a simple sliding-window traversal?

O(n) when each boundary moves forward at most n times.

Learning Objectives

  • Explain the central idea and purpose of sliding window technique.

  • Identify the assumptions, inputs, and conditions relevant to sliding window technique.

  • Evaluate an application of sliding window technique for correctness and practical resource requirements.

Sources and verification

Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.

  • Specialized Algorithms and Computational Topics

Suggest a correction or source · More in Algorithms & Data Structures