Sliding Window Algorithm Explained

Sliding window is an algorithm pattern for processing a contiguous range inside an array, string, or list without recomputing the whole range from scratch each time.

It is common in interview problems, but the same idea appears in backend work whenever code scans recent events, rolling counters, rate-limit windows, logs, metrics, or ordered records.

Quick answer

The sliding window pattern keeps a moving range with a left boundary and a right boundary.

Instead of recalculating a range every time, the algorithm updates the current state as the window moves:

• Add the new item entering the window.
• Remove the old item leaving the window.
• Track the best answer seen so far.

Sliding window problems are often O(n) because each element enters the window once and leaves the window at most once.

Read Big-O Notation Explained for the complexity intuition behind replacing repeated scans with one pass.

When sliding window applies

Sliding window usually applies when the problem is about a contiguous segment.

Look for phrases such as:

• Subarray.
• Substring.
• Consecutive elements.
• At most K.
• No more than K.
• Longest window.
• Minimum length window.
• Fixed-size window.
• Rolling sum or rolling average.

It is less useful when the selected items do not need to be contiguous. For example, “choose any three numbers” is usually not a sliding window problem.

Fixed-size window

A fixed-size window has a known length, such as “maximum sum of any 3 consecutive numbers.”

Naive solution:

For every starting index:
  sum the next k values

That can be O(n * k). Sliding window improves it by keeping the current sum.

Example input:

[4, 2, 1, 7, 8, 1, 2], k = 3

The first window is:

4 + 2 + 1 = 7

Move right by one:

old sum = 7
remove 4
add 7
new sum = 10

Only two updates are needed instead of summing all three values again.

Java fixed-window example

public static int maxSumOfK(int[] nums, int k) {
    if (k <= 0 || k > nums.length) {
        throw new IllegalArgumentException("k must be between 1 and nums.length");
    }

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

    int best = windowSum;

    for (int right = k; right < nums.length; right++) {
        windowSum += nums[right];
        windowSum -= nums[right - k];
        best = Math.max(best, windowSum);
    }

    return best;
}

This runs in O(n) time and O(1) extra space.

Variable-size window

A variable-size window expands and shrinks based on a condition.

Example problem:

Find the longest subarray with sum <= target.

The right pointer expands the window. If the sum becomes too large, the left pointer moves forward until the window is valid again.

public static int longestSubarrayAtMostTarget(int[] nums, int target) {
    int left = 0;
    int sum = 0;
    int best = 0;

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

        while (sum > target && left <= right) {
            sum -= nums[left];
            left++;
        }

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

    return best;
}

This version assumes non-negative numbers. If negative numbers are allowed, increasing the window may reduce the sum and shrinking may increase it, so the simple sliding-window condition can break.

Sliding window vs two pointers

Sliding window is a specialized form of two pointers.

Both patterns often use left and right, but their intent differs:

Pattern	Main idea	Common use
Sliding window	Maintain a contiguous range and update window state	Subarrays, substrings, rolling counts
Two pointers	Move two indexes to search, compare, partition, or converge	Sorted pairs, palindrome checks, partitioning

Read Two Pointers Algorithm Explained when the problem is about pairs, sorted arrays, or moving pointers toward each other rather than maintaining a window.

Common sliding window state

The window state depends on the problem.

Common state includes:

• Sum.
• Count.
• Frequency map.
• Distinct item count.
• Maximum or minimum seen.
• Number of invalid characters.
• Last seen index.

For substring problems, a map is common:

Map<Character, Integer> counts = new HashMap<>();

For simple numeric windows, a single sum may be enough.

Backend-style examples

Sliding window is useful beyond coding interviews.

Backend examples:

• Count requests in the last 60 seconds.
• Track a rolling error rate.
• Compute a moving average over recent latency samples.
• Scan logs for a burst of failures.
• Find the longest valid session activity streak.
• Detect repeated values in a recent event range.

Production rate limiting often needs more careful time-bucket and distributed-system design, but the sliding-window idea helps explain the core range-tracking behavior. Read Rate Limiting in APIs Explained for the API-side design.

Complexity

For a well-formed sliding window, each element is added once and removed at most once.

That gives:

Operation	Complexity
Scan array or string	O(n)
Maintain sum or count	O(1) per move
Frequency map updates	O(1) average per move
Extra space	O(1) to O(k), depending on state

The key improvement is avoiding repeated range work.

Common mistakes

The first mistake is using sliding window when values can be negative and the validity condition depends on the sum. Negative values can break the monotonic behavior that makes the window easy to shrink.

The second mistake is updating the answer before the window is valid. For variable windows, usually shrink first, then record the best valid window.

The third mistake is forgetting to remove state when the left pointer moves. If a character leaves the window, its frequency count must change.

The fourth mistake is mixing inclusive and exclusive boundaries. Be consistent about whether the window length is right - left + 1 or right - left.

The fifth mistake is assuming every two-pointer problem is sliding window. Some pointer problems do not maintain a contiguous state.

Practical recommendation

Use sliding window when the problem asks about a contiguous range and the range can move without rebuilding all state.

Ask three questions:

1. What enters the window?
2. What leaves the window?
3. When is the window valid?

If those answers are clear, the solution is often a single pass.

Related reading

Read Two Pointers Algorithm Explained for the broader pointer pattern and Prefix Sum Algorithm Explained when repeated range sums are easier with preprocessing.

For complexity fundamentals, read Big-O Notation Explained and use the Big-O Cheat Sheet. For the full sequence, browse the Algorithms and Complexity Learning Path and the Topics map.