Menu

Earn Premium with Referrals

Invite your friends and earn Premium rewards through our referral program.

See how it works and start inviting friends.

Sliding Window
DSA

Sliding Window

Learn how to efficiently solve contiguous subarray and substring problems using fixed and variable-size windows.

Sliding Window solves problems on contiguous subarrays by maintaining a window instead of recomputing it.

Its core idea:

Add the incoming element, remove the outgoing one — each element enters and leaves the window once.

Focus on recognizing:

Exactly K → Fixed window · Longest/shortest + condition → Variable window

Quick Recognition Cheat Sheet

If you see…Think…Main Idea
Exactly K elementsFixed WindowAdd incoming, remove outgoing
Maximum/minimum of size KFixed WindowKeep window size K
Longest subarray satisfying conditionVariable WindowExpand, then shrink if needed
Shortest subarray satisfying conditionVariable WindowExpand, shrink aggressively

1. Fixed-Size Window

The window always contains exactly K elements.

Core Idea

Add incoming element
Remove outgoing element
Update result

Longest Substring Without Repeating Characters

Grow a window with the right pointer; whenever a duplicate enters, jump the left pointer just past the previous copy. The window always holds distinct characters, and its max size is the answer.

String 'abcabcbb'. ▼L/▼R carets and the highlighted range ARE the window. As R advances, 'a' appears again at right=3 so L jumps past the old 'a' (window 'bca'). Repeat: max window length = 3 ('abc'). The window never holds a repeat — that's the whole invariant.

ARRAY VISUALIZER
Steps –
a
0
b
1
c
2
a
3
b
4
c
5
b
6
b
7
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        left = 0
                      
                        2
                        for right from 0 to n-1:
                      
                        3
                          if s[right] is already in window:
                      
                        4
                            left = move past the old copy
                      
                        5
                          add s[right] to window
                      
                        6
                          best = longest window so far
                      
                        7
                        return best
                      
public int maxSumFixed(int[] nums, int k) {
    int sum = 0;

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

    int max = sum;

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

    return max;
}
def max_sum_fixed(nums, k):
    window = sum(nums[:k])
    best = window

    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)

    return best
int maxSumFixed(vector<int>& nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i];

    int best = sum;

    for (int i = k; i < (int)nums.size(); i++) {
        sum += nums[i] - nums[i - k];
        best = max(best, sum);
    }

    return best;
}
function maxSumFixed(nums, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];

  let max = sum;

  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k];
    max = Math.max(max, sum);
  }

  return max;
}

Fixed K = Add incoming − Remove outgoing.

2. Variable-Size Window

The window size changes depending on a condition.

Core Idea

Expand right
    ↓
Check condition
    ↓
If invalid → shrink left
    ↓
Update answer

Minimum Window Substring (Contains All of T)

Given S = "ADOBECODEBANC" and T = "ABC", find the shortest substring of S that contains at least one A, one B, and one C. The expected answer is "BANC", which has length 4.

Use a sliding window [left, right] and frequency counts for the target characters A, B, and C. For S = "ADOBECODEBANC" and T = "ABC", expand right until the window contains all three required characters. At right = 5, the window "ADOBEC" becomes valid with matched = 3. Save it, then shrink from the left one character at a time while it remains valid. Removing A makes the window invalid, so stop. Continue expanding. At right = 12, the window "ODEBANC" is valid again. Shrink it: removing O gives "DEBANC", removing D gives "EBANC", removing E gives "BANC", which is still valid and has length 4. Removing B would make the window invalid because no B remains, so stop. Therefore the minimum window is "BANC".

ARRAY VISUALIZER
Steps –
A
0
D
1
O
2
B
3
E
4
C
5
O
6
D
7
E
8
B
9
A
10
N
11
C
12
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode

                        1
                        left = 0, matched = 0
                      
                        2
                        for right from 0 to n-1:
                      
                        3
                          add s[right] to window
                      
                        4
                          if count matches target: matched = matched + 1
                      
                        5
                          while all chars of t are matched:
                      
                        6
                            if window is smaller than best: save it
                      
                        7
                            remove s[left] from window
                      
                        8
                            if removing breaks a match: matched = matched - 1
                      
                        9
                            left = left + 1
                      
                        10
                        return saved window
                      
public int longestSubarray(int[] nums, int k) {
    int left = 0;
    int sum = 0;
    int result = 0;

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

        while (sum > k) {
            sum -= nums[left];
            left++;
        }

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

    return result;
}
def longest_subarray(nums, k):
    left = 0
    window = 0
    best = 0

    for right in range(len(nums)):
        window += nums[right]

        while window > k:
            window -= nums[left]
            left += 1

        best = max(best, right - left + 1)

    return best
int longestSubarray(vector<int>& nums, int k) {
    int left = 0, sum = 0, best = 0;

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

        while (sum > k) {
            sum -= nums[left];
            left++;
        }

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

    return best;
}
function longestSubarray(nums, k) {
  let left = 0,
    sum = 0,
    result = 0;

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

    while (sum > k) {
      sum -= nums[left];
      left++;
    }

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

  return result;
}

Watch the variable window grow over [1,2,3,4,5] until sum ≤ 8 breaks, shrink back to valid, and finish with best length 3. Press ▶ to animate.

3. Longest vs Shortest

The most important distinction:

Longest

Shrink only until the window becomes valid — update after shrinking.

while (condition is invalid) { shrink(); }
result = max(result, windowSize);

Shortest

Once valid, keep shrinking while it stays valid — update during shrinking.

while (condition is valid) {
    result = min(result, windowSize);
    shrink();
}

Longest → update after shrinking. Shortest → update during shrinking.

Common Mistakes

Confusing fixed and variable windows.

Exactly K → Fixed. Longest/shortest satisfying a condition → Variable.

Using if instead of while.

One removal may not restore validity — shrink in a loop.

Off-by-one on window length.

Length is always right - left + 1.

Complexity

PatternTime
Fixed windowO(n)
Variable windowO(n) — each index enters and leaves once

My Private Notes

Notes are auto-saved locally to this device.