Skip to content

Sliding window [mp]

Micro pattern

Description

Maintain a contiguous interval while moving its boundaries monotonically and preserving a validity condition.

Problems

Last-seen jump

Move the left boundary past the last occurrence of a repeated value.

Frequency-constrained window

Shrink the left boundary as counts change to find a valid or optimal interval.

Fixed-size window

Expire indices outside a fixed-width interval while retaining its best candidate.