Solving Fixed- and Variable-Window Problems with Sliding Windows

Good to see you again. In the previous lesson, you used a hash map to retain precisely the history needed for the next lookup—for example, a Two Sum complement or an anagram signature.

Sliding window uses the same economy of state, but the state now describes a contiguous range currently under consideration. Instead of restarting a calculation for every subarray or substring, you update the state as one element enters the range and one element leaves it.

In this lesson, you will distinguish fixed-size from variable-size windows, implement both in Java, justify why the nested-looking variable-window loop is still linear, and recognize the important constraint behind sum-based variable windows.

---

Recognizing a sliding-window problem

A sliding window is a contiguous range of an array or string. If its inclusive boundaries are left and right, the current range is:

$$[left,right]$$

Its length is:

$$right-left+1$$

A sliding window is a strong candidate when the prompt refers to:

• a subarray or substring, which means contiguous elements;
• a maximum, minimum, count, or existence condition over such ranges;
• a state that can be updated efficiently when an item enters or leaves the range.

The distinction between the two major forms is entirely driven by the wording:

Prompt wording	Window type	Typical action
“Exactly k consecutive elements”	Fixed size	Add one incoming element and remove one outgoing element
“Longest substring with…”	Variable size	Expand right; shrink left when invalid
“Shortest subarray whose sum is at least…”	Variable size	Expand until valid; shrink while still valid

The central question is:

What state represents the current window, and can I update it without rescanning the full window?

That state might be a running sum, a frequency map, a set, a deque, or another compact data structure. A window is not inherently a sum technique.

---

Fixed-size windows: reuse the overlap

Consider this prompt:

Given an integer array and an integer k, return the maximum sum of any contiguous subarray of exactly k elements.

For nums = [4, 2, 1, 7, 8, 1, 2] and k = 3, the candidate windows are:

• [4, 2, 1], sum $7$
• [2, 1, 7], sum $10$
• [1, 7, 8], sum $16$
• [7, 8, 1], sum $16$
• [8, 1, 2], sum $11$

A brute-force approach calculates each sum from scratch. There are $n-k+1$ windows and each sum takes $O(k)$, so it costs:

$$O((n-k+1)\cdot k)$$

Adjacent windows overlap in $k-1$ positions. Recomputing that overlap is the waste we remove.

When the first window [4, 2, 1] becomes [2, 1, 7], only two facts change:

1. 4 is no longer part of the window.
2. 7 has become part of the window.

So the update is:

$$\text{new window sum}=\text{old window sum}-\text{outgoing value}+\text{incoming value}$$

The window’s contents remain correct without summing all three values again.

Java implementation

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

    long windowSum = 0;

    // Build the initial window: indices [0, k - 1].
    for (int i = 0; i < k; i++) {
        windowSum += nums[i];
    }

    long maxSum = windowSum;

    // Each iteration adds nums[right] and removes nums[right - k].
    for (int right = k; right < nums.length; right++) {
        windowSum += nums[right];
        windowSum -= nums[right - k];

        maxSum = Math.max(maxSum, windowSum);
    }

    return maxSum;
}

This implementation deliberately initializes maxSum from the first valid window rather than 0. That matters when all values are negative:

maxSumFixedWindow(new int[] {-8, -3, -6, -2}, 2); // returns -9

Initializing the answer to 0 would incorrectly return a sum that no valid window has.

Fixed-window invariant and complexity

After processing a given right index in the second loop:

windowSum equals the sum of the exactly k elements ending at right.

The code maintains that invariant by adding the element at right and removing the element exactly k positions behind it.

Each element participates in a constant number of operations. Therefore:

• Time: $O(n)$
• Auxiliary space: $O(1)$

This form works even when array values are negative, because the window size is fixed. The algorithm never makes a decision based on whether a sum will rise or fall in the future.

---

Variable-size windows: maintain validity, not a preset length

A variable-size window does not know its final length in advance. Instead, the window’s boundaries respond to a condition.

Consider:

Given an array of non-negative integers and a positive target, find the length of the shortest contiguous subarray whose sum is at least the target.

For:

nums   = [2, 3, 1, 2, 4, 3]
target = 7

The answer is 2, from [4, 3].

The strategy is different from fixed size:

• Expand the right boundary until the window is valid.
• Once valid, record it.
• Then shrink from the left as long as the window remains valid, because the objective is to find the shortest valid range.

At the point shown in the image, [2, 3, 1, 2] has sum $8$, so it is valid. But length four may not be minimal.

1. Record length $4$.
2. Remove the leftmost 2; the sum becomes $6$.
3. The window is now invalid, so resume expansion.
4. Later, [2, 4, 3] has sum $9$, which is valid.
5. Remove 2; [4, 3] still has sum $7$, so record length $2$.
6. Remove 4; the remaining sum is $3$, so this final contraction is no longer valid.

The key detail is that a minimum-window solution updates its answer before removing the leftmost element. It is inspecting the valid window that exists now, then asking whether an even smaller valid one is possible.

Java implementation: shortest sum at least target

public static int minSubarrayLengthAtLeastTarget(int target, int[] nums) {
    if (target <= 0) {
        throw new IllegalArgumentException("target must be positive");
    }

    int left = 0;
    long windowSum = 0;
    int bestLength = Integer.MAX_VALUE;

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

        // The current window is valid. Try to make it smaller.
        while (windowSum >= target) {
            bestLength = Math.min(bestLength, right - left + 1);

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

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

The result 0 means that no qualifying subarray exists. In an interview, state that return contract explicitly; some platforms instead expect -1.

Why is this $O(n)$ despite the nested loop?

At first glance, a for loop containing a while loop can look quadratic. Here it is not.

• right moves from left to right at most $n$ times.
• left also moves from left to right at most $n$ times.
• No pointer moves backward.

Therefore, the total number of boundary movements is at most $2n$, which simplifies to:

$$O(n)$$

The extra space is $O(1)$, since the implementation keeps only indices, a sum, and the best answer.

---

The non-negative constraint is not optional

For the sum-based variable-window technique, the array must contain non-negative values. This is not a minor implementation detail; it is why shrinking or expanding provides useful information.

With non-negative values:

• Expanding the window cannot decrease the sum.
• Shrinking the window cannot increase the sum.

That monotonic behavior makes the decisions sound:

• If the sum is too small, expanding is the only useful direction.
• If the sum meets the target, shrinking is the only way to discover a shorter valid window.

With negative values, those claims fail. For example:

nums   = [1, -1, 3]
target = 3

A simple variable sum window reaches [1, -1, 3] with sum $3$. If it removes 1, the sum becomes $2$, so it would stop shrinking. Yet removing -1 afterward would produce [3], also with sum $3$, and that is the true shortest window.

For arbitrary positive and negative integers, do not apply this variable sum template blindly. Prefix sums combined with a hash-based strategy are often the appropriate direction; you will study that pattern in the next lesson.

---

Variable windows with hash-based state

The current window need not be summarized by a sum. A very common interview problem is:

Return the length of the longest substring with no repeated characters.

For this task, maintain a frequency map for characters in the current substring.

The invariant is:

Before each expansion, the active window contains no duplicate characters.

When a new character enters, it may violate that invariant. Shrink from the left until the incoming character’s frequency returns to one.

import java.util.HashMap;
import java.util.Map;

public static int longestUniqueSubstring(String s) {
    Map<Character, Integer> frequency = new HashMap<>();

    int left = 0;
    int bestLength = 0;

    for (int right = 0; right < s.length(); right++) {
        char incoming = s.charAt(right);
        frequency.merge(incoming, 1, Integer::sum);

        // Before adding incoming, the window had unique characters.
        // Therefore, only incoming can have caused the violation.
        while (frequency.get(incoming) > 1) {
            char outgoing = s.charAt(left);
            frequency.put(outgoing, frequency.get(outgoing) - 1);
            left++;
        }

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

    return bestLength;
}

This is the bridge between the previous lesson and this one:

• The hash map represents current window state.
• The left and right pointers ensure it represents only a contiguous range.
• The while loop restores the window invariant after a violation.

Assuming ordinary expected constant-time HashMap operations:

• Time: expected $O(n)$
• Space: $O(\min (n,a))$, where $a$ is the number of distinct characters that can appear.

Leaving characters with frequency zero in the map is correct here because the code checks frequencies rather than map size. Removing zero-count entries is also valid, but it is not necessary for correctness.

---

Choose the update order from the objective

A frequent interview mistake is memorizing one sliding-window template and applying it mechanically. The order in which you update the answer depends on the objective.

Objective	Validity rule	When to update answer
Maximum sum of exactly k values	Window length is exactly k	Evaluate every completed fixed-size window
Longest window satisfying a constraint	Window must be valid	Restore validity, then update maximum length
Shortest window satisfying a constraint	Window is currently valid	Update minimum length, then shrink further
Count windows matching a condition	Depends on the problem	Often requires a specialized counting argument

For a longest valid window, restoring validity first is necessary because an invalid range cannot be an answer.

For a shortest valid window, record the answer before shrinking because the current valid window itself may be the best candidate.

---

A concise interview explanation

For a fixed-window maximum-sum problem, a clear explanation is:

“Because the prompt asks for exactly k consecutive elements, I use a fixed sliding window. I compute the first window sum once. Each subsequent window removes one outgoing value and adds one incoming value, so each shift is constant time. The total complexity is $O(n)$ time and $O(1)$ auxiliary space.”

For a variable minimum-length sum problem, include the key assumption:

“Because values are non-negative, the window sum changes monotonically: expanding cannot reduce it and shrinking cannot increase it. I expand until the sum reaches the target, then repeatedly shrink while it remains valid, recording the shortest valid range. Both pointers move forward at most n times, so runtime is $O(n)$.”

That explanation demonstrates more than familiarity with a pattern: it establishes why the technique is correct under the prompt’s constraints.

---

Key takeaways

• Sliding windows apply to contiguous subarrays and substrings.
• A fixed-size window has a known length. Update its state by removing the outgoing item and adding the incoming item.
• A variable-size window adjusts its left boundary to restore or exploit a validity condition.
• The apparent nested loop in a variable window is usually still $O(n)$, because each pointer moves forward at most $n$ times.
• For shortest valid windows, update the answer while the current window is valid, then try shrinking.
• For longest valid windows, shrink until valid first, then update the answer.
• Sum-based variable windows require non-negative values unless the problem provides another monotonic guarantee.
• Hash maps and sliding windows combine naturally for substring conditions such as uniqueness or bounded distinct-character counts.

Next, you will work with another pointer-based pattern: solving sorted-array problems using opposing or same-direction two pointers.