Code Templates

The Sliding Window pattern relies on two pointers moving in the same direction to identify a specific subarray or substring. Below are standardized templates for the most common variations.

For a theoretical overview, see the Concept Guide.

The Variable Size Window Template

This is the “classic” sliding window. It expands as much as possible until a condition is met, then shrinks from the left to find the optimal (often minimum) solution. This template directly solves Minimum Size Subarray Sum.

function minSubArrayLen(target, nums) {
    let left = 0;
    let windowSum = 0;
    let result = Infinity;

    for (let right = 0; right < nums.length; right++) {
        // 1. Expand: Include the rightmost element
        windowSum += nums[right];

        // 2. Shrink: While condition is satisfied, try to find a smaller window
        while (windowSum >= target) {
            // Update global minimum/maximum
            result = Math.min(result, right - left + 1);

            // Remove the leftmost element and shift the pointer
            windowSum -= nums[left];
            left++;
        }
    }

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

def minSubArrayLen(target: int, nums: List[int]) -> int:
    left = 0
    window_sum = 0
    result = float('inf')

    for right in range(len(nums)):
        # 1. Expand: Include the rightmost element
        window_sum += nums[right]

        # 2. Shrink: While condition is satisfied, try to find a smaller window
        while window_sum >= target:
            # Update global minimum/maximum
            result = min(result, right - left + 1)

            # Remove the leftmost element and shift the pointer
            window_sum -= nums[left]
            left += 1

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

public int minSubArrayLen(int target, int[] nums) {
    int left = 0;
    int windowSum = 0;
    int result = Integer.MAX_VALUE;

    for (int right = 0; right < nums.length; right++) {
        // 1. Expand: Include the rightmost element
        windowSum += nums[right];

        // 2. Shrink: While condition is satisfied, try to find a smaller window
        while (windowSum >= target) {
            // Update global minimum/maximum
            result = Math.min(result, right - left + 1);

            // Remove the leftmost element and shift the pointer
            windowSum -= nums[left];
            left++;
        }
    }

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

int minSubArrayLen(int target, vector<int>& nums) {
    int left = 0;
    int windowSum = 0;
    int result = INT_MAX;

    for (int right = 0; right < nums.size(); right++) {
        // 1. Expand: Include the rightmost element
        windowSum += nums[right];

        // 2. Shrink: While condition is satisfied, try to find a smaller window
        while (windowSum >= target) {
            // Update global minimum/maximum
            result = min(result, right - left + 1);

            // Remove the leftmost element and shift the pointer
            windowSum -= nums[left];
            left++;
        }
    }

    return result == INT_MAX ? 0 : result;
}

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

    for right := 0; right < len(nums); right++ {
        // 1. Expand: Include the rightmost element
        windowSum += nums[right]

        // 2. Shrink: While condition is satisfied, try to find a smaller window
        for windowSum >= target {
            // Update global minimum/maximum
            length := right - left + 1
            if length < result {
                result = length
            }

            // Remove the leftmost element and shift the pointer
            windowSum -= nums[left]
            left++
        }
    }

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

def min_sub_array_len(target, nums)
  left = 0
  window_sum = 0
  result = Float::INFINITY

  nums.each_with_index do |num, right|
    # 1. Expand: Include the rightmost element
    window_sum += num

    # 2. Shrink: While condition is satisfied, try to find a smaller window
    while window_sum >= target
      # Update global minimum/maximum
      result = [result, right - left + 1].min

      # Remove the leftmost element and shift the pointer
      window_sum -= nums[left]
      left += 1
    end
  end

  result == Float::INFINITY ? 0 : result
end

Code Breakdown

Logic Flow

The template follows a two-pointer state machine logic:

  stateDiagram-v2
    [*] --> Expand: Start
    Expand --> CheckCondition: Increment Right
    CheckCondition --> Expand: Condition Not Met
    CheckCondition --> Shrink: Condition Met
    Shrink --> UpdateResult: Record Window
    UpdateResult --> CheckCondition: Increment Left
    Shrink --> Expand: Condition No Longer Met
    Expand --> [*]: Right reaches End

Key Sections

State Management: windowSum (or a Hash Map) tracks the current content of the window.
Expansion: The right pointer moves every iteration, adding one element to the state.
Contraction: The left pointer moves only when the window is “valid” or “invalid” depending on the problem goal (e.g., sum is large enough).
Result Update: Usually happens right before or right after the left pointer moves.

Variations

Fixed Size Window

Use this when the window size $K$ is constant. This pattern iterates through the array once, adding the next element and removing the element that is now outside the window.

let windowSum = 0;
let maxSum = 0;

for (let i = 0; i < nums.length; i++) {
    windowSum += nums[i]; // Add next element

    if (i >= k - 1) { // Window is full
        maxSum = Math.max(maxSum, windowSum);
        windowSum -= nums[i - (k - 1)]; // Remove oldest element
    }
}

window_sum = 0
max_sum = 0

for i in range(len(nums)):
    window_sum += nums[i] # Add next element

    if i >= k - 1: # Window is full
        max_sum = max(max_sum, window_sum)
        window_sum -= nums[i - (k - 1)] # Remove oldest element

int windowSum = 0;
int maxSum = 0;

for (int i = 0; i < nums.length; i++) {
    windowSum += nums[i]; // Add next element

    if (i >= k - 1) { // Window is full
        maxSum = Math.max(maxSum, windowSum);
        windowSum -= nums[i - (k - 1)]; // Remove oldest element
    }
}

int windowSum = 0;
int maxSum = 0;

for (int i = 0; i < nums.size(); i++) {
    windowSum += nums[i]; // Add next element

    if (i >= k - 1) { // Window is full
        maxSum = max(maxSum, windowSum);
        windowSum -= nums[i - (k - 1)]; // Remove oldest element
    }
}

windowSum := 0
maxSum := 0

for i := 0; i < len(nums); i++ {
    windowSum += nums[i] // Add next element

    if i >= k - 1 { // Window is full
        if windowSum > maxSum {
            maxSum = windowSum
        }
        windowSum -= nums[i-(k-1)] // Remove oldest element
    }
}

window_sum = 0
max_sum = 0

nums.each_with_index do |num, i|
  window_sum += num # Add next element

  if i >= k - 1 # Window is full
    max_sum = [max_sum, window_sum].max
    window_sum -= nums[i - (k - 1)] # Remove oldest element
  end
end

String Frequency Window

Use a Hash Map or Frequency Array to track characters. This is essential for problems involving unique characters or anagrams.

const counts = new Map();

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

    while (/* condition */) {
        const leftChar = s[left];
        counts.set(leftChar, counts.get(leftChar) - 1);
        if (counts.get(leftChar) === 0) counts.delete(leftChar);
        left++;
    }
}

counts = {}

for right in range(len(s)):
    char = s[right]
    counts[char] = counts.get(char, 0) + 1

    while # condition:
        left_char = s[left]
        counts[left_char] -= 1
        if counts[left_char] == 0:
            del counts[left_char]
        left += 1

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

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

    while (/* condition */) {
        char leftChar = s.charAt(left);
        counts.put(leftChar, counts.get(leftChar) - 1);
        if (counts.get(leftChar) == 0) counts.remove(leftChar);
        left++;
    }
}

unordered_map<char, int> counts;

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

    while (/* condition */) {
        counts[s[left]]--;
        if (counts[s[left]] == 0) counts.erase(s[left]);
        left++;
    }
}

counts := make(map[byte]int)

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

    for /* condition */ {
        counts[s[left]]--
        if counts[s[left]] == 0 {
            delete(counts, s[left])
        }
        left++
    }
}

counts = Hash.new(0)

s.each_char.with_index do |char, right|
  counts[char] += 1

  while # condition
    left_char = s[left]
    counts[left_char] -= 1
    counts.delete(left_char) if counts[left_char] == 0
    left += 1
  end
end

Practice

Apply these templates to real-world problems in the Practice Problems section.