# Sliding Window and Two Pointer Interview Patterns

Source: https://www.techinterview.org/post/3233461182/sliding-window-two-pointer-patterns/
Updated: 2026-07-05 · techinterview.org

Sliding window and two pointer techniques are among the most frequently tested patterns in coding interviews. They convert O(n²) or O(n³) brute-force solutions into O(n) linear time, and appear in substring, subarray, and two-sequence problems across all major tech company interviews.

## Two Pointer: Fundamentals


```
# Pattern 1: Converging pointers (sorted array, find pair)
def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []


# Pattern 2: Fast/slow write pointer (in-place dedup)
def remove_duplicates(nums: list[int]) -> int:
    """LC 26: in-place, return new length"""
    k = 0  # write pointer
    for read in range(len(nums)):
        if k == 0 or nums[read] != nums[k - 1]:
            nums[k] = nums[read]
            k += 1
    return k
```


## Pattern: Three Sum (Sort + Two Pointers)


```
def threeSum(nums: list[int]) -> list[list[int]]:
    """LC 15: all unique triplets summing to 0 — O(n²)"""
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i-1]:
            continue  # skip duplicate anchors
        left, right = i + 1, len(nums) - 1
        while left < right:
            s = nums[i] + nums[left] + nums[right]
            if s == 0:
                result.append([nums[i], nums[left], nums[right]])
                while left < right and nums[left] == nums[left+1]: left += 1
                while left < right and nums[right] == nums[right-1]: right -= 1
                left += 1; right -= 1
            elif s < 0: left += 1
            else: right -= 1
    return result  # Time O(n²), Space O(1)
```


## Fixed-Size Sliding Window


```
def max_sum_subarray_k(nums: list[int], k: int) -> int:
    """Maximum sum of any subarray of length k — O(n)"""
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # slide: add new, remove old
        max_sum = max(max_sum, window_sum)
    return max_sum

def find_all_anagrams(s: str, p: str) -> list[int]:
    """LC 438: All anagram start indices — O(n)"""
    from collections import Counter
    need = Counter(p)
    have = Counter(s[:len(p)])
    result = []
    if have == need:
        result.append(0)
    for i in range(len(p), len(s)):
        # add new char
        have[s[i]] += 1
        # remove old char
        old = s[i - len(p)]
        have[old] -= 1
        if have[old] == 0:
            del have[old]
        if have == need:
            result.append(i - len(p) + 1)
    return result
```


## Variable-Size Sliding Window (Expand/Shrink)


```
Template for "shortest/longest subarray satisfying condition":

def sliding_window_variable(nums, condition):
    left = 0
    result = float('inf')  # or -inf for longest
    window_state = initial_state
    for right in range(len(nums)):
        # EXPAND: add nums[right] to window
        update(window_state, nums[right])
        # SHRINK: move left until window is valid (for shortest)
        # OR: while window is valid, try to shrink (for longest)
        while condition(window_state):
            result = min(result, right - left + 1)
            remove(window_state, nums[left])
            left += 1
    return result
```


### Minimum Size Subarray Sum


```
def minSubArrayLen(target: int, nums: list[int]) -> int:
    """LC 209: shortest subarray with sum >= target — O(n)"""
    left = 0
    current_sum = 0
    min_len = float('inf')
    for right in range(len(nums)):
        current_sum += nums[right]
        while current_sum >= target:
            min_len = min(min_len, right - left + 1)
            current_sum -= nums[left]
            left += 1
    return min_len if min_len != float('inf') else 0
```


### Longest Substring Without Repeating Characters


```
def lengthOfLongestSubstring(s: str) -> int:
    """LC 3 — O(n) with char index tracking"""
    char_index = {}  # char → last seen index
    left = 0
    max_len = 0
    for right, ch in enumerate(s):
        if ch in char_index and char_index[ch] >= left:
            left = char_index[ch] + 1  # jump left past duplicate
        char_index[ch] = right
        max_len = max(max_len, right - left + 1)
    return max_len
```


### Longest Substring with At Most K Distinct Characters


```
def lengthOfLongestSubstringKDistinct(s: str, k: int) -> int:
    """LC 340 — O(n)"""
    from collections import defaultdict
    count = defaultdict(int)
    left = 0
    max_len = 0
    for right, ch in enumerate(s):
        count[ch] += 1
        while len(count) > k:
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1
        max_len = max(max_len, right - left + 1)
    return max_len
```


## Pattern: Minimum Window Substring


```
def minWindow(s: str, t: str) -> str:
    """LC 76: smallest window in s containing all chars of t — O(n+m)"""
    from collections import Counter
    need = Counter(t)
    missing = len(t)  # total chars still needed
    left = 0
    best_left = best_right = -1
    best_len = float('inf')
    for right, ch in enumerate(s):
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        if missing == 0:  # window contains all chars of t
            # shrink from left
            while need[s[left]] < 0:
                need[s[left]] += 1
                left += 1
            # left is now at tightest valid position
            if right - left + 1 < best_len:
                best_len = right - left + 1
                best_left, best_right = left, right
            # advance left to search for better windows
            need[s[left]] += 1
            missing += 1
            left += 1
    return s[best_left:best_right+1] if best_left != -1 else ''
```


## Pattern: [Container With Most Water](https://www.techinterview.org/post/3233474773/container-with-most-water-two-pointer/)


```
def maxArea(height: list[int]) -> int:
    """LC 11: converging two pointers — O(n)"""
    left, right = 0, len(height) - 1
    max_water = 0
    while left < right:
        water = min(height[left], height[right]) * (right - left)
        max_water = max(max_water, water)
        # move the shorter wall inward (moving taller can't help)
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    return max_water
```


## Pattern: Trapping Rain Water


```
def trap(height: list[int]) -> int:
    """LC 42: two pointer O(n) time O(1) space"""
    left, right = 0, len(height) - 1
    left_max = right_max = 0
    water = 0
    while left < right:
        if height[left] = left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    return water

# Key insight: at any position, water trapped = min(max_left, max_right) - height
# Two-pointer approach: whichever side has smaller max determines water at current position
```


## Pattern: Sliding Window Maximum (Monotonic Deque)


```
from collections import deque

def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
    """LC 239: max of each window — O(n)"""
    dq = deque()  # stores indices, decreasing values
    result = []
    for i, num in enumerate(nums):
        # remove indices outside window
        while dq and dq[0] < i - k + 1:
            dq.popleft()
        # maintain decreasing order (remove smaller elements from back)
        while dq and nums[dq[-1]] = k - 1:
            result.append(nums[dq[0]])  # front is always the max
    return result
```


## Problem Recognition Cheat Sheet

| Clue in Problem | Pattern |
| --- | --- |
| "sorted array", "find pair/triplet summing to X" | Two pointers (converging) |
| "subarray/substring", "sum/count/condition" | Sliding window (expand/shrink) |
| "at most K distinct", "longest without repeating" | Variable-size window + hashmap |
| "fixed size window", "max/min of all windows" | Fixed window or monotonic deque |
| "linked list cycle", "find middle" | Fast/slow pointers |
| "remove duplicates in-place", "partition" | Read/write pointers (same direction) |

## Key Interview Tips

- **When to shrink**: For "shortest" problems, shrink when condition is satisfied. For "longest" problems, shrink when condition is violated. The template is the same — just swap the shrink trigger.

- **Avoid comparison of Counter objects**: `Counter == Counter` is O(k) — track a `formed` count instead (how many unique chars have required frequency) for O(1) per step.

- **Three-pointer problems**: Dutch National Flag (3-way partition) uses three pointers — low, mid, high — to sort [0,1,2] in-place in a single pass.

- **Two pointers in 2D**: Problems like "search a sorted 2D matrix" — start from top-right corner: move left if value > target, move down if value < target. O(m+n).

- [Shopify Interview Guide](https://techinterview.org/shopify-interview-guide/)

- [Coinbase Interview Guide](https://techinterview.org/coinbase-interview-guide/)

- [Atlassian Interview Guide](https://techinterview.org/atlassian-interview-guide/)

- [LinkedIn Interview Guide](https://techinterview.org/linkedin-interview-guide/)

- [Uber Interview Guide](https://techinterview.org/uber-interview-guide/)

- [Apple Interview Guide](https://techinterview.org/apple-interview-guide/)

## Companies That Ask This

- [Meta Interview Guide](https://techinterview.org/meta-interview-guide/)