Sliding Window

Sliding Window is an array and string technique for maintaining information about a contiguous range while its boundaries move. Instead of recomputing every candidate subarray from scratch, the algorithm updates state when elements enter or leave the active window.

Fixed-Size Window

When every candidate range has exactly k elements, initialize the first window and then slide it by removing the outgoing value and adding the incoming value.

Variable-Size Window

When the window must satisfy a condition, expand the right boundary and shrink the left boundary whenever the maintained state violates or satisfies the required property.

Window State

The maintained state may be a sum, frequency map, distinct count, maximum structure or another aggregate that can be updated incrementally.

When It Applies

Sliding window is primarily associated with contiguous ranges. Subsequence problems that can skip arbitrary elements usually require a different technique.

Worked Examples

Example 1: Maximum Sum of Size K

Update the sum in constant time as one value leaves and one value enters.

Code

public class Main {
    static int maxSum(
        int[] nums,
        int k
    ) {
        int sum = 0;

        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        int best = sum;

        for (int right = k;
             right < nums.length;
             right++) {

            sum += nums[right];
            sum -= nums[right - k];

            best = Math.max(best, sum);
        }

        return best;
    }

    public static void main(String[] args) {
        System.out.println(
            maxSum(
                new int[]{2, 1, 5, 1, 3, 2},
                3
            )
        );
    }
}

Expected Result

Example 2: Minimum Length with Sum at Least Target

For positive numbers, expand until the target is reached and then shrink while preserving feasibility.

Code

public class Main {
    static int minLength(
        int target,
        int[] nums
    ) {
        int left = 0;
        int sum = 0;
        int best = Integer.MAX_VALUE;

        for (int right = 0;
             right < nums.length;
             right++) {

            sum += nums[right];

            while (sum >= target) {
                best =
                    Math.min(
                        best,
                        right - left + 1
                    );

                sum -= nums[left++];
            }
        }

        return best == Integer.MAX_VALUE
            ? 0
            : best;
    }

    public static void main(String[] args) {
        System.out.println(
            minLength(
                7,
                new int[]{2, 3, 1, 2, 4, 3}
            )
        );
    }
}

Expected Result

Example 3: Longest Unique Substring

A frequency set or last-position map allows the left boundary to remove duplicate characters.

Code

import java.util.*;

public class Main {
    static int longest(String s) {
        Set<Character> window =
            new HashSet<>();

        int left = 0;
        int best = 0;

        for (int right = 0;
             right < s.length();
             right++) {

            while (
                window.contains(
                    s.charAt(right)
                )
            ) {
                window.remove(
                    s.charAt(left++)
                );
            }

            window.add(s.charAt(right));

            best =
                Math.max(
                    best,
                    right - left + 1
                );
        }

        return best;
    }

    public static void main(String[] args) {
        System.out.println(
            longest("abcabcbb")
        );
    }
}

Expected Result

Example 4: Window Average

The same fixed-window pattern works for aggregates other than maximum sum.

Code

public class Main {
    public static void main(String[] args) {
        int[] nums = {2, 4, 6, 8};
        int k = 2;
        int sum = 0;

        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

        System.out.println(
            sum / (double) k
        );
    }
}

Expected Result

3.0

Complexity Analysis

Operation	Complexity	Explanation
Fixed window	O(n)	Every incoming and outgoing element is processed a constant number of times.
Variable window	O(n)	Both boundaries move only forward through the input.
Frequency-state space	O(k) or O(alphabet)	Storage depends on values represented inside the active window.

Common Mistakes

Applying sliding window to non-contiguous subsequences.
Assuming a positive-number shrinking rule still works when negative values invalidate monotonicity.
Forgetting to remove outgoing values from window state.
Recomputing the entire aggregate after every boundary movement.

Interview Checklist

Look for contiguous subarray or substring language.
Determine whether window size is fixed or condition-driven.
Define exactly what state enters and leaves with each boundary.
Check whether negative values break a sum-based monotonic window.