LeetCode Patterns: Two Pointers and Sliding Window

Introduction

LeetCode two pointers and sliding window are the most common patterns in array and string problems. Two pointers create O(n) traversal by using “both ends of interval” or “advancing in same direction”, while sliding window maintains sum, frequency, or conditions of continuous intervals to find optimal solutions. In this article, we’ll first memorize templates for each pattern, then apply them to problems like LeetCode 3 (Longest Substring Without Repeating Characters) and 76 (Minimum Window Substring). We’ll translate the same logic to C++ and Python so you can use them immediately in interviews and exams.

What You’ll Learn

• Distinguish between two pointers (symmetric/simultaneous advance) and sliding window
• Use fixed length vs variable length window templates instantly
• Practice translating the same logic between C++ and Python

---

Table of Contents

1. Concepts
2. Practical Implementation
3. Advanced Usage
4. Performance Comparison
5. Real-World Cases
6. Troubleshooting
7. Conclusion

---

Concepts

Two Pointers

• Symmetric: Find pairs with sum equal to target in sorted array — move left and right inward.
• Simultaneous Advance: “…ending at each element” type — i and j only increase in one direction for overall O(n).

Sliding Window

• Fixed Length k: Slide window one position at a time, updating sum/average/max.
• Variable Length: Expand right until condition is met, shrink left when broken to record min/max length. Sliding window is often viewed as a type of two pointers. In interviews/exams, saying “represent interval with two indices” is sufficient.

---

Practical Implementation

Variable Length — “Longest Substring Without Repeating Characters” (LeetCode 3)

Idea: Expand with right while counting character frequency, shrink left when duplicates appear to restore valid interval.

// C++17 — Longest Substring Without Repeating Characters
#include <string>
#include <unordered_map>
#include <algorithm>
class Solution {
public:
    int lengthOfLongestSubstring(const std::string& s) {
        std::unordered_map<char, int> cnt;
        int left = 0, ans = 0;
        for (int right = 0; right < (int)s.size(); ++right) {
            cnt[s[right]]++;
            while (cnt[s[right]] > 1) {
                cnt[s[left]]--;
                left++;
            }
            ans = std::max(ans, right - left + 1);
        }
        return ans;
    }
};

# Python 3 — Same logic
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        cnt = {}
        left = 0
        ans = 0
        for right, ch in enumerate(s):
            cnt[ch] = cnt.get(ch, 0) + 1
            while cnt[ch] > 1:
                cnt[s[left]] -= 1
                left += 1
            ans = max(ans, right - left + 1)
        return ans

Minimum Window — LeetCode 76 Style

Idea: Track whether window counter satisfies target multiset with need, shrink left when satisfied to update minimum length.

from collections import Counter
class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if not s or not t:
            return ""
        need = Counter(t)
        required = len(need)
        formed = 0
        window = {}
        left = 0
        best_len = float("inf")
        best = (0, 0)
        for right, c in enumerate(s):
            window[c] = window.get(c, 0) + 1
            if c in need and window[c] == need[c]:
                formed += 1
            while formed == required and left <= right:
                if right - left + 1 < best_len:
                    best_len = right - left + 1
                    best = (left, right)
                lch = s[left]
                window[lch] -= 1
                if lch in need and window[lch] < need[lch]:
                    formed -= 1
                left += 1
        if best_len == float("inf"):
            return ""
        l, r = best
        return s[l : r + 1]

// C++17 — Minimum Window Substring
#include <string>
#include <unordered_map>
#include <climits>
class Solution {
public:
    std::string minWindow(const std::string& s, const std::string& t) {
        if (s.empty() || t.empty()) return "";
        
        std::unordered_map<char, int> need, window;
        for (char c : t) need[c]++;
        
        int required = need.size();
        int formed = 0;
        int left = 0;
        int minLen = INT_MAX;
        int minLeft = 0;
        
        for (int right = 0; right < (int)s.size(); ++right) {
            char c = s[right];
            window[c]++;
            
            if (need.count(c) && window[c] == need[c]) {
                formed++;
            }
            
            while (formed == required && left <= right) {
                if (right - left + 1 < minLen) {
                    minLen = right - left + 1;
                    minLeft = left;
                }
                
                char lch = s[left];
                window[lch]--;
                if (need.count(lch) && window[lch] < need[lch]) {
                    formed--;
                }
                left++;
            }
        }
        
        return minLen == INT_MAX ? "" : s.substr(minLeft, minLen);
    }
};

---

Advanced Usage

• Frequency Limit in Integer Arrays: Use fixed-size array (e.g., 26 slots for lowercase) instead of Counter for constant time updates.
• Max Length vs Min Length: Just change the while condition — “move left on violation” is the common skeleton.
• Fixed Length k: Maintain sum while sliding — window_sum += a[right] - a[left-k] pattern.

Fixed Length Window — Maximum Average Subarray

// C++ — Maximum average of subarray with length 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 maxSum = sum;
        for (int i = k; i < nums.size(); i++) {
            sum += nums[i] - nums[i - k];
            maxSum = max(maxSum, sum);
        }
        
        return maxSum / k;
    }
};

# Python — Same logic
class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        window_sum = sum(nums[:k])
        max_sum = window_sum
        
        for i in range(k, len(nums)):
            window_sum += nums[i] - nums[i - k]
            max_sum = max(max_sum, window_sum)
        
        return max_sum / k

---

Performance Comparison

Pattern	Typical Time	Notes
Two Pointers (one direction)	O(n)	Inner while moves pointers total O(n)
Sliding Window + HashMap	O(n)	Can be O(1) space if limited to alphabet
Simple nested for	O(n²)	First suspect if it can be converted to sliding

Space Complexity

• HashMap/Counter: O(k) where k is unique characters
• Fixed Array: O(1) for limited character set (e.g., 26 lowercase letters)
• No Extra Space: Some problems can track with just counters

---

Real-World Cases

• Log Streams: Sum of last k minutes window — Fixed window + deque.
• String Search Optimization: Substring frequency comparison — Counter + sliding (combined with Rabin-Karp).
• Network Traffic Analysis: Monitor packet counts in time windows
• Stock Trading: Maximum profit in k-day windows

---

Troubleshooting

Confused About while Condition

• Write the invariant in one line: “[left, right] is always a valid candidate” or “move left minimally on violation”.
• Template structure:

  expand right (add to window)
  while (condition violated):
      shrink left (remove from window)
  update answer

Off-by-One Errors

• right - left + 1 vs right - left, verify with empty string and length 1 test cases.
• Remember: [left, right] is inclusive on both ends
• Window size = right - left + 1

Performance Issues

• Ensure inner operations are O(1) — use counters, not searching
• Avoid nested loops inside the window loop
• Profile if using complex data structures

---

Common Patterns Summary

Pattern 1: Longest Valid Substring

def longest_valid(s):
    left = 0
    ans = 0
    # state tracking (counter, set, etc.)
    
    for right in range(len(s)):
        # add s[right] to window
        
        while not valid():
            # remove s[left] from window
            left += 1
        
        ans = max(ans, right - left + 1)
    
    return ans

Pattern 2: Shortest Valid Substring

def shortest_valid(s):
    left = 0
    ans = float('inf')
    # state tracking
    
    for right in range(len(s)):
        # add s[right] to window
        
        while valid():
            ans = min(ans, right - left + 1)
            # remove s[left] from window
            left += 1
    
    return ans if ans != float('inf') else 0

Pattern 3: Count Valid Subarrays

def count_valid(nums):
    left = 0
    count = 0
    # state tracking
    
    for right in range(len(nums)):
        # add nums[right] to window
        
        while not valid():
            # remove nums[left] from window
            left += 1
        
        # all subarrays ending at right are valid
        count += right - left + 1
    
    return count

---

Conclusion

LeetCode two pointers and sliding window are most efficient when you memorize templates and practice changing only the invariant for each problem. If you get time limit exceeded, check complexity first with the time complexity checklist.

Key Takeaways

1. Two pointers is a general technique, sliding window is a specific application
2. Fixed window: Maintain window size, slide by adding/removing elements
3. Variable window: Expand until valid, shrink to find optimal
4. Template approach: Memorize structure, customize condition
5. Language choice: Use what you’re comfortable with, practice both for flexibility

---

Practice Problems

Beginner

• LeetCode 3: Longest Substring Without Repeating Characters
• LeetCode 209: Minimum Size Subarray Sum
• LeetCode 643: Maximum Average Subarray I

Intermediate

• LeetCode 76: Minimum Window Substring
• LeetCode 438: Find All Anagrams in a String
• LeetCode 567: Permutation in String

Advanced

• LeetCode 239: Sliding Window Maximum
• LeetCode 992: Subarrays with K Different Integers
• LeetCode 1004: Max Consecutive Ones III

---

Related Posts

• BFS vs DFS Complete Comparison
• Algorithm Optimization Case Studies
• Time Complexity Optimization Checklist

---

Keywords

Algorithm, LeetCode, Two Pointers, Sliding Window, Coding Interview, Pattern, Template, C++, Python, Optimization

---

자주 묻는 질문 (FAQ)

Q. 이 내용을 실무에서 언제 쓰나요?

A. Master LeetCode two pointers and sliding window patterns. Learn the difference between fixed and variable window templat… 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.

Q. 선행으로 읽으면 좋은 글은?

A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.

Q. 더 깊이 공부하려면?

A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.

---

같이 보면 좋은 글 (내부 링크)

이 주제와 연결되는 다른 글입니다.

• 알고리즘 BFS vs DFS 완벽 비교 | 그래프 탐색 선택 가이드
• 알고리즘 최적화 실전 사례 | 코딩테스트 시간 초과(TLE) 해결기
• 코딩 테스트에서 시간 복잡도 줄이는 체크리스트 | TLE 탈출

---

이 글에서 다루는 키워드 (관련 검색어)

Algorithm, LeetCode, Two Pointers, Sliding Window, Coding Interview, Pattern 등으로 검색하시면 이 글이 도움이 됩니다.