Problems

Master the sliding window pattern by solving these carefully selected problems. We’ve organized them to take you from basic fixed-size windows to complex variable-size problems with frequency tracking.

For a theoretical overview, check out the Concept Guide or the Code Templates.

Easy Problems

1. Maximum Average Subarray I

LeetCode 643

Brief: Find the contiguous subarray of size k that has the maximum average value.
Why this pattern?: Since the window size k is fixed, we can efficiently update the sum in
O(1)
by sliding the window one element at a time.
Key Insight: Instead of recalculating the average, just track the maximum sum.

Visual:

  graph LR
    subgraph Array
    A[1] --- B[12] --- C[-5] --- D[-6] --- E[50] --- F[3]
    end
    subgraph Window_Size_4
    A --- B --- C --- D
    end
    style Window_Size_4 fill:#f9d,stroke:#333

var findMaxAverage = function(nums, k) {
    let sum = 0;
    for (let i = 0; i < k; i++) {
        sum += nums[i];
    }

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

    return maxSum / k;
};

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        curr_sum = sum(nums[:k])
        max_sum = curr_sum

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

        return max_sum / k

class Solution {
    public double findMaxAverage(int[] nums, int k) {
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

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

        return maxSum / k;
    }
}

class Solution {
public:
    double findMaxAverage(vector<int>& nums, int k) {
        double sum = 0;
        for (int i = 0; i < k; i++) {
            sum += nums[i];
        }

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

        return max_sum / k;
    }
};

func findMaxAverage(nums []int, k int) float64 {
    sum := 0
    for i := 0; i < k; i++ {
        sum += nums[i]
    }

    maxSum := sum
    for i := k; i < len(nums); i++ {
        sum = sum - nums[i-k] + nums[i]
        if sum > maxSum {
            maxSum = sum
        }
    }

    return float64(maxSum) / float64(k)
}

def find_max_average(nums, k)
  curr_sum = nums[0...k].sum
  max_sum = curr_sum

  (k...nums.length).each do |i|
    curr_sum = curr_sum - nums[i - k] + nums[i]
    max_sum = [max_sum, curr_sum].max
  end

  max_sum.to_f / k
end

Medium Problems

2. Minimum Size Subarray Sum

LeetCode 209

Brief: Find the minimal length of a contiguous subarray of which the sum is ≥ target.
Why this pattern?: We use a variable-size window that expands to find a valid sum and then aggressively shrinks to find the shortest version of that window.
Key Insight: The window sum only increases when moving right and decreases when moving left.

Visual:

  graph TD
    S1[Expand Right: 2, 3, 1, 2] -->|Sum=8| S2[Shrink Left: 3, 1, 2]
    S2 -->|Sum=6| S3[Expand Right: 3, 1, 2, 4]
    S3 -->|Sum=10| S4[Shrink Left: 1, 2, 4]
    style S4 fill:#aaf,stroke:#333

var minSubArrayLen = function(target, nums) {
    let left = 0;
    let sum = 0;
    let minLen = Infinity;

    for (let right = 0; right < nums.length; right++) {
        sum += nums[right];
        while (sum >= target) {
            minLen = Math.min(minLen, right - left + 1);
            sum -= nums[left];
            left++;
        }
    }

    return minLen === Infinity ? 0 : minLen;
};

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left = 0
        curr_sum = 0
        min_len = float('inf')

        for right in range(len(nums)):
            curr_sum += nums[right]
            while curr_sum >= target:
                min_len = min(min_len, right - left + 1)
                curr_sum -= nums[left]
                left += 1

        return 0 if min_len == float('inf') else min_len

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int sum = 0;
        int minLen = Integer.MAX_VALUE;

        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

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

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0;
        int sum = 0;
        int min_len = INT_MAX;

        for (int right = 0; right < nums.size(); right++) {
            sum += nums[right];
            while (sum >= target) {
                min_len = min(min_len, right - left + 1);
                sum -= nums[left];
                left++;
            }
        }

        return min_len == INT_MAX ? 0 : min_len;
    }
};

func minSubArrayLen(target int, nums []int) int {
    left := 0
    sum := 0
    minLen := math.MaxInt32

    for right := 0; right < len(nums); right++ {
        sum += nums[right]
        for sum >= target {
            length := right - left + 1
            if length < minLen {
                minLen = length
            }
            sum -= nums[left]
            left++
        }
    }

    if minLen == math.MaxInt32 {
        return 0
    }
    return minLen
}

def min_sub_array_len(target, nums)
  left = 0
  sum = 0
  min_len = Float::INFINITY

  nums.each_with_index do |num, right|
    sum += num
    while sum >= target
      min_len = [min_len, right - left + 1].min
      sum -= nums[left]
      left += 1
    end
  end

  min_len == Float::INFINITY ? 0 : min_len
end

3. Longest Substring Without Repeating Characters

LeetCode 3

Brief: Find the length of the longest substring without repeating characters.
Why this pattern?: We use a sliding window to track unique characters. When a duplicate is found, the window “jumps” past the previous occurrence.
Key Insight: Instead of moving left one by one, use a Map to store indices and move left to last_pos + 1.

Visual:

  graph LR
    A[abcabcbb] -->|Right=3| B[bca]
    B -->|Right=4| C[cab]
    style C fill:#f9d,stroke:#333

var lengthOfLongestSubstring = function(s) {
    let left = 0;
    let maxLen = 0;
    const charMap = new Map();

    for (let right = 0; right < s.length; right++) {
        if (charMap.has(s[right])) {
            left = Math.max(left, charMap.get(s[right]) + 1);
        }
        charMap.set(s[right], right);
        maxLen = Math.max(maxLen, right - left + 1);
    }

    return maxLen;
};

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        char_map = {}
        left = 0
        max_len = 0

        for right, char in enumerate(s):
            if char in char_map:
                left = max(left, char_map[char] + 1)
            char_map[char] = right
            max_len = max(max_len, right - left + 1)

        return max_len

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> charMap = new HashMap<>();
        int left = 0;
        int maxLen = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            if (charMap.containsKey(c)) {
                left = Math.max(left, charMap.get(c) + 1);
            }
            charMap.put(c, right);
            maxLen = Math.max(maxLen, right - left + 1);
        }

        return maxLen;
    }
}

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char, int> char_map;
        int left = 0;
        int max_len = 0;

        for (int right = 0; right < s.length(); right++) {
            if (char_map.count(s[right])) {
                left = max(left, char_map[s[right]] + 1);
            }
            char_map[s[right]] = right;
            max_len = max(max_len, right - left + 1);
        }

        return max_len;
    }
};

func lengthOfLongestSubstring(s string) int {
    charMap := make(map[byte]int)
    left := 0
    maxLen := 0

    for right := 0; right < len(s); right++ {
        if pos, ok := charMap[s[right]]; ok {
            if pos + 1 > left {
                left = pos + 1
            }
        }
        charMap[s[right]] = right
        if right - left + 1 > maxLen {
            maxLen = right - left + 1
        }
    }

    return maxLen
}

def length_of_longest_substring(s)
  char_map = {}
  left = 0
  max_len = 0

  s.each_char.with_index do |char, right|
    if char_map.key?(char)
      left = [left, char_map[char] + 1].max
    end
    char_map[char] = right
    max_len = [max_len, right - left + 1].max
  end

  max_len
end

Hard Problems

4. Minimum Window Substring

LeetCode 76

Brief: Given two strings s and t, return the minimum window in s which will contain all the characters in t.
Why this pattern?: This is the ultimate sliding window challenge. It requires tracking two frequency maps and a “formed” counter to know when a window is valid.
Key Insight: Only shrink when the window contains all required characters.

Visual:

  graph TD
    T[Target: ABC] --- S[Source: ADOBECODEBANC]
    W1[Valid Window: ADOBEC] --> W2[Valid Window: BECODEBA]
    W2 --> W3[Smallest Window: BANC]
    style W3 fill:#f9d,stroke:#333

var minWindow = function(s, t) {
    if (t.length > s.length) return "";

    const targetMap = new Map();
    for (let char of t) targetMap.set(char, (targetMap.get(char) || 0) + 1);

    const windowMap = new Map();
    let left = 0, formed = 0;
    let required = targetMap.size;
    let ans = [-1, 0, 0]; // length, left, right

    for (let right = 0; right < s.length; right++) {
        let char = s[right];
        windowMap.set(char, (windowMap.get(char) || 0) + 1);

        if (targetMap.has(char) && windowMap.get(char) === targetMap.get(char)) {
            formed++;
        }

        while (left <= right && formed === required) {
            char = s[left];
            if (ans[0] === -1 || right - left + 1 < ans[0]) {
                ans = [right - left + 1, left, right];
            }

            windowMap.set(char, windowMap.get(char) - 1);
            if (targetMap.has(char) && windowMap.get(char) < targetMap.get(char)) {
                formed--;
            }
            left++;
        }
    }

    return ans[0] === -1 ? "" : s.substring(ans[1], ans[2] + 1);
};

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not t or not s: return ""

        target_counts = Counter(t)
        required = len(target_counts)

        left = 0
        formed = 0
        window_counts = {}
        ans = float("inf"), None, None

        for right, char in enumerate(s):
            window_counts[char] = window_counts.get(char, 0) + 1
            if char in target_counts and window_counts[char] == target_counts[char]:
                formed += 1

            while left <= right and formed == required:
                char = s[left]
                if right - left + 1 < ans[0]:
                    ans = (right - left + 1, left, right)

                window_counts[char] -= 1
                if char in target_counts and window_counts[char] < target_counts[char]:
                    formed -= 1
                left += 1

        return "" if ans[0] == float("inf") else s[ans[1] : ans[2] + 1]

class Solution {
    public String minWindow(String s, String t) {
        if (s.length() < t.length()) return "";

        Map<Character, Integer> target = new HashMap<>();
        for (char c : t.toCharArray()) target.put(c, target.getOrDefault(c, 0) + 1);

        Map<Character, Integer> window = new HashMap<>();
        int left = 0, formed = 0, required = target.size();
        int minLen = Integer.MAX_VALUE, start = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s.charAt(right);
            window.put(c, window.getOrDefault(c, 0) + 1);

            if (target.containsKey(c) && window.get(c).intValue() == target.get(c).intValue()) {
                formed++;
            }

            while (left <= right && formed == required) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    start = left;
                }

                char leftChar = s.charAt(left);
                window.put(leftChar, window.get(leftChar) - 1);
                if (target.containsKey(leftChar) && window.get(leftChar) < target.get(leftChar)) {
                    formed--;
                }
                left++;
            }
        }

        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
    }
}

class Solution {
public:
    string minWindow(string s, string t) {
        if (s.length() < t.length()) return "";

        unordered_map<char, int> target;
        for (char c : t) target[c]++;

        unordered_map<char, int> window;
        int left = 0, formed = 0, required = target.size();
        int min_len = INT_MAX, start = 0;

        for (int right = 0; right < s.length(); right++) {
            char c = s[right];
            window[c]++;

            if (target.count(c) && window[c] == target[c]) {
                formed++;
            }

            while (left <= right && formed == required) {
                if (right - left + 1 < min_len) {
                    min_len = right - left + 1;
                    start = left;
                }

                char left_char = s[left];
                window[left_char]--;
                if (target.count(left_char) && window[left_char] < target[left_char]) {
                    formed--;
                }
                left++;
            }
        }

        return min_len == INT_MAX ? "" : s.substr(start, min_len);
    }
};

func minWindow(s string, t string) string {
    if len(s) < len(t) {
        return ""
    }

    target := make(map[byte]int)
    for i := 0; i < len(t); i++ {
        target[t[i]]++
    }

    window := make(map[byte]int)
    left, formed, required := 0, 0, len(target)
    minLen, start := math.MaxInt32, 0

    for right := 0; right < len(s); right++ {
        c := s[right]
        window[c]++

        if count, ok := target[c]; ok && window[c] == count {
            formed++
        }

        for left <= right && formed == required {
            if right - left + 1 < minLen {
                minLen = right - left + 1
                start = left
            }

            leftChar := s[left]
            window[leftChar]--
            if count, ok := target[leftChar]; ok && window[leftChar] < count {
                formed--
            }
            left++
        }
    }

    if minLen == math.MaxInt32 {
        return ""
    }
    return s[start : start+minLen]
}

def min_window(s, t)
  return "" if s.length < t.length

  target_counts = Hash.new(0)
  t.each_char { |c| target_counts[c] += 1 }

  window_counts = Hash.new(0)
  left = 0
  formed = 0
  required = target_counts.size
  min_len = Float::INFINITY
  ans = [0, 0]

  s.each_char.with_index do |char, right|
    window_counts[char] += 1
    if target_counts.key?(char) && window_counts[char] == target_counts[char]
      formed += 1
    end

    while left <= right && formed == required
      if right - left + 1 < min_len
        min_len = right - left + 1
        ans = [left, min_len]
      end

      left_char = s[left]
      window_counts[left_char] -= 1
      if target_counts.key?(left_char) && window_counts[left_char] < target_counts[left_char]
        formed -= 1
      end
      left += 1
    end
  end

  min_len == Float::INFINITY ? "" : s[ans[0], ans[1]]
end

Recommended Study Order

Fixed Window Basics: Start with Maximum Average Subarray I to understand simple window sliding.
Variable Window Core: Move to Minimum Size Subarray Sum. This is the most common interview variation.
Hash Map Integration: Tackle Longest Substring Without Repeating Characters to learn how to use auxiliary data structures with windows.
Advanced State Tracking: Finalize your knowledge with Minimum Window Substring. If you can solve this, you can solve almost any sliding window problem.

Pro Tip: Whenever you see “contiguous subarray” and a constraint (sum, number of unique elements), Sliding Window is almost always the

O(N)

solution you're looking for.