03. Two Pointers and Sliding Window

📋 Jump to Takeaways

Two pointers and sliding window are techniques that turn O(n²) brute-force solutions into O(n). They work by maintaining a window or pair of indices that move through the array in a controlled way, avoiding redundant work.

Two Pointers: Opposite Direction

Two pointers start at opposite ends and move toward each other. Used when the array is sorted or when you need to compare elements from both ends.

LeetCode 167 - Two Sum II - Input Array Is Sorted

def two_sum_sorted(nums: list[int], target: int) -> list[int]:
    l, r = 0, len(nums) - 1
    while l < r:
        s = nums[l] + nums[r]
        if s == target:
            return [l, r]
        elif s < target:
            l += 1  # need larger sum
        else:
            r -= 1  # need smaller sum
    return []

Why it works: if the sum is too small, moving l right increases it. If too large, moving r left decreases it. Each element is visited at most once → O(n).

LeetCode 11 - Container With Most Water

def max_area(height: list[int]) -> int:
    l, r = 0, len(height) - 1
    best = 0
    while l < r:
        area = min(height[l], height[r]) * (r - l)
        best = max(best, area)
        if height[l] < height[r]:
            l += 1
        else:
            r -= 1
    return best

Move the shorter side inward — moving the taller side can never increase the area.

LeetCode 125 - Valid Palindrome

def is_palindrome(s: str) -> bool:
    l, r = 0, len(s) - 1
    while l < r:
        while l < r and not s[l].isalnum():
            l += 1
        while l < r and not s[r].isalnum():
            r -= 1
        if s[l].lower() != s[r].lower():
            return False
        l += 1
        r -= 1
    return True

Two Pointers: Same Direction (Read/Write)

Both pointers move left to right, but at different speeds. The "fast" pointer scans every element; the "slow" pointer tracks a position of interest.

LeetCode 26 - Remove Duplicates from Sorted Array

def remove_duplicates(nums: list[int]) -> int:
    if not nums:
        return 0
    slow = 1
    for fast in range(1, len(nums)):
        if nums[fast] != nums[fast - 1]:
            nums[slow] = nums[fast]
            slow += 1
    return slow

The slow pointer marks where the next valid element should go. The fast pointer finds valid elements. This is the "read/write pointer" pattern.

LeetCode 283 - Move Zeroes

def move_zeroes(nums: list[int]) -> None:
    w = 0
    for r in range(len(nums)):
        if nums[r] != 0:
            nums[w], nums[r] = nums[r], nums[w]
            w += 1

Two Pointers: Fast and Slow (Floyd's)

Used on linked lists to detect cycles and find midpoints:

LeetCode 141 - Linked List Cycle

def has_cycle(head) -> bool:
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

3Sum — Fix One, Two-Pointer the Rest

LeetCode 15 - 3Sum

def three_sum(nums: list[int]) -> list[list[int]]:
    nums.sort()
    result = []
    for i in range(len(nums) - 2):
        if i > 0 and nums[i] == nums[i - 1]:
            continue  # skip duplicates
        l, r = i + 1, len(nums) - 1
        while l < r:
            s = nums[i] + nums[l] + nums[r]
            if s == 0:
                result.append([nums[i], nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
                while l < r and nums[r] == nums[r + 1]:
                    r -= 1
            elif s < 0:
                l += 1
            else:
                r -= 1
    return result

O(n²) — one loop * two-pointer pass. The O(n³) brute force checks every triple.

Sliding Window: Fixed Size

Maintain a window of exactly K elements. Slide it across the array — add the new right element, remove the old left element.

# Maximum sum of K consecutive elements — O(n)
def max_sum_k(nums: list[int], k: int) -> int:
    window_sum = sum(nums[:k])
    max_sum = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]  # add right, remove left
        max_sum = max(max_sum, window_sum)
    return max_sum

Without sliding window: check every subarray of size K → O(n×k). With sliding window: O(n).

Sliding Window: Variable Size

The window expands right until a condition is violated, then shrinks from the left until the condition is restored. This is the more powerful (and common) pattern.

Template:

def sliding_window(s: str) -> int:
    left = 0
    best = 0
    # state tracking (dict, counter, etc.)

    for right in range(len(s)):
        # expand: add s[right] to window state

        while "window is invalid":
            # shrink: remove s[left] from window state
            left += 1

        # update best answer with current valid window
        best = max(best, right - left + 1)
    return best

LeetCode 3 - Longest Substring Without Repeating Characters

def length_of_longest_substring(s: str) -> int:
    seen = {}  # char → last index
    left = 0
    best = 0
    for right in range(len(s)):
        if s[right] in seen and seen[s[right]] >= left:
            left = seen[s[right]] + 1  # shrink past the duplicate
        seen[s[right]] = right
        best = max(best, right - left + 1)
    return best

LeetCode 209 - Minimum Size Subarray Sum

def min_sub_array_len(target: int, nums: list[int]) -> int:
    left = 0
    current_sum = 0
    best = len(nums) + 1
    for right in range(len(nums)):
        current_sum += nums[right]  # expand
        while current_sum >= target:
            best = min(best, right - left + 1)
            current_sum -= nums[left]  # shrink
            left += 1
    return best if best <= len(nums) else 0

LeetCode 76 - Minimum Window Substring

Given strings s and t, find the shortest substring of s that contains all characters of t (including duplicates). Example: s = "ADOBECODEBANC", t = "ABC" → answer is "BANC".

Approach: Expand right until the window contains all chars of t. Then shrink left to minimize the window while it's still valid. Track "how many chars of t are still missing" — when missing == 0, the window is valid.

from collections import Counter

def min_window(s: str, t: str) -> str:
    need = Counter(t)
    missing = len(t)
    left = 0
    start, end = 0, 0
    best = len(s) + 1

    for right in range(len(s)):
        if need[s[right]] > 0:
            missing -= 1
        need[s[right]] -= 1

        while missing == 0:
            if right - left + 1 < best:
                best = right - left + 1
                start, end = left, right + 1
            need[s[left]] += 1
            if need[s[left]] > 0:
                missing += 1
            left += 1

    return s[start:end] if best <= len(s) else ""

Kadane's Algorithm

Kadane's solves the maximum subarray sum problem in O(n). At each position, decide: extend the current subarray, or start fresh here.

LeetCode 53 - Maximum Subarray

def max_sub_array(nums: list[int]) -> int:
    max_sum = cur_sum = nums[0]
    for i in range(1, len(nums)):
        cur_sum = max(nums[i], cur_sum + nums[i])
        max_sum = max(max_sum, cur_sum)
    return max_sum

The logic: if cur_sum has gone negative, it can only hurt future elements — drop it and restart. This is the same "extend or reset" idea as variable-size sliding window, but without an explicit left pointer.

Why it belongs here: Kadane's is not DP in the traditional sense (no table, no subproblem lookup). It's a single-pass greedy scan that maintains running state — the same mental model as sliding window.

Variant — Maximum Product Subarray:

LeetCode 152 - Maximum Product Subarray

Find the contiguous subarray with the largest product. The twist: negatives can flip signs — a very negative min_prod times a negative number becomes the new max. Track both max_prod and min_prod at each step, swap them when you hit a negative.

def max_product(nums: list[int]) -> int:
    max_prod = min_prod = result = nums[0]
    for i in range(1, len(nums)):
        if nums[i] < 0:
            max_prod, min_prod = min_prod, max_prod
        max_prod = max(nums[i], max_prod * nums[i])
        min_prod = min(nums[i], min_prod * nums[i])
        result = max(result, max_prod)
    return result

When to Use Two Pointers vs Sliding Window

Technique	When
Opposite-direction pointers	Sorted array, pair problems, palindromes
Same-direction (read/write)	In-place removal, compaction
Fast/slow pointers	Linked list cycles, finding midpoints
Fixed sliding window	Subarray/substring of exact size K
Variable sliding window	Longest/shortest subarray satisfying a condition
Kadane's algorithm	Maximum/minimum subarray sum or product

The Key Insight

Both techniques avoid recomputation. Instead of recalculating from scratch for every position (O(n²)), they maintain running state and update it incrementally as pointers move (O(n)).

Python-Specific Tips

Use enumerate() when you need both index and value
Tuple unpacking for swaps: nums[i], nums[j] = nums[j], nums[i]
collections.defaultdict(int) for window frequency maps
Counter for sliding window character counting with subtraction
Python's max()/min() with short lists is fine — don't over-optimize

Practice Problems

Problem	Difficulty	Link
Valid Palindrome	Easy	LeetCode 125
Move Zeroes	Easy	LeetCode 283
Two Sum II (sorted)	Medium	LeetCode 167
3Sum	Medium	LeetCode 15
Container With Most Water	Medium	LeetCode 11
Longest Substring Without Repeating Characters	Medium	LeetCode 3
Minimum Size Subarray Sum	Medium	LeetCode 209
Minimum Window Substring	Hard	LeetCode 76
Maximum Subarray	Medium	LeetCode 53
Maximum Product Subarray	Medium	LeetCode 152
Trapping Rain Water	Hard	LeetCode 42

Key Takeaways

Two pointers and sliding window turn O(n²) into O(n) by avoiding redundant work
Opposite-direction: sorted arrays, pair sums, palindromes
Same-direction: in-place compaction, read/write pointer
Fixed window: add right, remove left, constant size
Variable window: expand right until invalid, shrink left until valid
The variable sliding window template solves dozens of "longest/shortest subarray" problems
Both techniques maintain running state instead of recomputing from scratch
Kadane's algorithm: extend the subarray if it helps, restart if running sum is negative — O(n)
In Python, use Counter and defaultdict for window state — they're optimized in C