L1: Introduction to Sliding Window and Two Pointers | Templates | Patterns

Welcome to the foundational masterclass on the Two Pointers and Sliding Window algorithmic pattern. Unlike rigid dynamic programming recipes or binary search boilerplate, two pointers and sliding window techniques are constructive algorithmic frameworks. You must understand the underlying mental models, master the reusable templates, and mold them dynamically to fit diverse interview constraints.

1. Why Do We Need Sliding Window and Two Pointers?

When dealing with arrays or strings, brute-force solutions often require examining every possible contiguous subsegment (subarray or substring). For an array of size $N$, the total number of subarrays is $\frac{N(N+1)}{2}$, resulting in an inefficient $\mathcal{O}(N^2)$ or $\mathcal{O}(N^3)$ time complexity.

The Sliding Window and Two Pointers techniques allow us to process contiguous segments in linear time ($\mathcal{O}(N)$ or $\mathcal{O}(2N)$) by maintaining a dynamic window bounded by two indices (L and R) instead of recomputing values from scratch for every new subsegment.

2. Core Mental Model: The Window and Its Boundaries

Think of a sliding window as a flexible inspection frame placed over a contiguous section of an array:

• Left Pointer (L): Marks the beginning (leftmost edge) of the current window.
• Right Pointer (R): Marks the end (rightmost edge) of the current window.
• Expansion vs. Shrinking:
  • Expansion is typically driven by moving R to the right (r++), incorporating new elements into the window.
  • Shrinking is typically driven by moving L to the right (l++), discarding elements from the left when the window violates a problem condition.

Array: [ 2,  5,  1,  7,  10 ]
         ^        ^
         |        |
         L        R
    (Window of size 4, sum = 15)

3. The Four Core Problem Patterns

Interview problems involving two pointers and sliding windows generally fall into four distinct categories:

4. Pattern 1: Constant Window (Fixed Size $K$)

The Problem Setup

Given an array of positive and negative integers and an integer $K$, find the maximum sum obtainable by picking $K$ consecutive elements.

Algorithmic Mechanics

1. Initialize L = 0 and R = K - 1.
2. Compute the initial sum for the first window from index 0 to K - 1 using a simple loop.
3. Slide the window forward by incrementing both L and R:
   • Subtract arr[L] from the running sum.
   • Increment l++.
   • Increment r++.
   • Add the new arr[R] to the running sum.
4. Track the maximum sum encountered across all window shifts.

Constant Window Code Template

int maxScore(vector<int>& arr, int k) {
    int n = arr.size();
    int l = 0, r = k - 1;
    int sum = 0;
    
    // 1. Compute initial window sum
    for (int i = l; i <= r; i++) {
        sum += arr[i];
    }
    int maxSum = sum;
    
    // 2. Slide the window
    while (r < n - 1) {
        sum -= arr[l];
        l++;
        r++;
        sum += arr[r];
        maxSum = max(maxSum, sum);
    }
    return maxSum;
}

5. Pattern 2: Longest Subarray / Substring (Variable Size)

Problem Setup

Find the length of the longest subarray where the sum is less than or equal to $K$ (sum <= K).

Evolution 1: The Brute Force Approach

Generate every possible subarray, compute its sum, and check the condition.

// Brute Force: Generate all subarrays
int maxLen = 0;
int n = arr.size();
for (int i = 0; i < n; i++) {
    int sum = 0;
    for (int j = i; j < n; j++) {
        sum += arr[j];
        if (sum <= k) {
            maxLen = max(maxLen, j - i + 1);
        } else {
            break; // Optimization: Exceeds K, stop inner loop
        }
    }
}

• Time Complexity: $\mathcal{O}(N^2)$
• Space Complexity: $\mathcal{O}(1)$

Evolution 2: Better Approach (Two Pointers & Sliding Window with while loop)

Instead of recomputing sums from scratch, maintain a sliding window [L, R]. Expand R to add elements. If the sum exceeds $K$ (violating the condition), shrink from the left (L) until the window becomes valid again.

// Better Approach: O(2N) Sliding Window with while loop shrinking
int left = 0, right = 0, sum = 0, maxLen = 0;
int n = arr.size();

while (right < n) {
    sum += arr[right]; // Expand window
    
    // If window is invalid, shrink from the left until valid
    while (sum > k) {
        sum -= arr[left];
        left++;
    }
    
    // When valid, update max length
    if (sum <= k) {
        maxLen = max(maxLen, right - left + 1);
    }
    
    right++;
}

• Time Complexity: $\mathcal{O}(2N)$ because R traverses $N$ elements and L at most traverses $N$ elements across the entire execution.
• Space Complexity: $\mathcal{O}(1)$

Evolution 3: Optimal Approach (Optimized if instead of while)

Crucial Insight: If you are only asked to find the maximum length of a valid subarray (and not the exact subarray itself), you do not need to shrink the window back to a smaller size when it violates the condition. Once you find a maximum valid length, your window size never needs to shrink below that maximum length. You only need to slide a window of size maxLen + 1 forward.

// Optimal Approach: O(N) Sliding Window using 'if' instead of 'while'
int left = 0, right = 0, sum = 0, maxLen = 0;
int n = arr.size();

while (right < n) {
    sum += arr[right]; // Expand window
    
    // Instead of shrinking completely with a while loop, 
    // simply slide the window of fixed maximum size by 1 if invalid.
    if (sum > k) {
        sum -= arr[left];
        left++;
    }
    
    if (sum <= k) {
        maxLen = max(maxLen, right - left + 1);
    }
    
    right++;
}

• Time Complexity: $\mathcal{O}(N)$ — exactly one pass through the array.
• Space Complexity: $\mathcal{O}(1)$
• Note on Subarrays: If the problem requires you to return the actual subarray rather than just its length, you must use the while loop shrinking mechanism to correctly isolate valid bounds.

6. Pattern 3: Number of Subarrays with a Condition

Problem Setup

Find the exact number of subarrays meeting a strict condition (e.g., sum == K).

The Subtraction Trick

When direct window expansion and shrinking become ambiguous due to strict equality constraints (sum == K), we transform the counting problem into a difference of two "less than or equal to" inequalities:

Both Count(sum <= K) and Count(sum <= K - 1) can be efficiently solved using Pattern 2 sliding window templates.

7. Pattern 4: Shortest / Minimum Window Substring

Problem Setup

Find the shortest subarray or substring that satisfies a given condition.

Algorithmic Mechanics

1. Initialize L = 0, R = 0, and track a minimum length (e.g., minLen = infinity).
2. Expand R until the window becomes valid.
3. Once valid, shrink from the left (L) as much as possible while maintaining validity to discover the shortest possible window satisfying the condition.
4. Record the minimum length and repeat the expansion cycle.

8. Summary and Key Takeaways

• Constructive Framework: Two pointers and sliding window are conceptual toolkits, not rigid algorithms to memorize. You mold the template to fit the problem constraints.
• Window Boundaries: L represents the left edge (shrinking), and R represents the right edge (expanding).
• Constant Window Pattern: Used when window size $K$ is fixed; slide by subtracting the outgoing element and adding the incoming element.
• Variable Window Pattern (Longest): Expand with R, validate, and shrink when invalid.
• Optimization Trick (if vs while): When searching for the maximum length, replace the shrinking while loop with an if statement to achieve strict $\mathcal{O}(N)$ time complexity.
• Exact Count Pattern: Problems asking for exact matches (sum == K) are typically solved by subtracting two inequality ranges: $f(\le K) - f(\le K-1)$.
• Subarray Retrieval: If the problem demands printing the actual subarray, retain the while loop shrinking pattern and store L and R indices whenever a new maximum length is found.