Overview & Concept

The Sliding Window Technique maintains an active contiguous subsegment [left..right] that dynamically expands and contracts to search for target sums, maximum metrics, or substring properties in amortized O(n) linear time.

How It Works

Right Boundary Expansion: Iterates right pointer from 0 to n-1, adding new elements into running window state.

Left Boundary Contraction: When window sum exceeds target or violates constraints, advances left pointer to shrink window.

Running State Maintenance: Updates state incrementally (add incoming element, subtract outgoing element) in O(1).

Amortized O(n) Efficiency: Both pointers move strictly forward, yielding 2n operations total.

Step-by-Step Execution

1. Initialize WindowSet left = 0, currentSum = 0.

2. Expand RightAdd arr[right] to currentSum.

3. Contract LeftWhile currentSum > target and left < right, subtract arr[left] and increment left.

4. Check TargetIf currentSum == target, return window range [left..right].

Asymptotic Complexity Analysis

Metric	Best Case	Average Case	Worst Case	Space Complexity
Complexity Bound	O(1)	O(n)	O(n)	O(1)
Explanation	Optimal input arrangement minimizing operations.	Expected time for uniformly distributed randomized inputs.	Adversarial degenerate conditions requiring full traversal.	Auxiliary memory allocated beyond original input size.

Pseudocode & Invariants

Algorithm Logic

procedure slidingWindowSearch(A, target):
  left = 0, currentSum = 0
  for right = 0 to length(A) - 1:
    currentSum = currentSum + A[right]
    while currentSum > target and left < right:
      currentSum = currentSum - A[left]
      left = left + 1
    if currentSum == target: return [left, right]
  return [-1, -1]

Algorithmic Invariants

Contiguity Invariant: Active window [left..right] always represents an uninterrupted subsegment.

Correctness Guarantee: Invariants hold true prior to loop entry, are preserved during every iteration, and guarantee correct post-condition upon termination.

Advantages & Disadvantages

Key Advantages

•Converts brute-force O(n²) nested loop searches into single-pass O(n) algorithms.
•O(1) extra memory overhead.

Trade-offs & Limitations

•Variable-size window expansion/contraction requires positive numbers for monotonic sum behavior.

Real-World Applications

Network Congestion & Rate Limiting

Sliding window protocol regulating TCP packet throughput.

Financial Moving Averages

Computing rolling metrics and volume thresholds over real-time tick data.

Decision Guide: When to Use

Ideal Scenarios

✓When searching for contiguous subarrays or substrings with target constraints.

Consider Alternatives When

✕When searching non-contiguous subsequences or when negative numbers break monotonicity.

Compare trade-offs and complexity across complementary tools in AlgoViz.

Two Pointers Search Sublist Search