LeetCode (2): Two Pointers - Collision, Fast-Slow & Sliding Window Complete Guide

Chen Kai BOSS

2023-04-18 00:00:00 2023-04-18 00:00

Algorithm

9.5k Words 59 Mins

Two pointers is one of the most elegant techniques in interview algorithms: by cleverly maintaining the positional relationship between two pointers, you can reduce brute-force complexity towhile maintainingspace overhead. This guide systematically introduces three core patterns —Collision Pointers (converging from both ends), Fast-Slow Pointers (cycle detection with speed differential), and Sliding Window (dynamic subarray maintenance)— building a complete two-pointer thinking system through six classic problems. We'll also deeply analyze when to choose two pointers over hash tables, how to avoid boundary errors, and communication techniques for interviews.

📚 LeetCode Algorithm Masterclass Series (10 Parts): 1. Hash Tables (Two Sum, Longest Consecutive, Group Anagrams) 2. → Two Pointers (Collision, Fast-Slow, Sliding Window) ← You are here 3. Linked List Operations (Reverse, cycle detection, merge) 4. Binary Tree Traversal & Recursion (Inorder/Preorder/Postorder, LCA) 5. Dynamic Programming Intro (1D/2D DP, state transition) 6. Backtracking Algorithms (Permutations, combinations, pruning) 7. Binary Search Advanced (Integer/Real binary search, answer binary search) 8. Stack & Queue (Monotonic stack, priority queue, deque) 9. Graph Algorithms (BFS/DFS, topological sort, union-find) 10. Greedy & Bit Manipulation (Greedy strategies, bitwise tricks)

Core Concept of Two Pointers

Why Do We Need Two Pointers?

Scenario: Find two numbers in a sorted array that sum to a target value.

Brute Force: Two nested loops enumerate all pairs → Two Pointers Optimization:

Left pointer points to smallest value
Right pointer points to largest value
If sum too small, move left pointer right (increase sum)
If sum too large, move right pointer left (decrease sum)
Complexity reduces to

Three Core Patterns

Pattern	Pointer Relationship	Typical Scenario	Example Problems
Collision Pointers	Move from both ends toward center	Sorted array, palindrome check	Two Sum II, Container With Most Water
Fast-Slow Pointers	Move at different speeds	Linked list cycle detection, find middle	Linked List Cycle, Happy Number
Sliding Window	Maintain fixed/dynamic interval	Subarray/substring problems	Longest Substring Without Repeating, Minimum Window Substring

Pattern 1: Collision Pointers

Core Characteristics

Left pointer starts from beginning
Right pointer starts from end
Pointers converge, moving toward each other until they meet
Usually used for sorted arrays or problems requiring consideration of both ends

Real-World Analogy

Imagine you're at a bookstore with a fixed budget for two books:

You start from the cheapest shelf
Your friend starts from the most expensive shelf
If total too cheap, you move toward expensive books
If total too expensive, friend moves toward cheap books
Eventually you meet at shelves that exactly fit your budget

LeetCode 11: Container With Most Water

Problem Analysis

Core Challenge: The key difficulty lies in finding the container with maximum area intime, rather than brute-force checking allpossible container pairs. Container area is determined by both width and height, where width is the distance between two lines and height is the shorter line.

Solution Approach: Use collision pointers (converging from both ends). The key insight is a greedy strategy: always move the shorter side. Since area is determined by the shorter edge, moving the longer edge only reduces width without increasing height, so area must decrease; moving the shorter edge reduces width but may encounter a taller edge, so area may increase. This strategy ensures we don't miss the optimal solution.

Complexity Analysis: - Time Complexity: - Each element visited at most once - Space Complexity: - Only two pointers

Key Insight: The correctness of the greedy strategy is based on proof by contradiction: if the optimal solution is, our algorithm will gradually approach it by moving the shorter side, without skipping the optimal solution.

Problem Statement

Givennon-negative integers, where each represents a pointon a coordinate plane.vertical lines are drawn such that the two endpoints of lineare atand. Find two lines that together with the x-axis form a container that holds the most water.

Example:

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: Lines atandform container, area = Constraints:

- -

Core Insight

Area formula: Greedy strategy: 1. Start from both ends (maximum width) 2. Always move the shorter side (since height is determined by the shorter line) 3. Moving the taller side can only decrease area (width decreases, height won't increase)

Python Implementation

def maxArea(height):
    # Initialize two pointers: start from both ends (maximum width)
    left, right = 0, len(height) - 1
    max_area = 0  # Track maximum area
    
    # Collision pointers: converge toward center
    while left < right:
        # Calculate current container area
        # Width = distance between two lines
        width = right - left
        # Height = shorter line (water overflows from shorter side)
        current_height = min(height[left], height[right])
        # Area = width × height
        current_area = width * current_height
        # Update maximum area
        max_area = max(max_area, current_area)
        
        # Key greedy strategy: always move the shorter side
        # Reason: Moving longer side only reduces width, height won't increase, area must decrease
        # Moving shorter side reduces width but may encounter taller edge, area may increase
        if height[left] < height[right]:
            left += 1   # Move left pointer right
        else:
            right -= 1  # Move right pointer left
    
    return max_area

Java Implementation

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxArea = 0;
        
        while (left < right) {
            int width = right - left;
            int currentHeight = Math.min(height[left], height[right]);
            int currentArea = width * currentHeight;
            maxArea = Math.max(maxArea, currentArea);
            
            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        
        return maxArea;
    }
}

Complexity Analysis

Time:, each element visited at most once
Space:, only two pointers

Deep Dive

Algorithm Principle: Why Is the Greedy Strategy Correct?

Core Idea: Area formula is, where. When we move pointers: - Move longer side:decreases, butwon't increase (height determined by shorter side), so area must decrease - Move shorter side:decreases, but may encounter taller edge,may increase, area may increase

Therefore, only moving the shorter side has potential to find larger area.

Time Complexity Proof: Why O(n)?

Pointer movement: left can only move right, right can only move left
Total moves: At most(stop when pointers meet)
Each iteration:operations (calculate area, compare, move pointers)
Total time:

Space Optimization: Is There a More Space-Efficient Method?

This problem is already space-optimal: - Two pointers:space - Cannot optimize further: Must store current max area and two pointer positions

Comparison with other methods: - Brute force:space buttime - Dynamic programming: Not applicable (no overlapping subproblems)

Common Mistakes Analysis

Mistake Type	Wrong Code	Problem	Correct Approach
Move longer side	`if height[left] > height[right]: left += 1`	Miss optimal solution	Move shorter side
Move both sides	`left += 1; right -= 1`	May skip optimal solution	Move only one side
Forget to update max	Calculate but don't store	Cannot return answer	`max_area = max(max_area, current_area)`

Variant Extensions

Container With Most Water (3D): Extend to 3D space
Trapping Rain Water: Similar problem but different calculation
Largest Rectangle Area: Use monotonic stack

Why Is This Greedy Strategy Correct?

Proof by contradiction: Assume optimal solution iswhere - If we start atand move toward: - If, we move left pointer - All areaswhereare considered - Key: Moving the shorter pointer is the only way to potentially find larger area - Moving the taller pointer must result in smaller area (width decreases, height can't increase)

Mathematical Proof

Let,, assume.

Current area:where If we move right pointer (wrong move):

New width:(smaller)
New height:(can't exceed shorter side)
New area: If we move left pointer (correct move):
New width:
New height:could be larger than
New area:, might be larger

Conclusion: Only moving shorter pointer has potential for improvement.

Common Pitfalls

Pitfall 1: Try All Pairs

# ❌ Brute force O(n ²)
for i in range(n):
    for j in range(i+1, n):
        area = min(height[i], height[j]) * (j - i)

Why slow: Computes allpairs

Pitfall 2: Move Taller Pointer

1
2
3

# ❌ Wrong strategy
if height[left] > height[right]:
    left += 1

Why wrong: Misses potential optimal solutions

Pitfall 3: Sort First

Problem: Sorting destroys original position relationships, but width calculation depends on indices

LeetCode 15: 3Sum

Problem Analysis

Core Challenge: The key difficulty lies in efficiently finding all unique triplets withoutbrute-force enumeration. The problem requires returning all solutions without duplicates, which adds complexity to deduplication.

Solution Approach: Convert three sum to two sum. First sort the array (allowed since problem doesn't require indices), then fix the first number and use collision pointers on the remaining portion to find two numbers summing to -nums[i]. The key technique is three-level deduplication: skip duplicates at the first number, second number (left pointer), and third number (right pointer) to ensure unique results.

Complexity Analysis: - Time Complexity: - Sorting+ outer loop× inner two pointers - Space Complexity:to - Sorting stack space

Key Insight: After sorting, we can use two pointers to reduce the complexity of finding two numbers fromto. Deduplication is crucial and must be handled correctly at all three positions.

Problem Statement

Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] such thatand nums[i] + nums[j] + nums[k] = 0. The solution set must not contain duplicate triplets.

Example:

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Constraints:

- -

Core Insight

Convert to Two Sum: 1. Sort the array first (allowed since problem doesn't require indices) 2. Fix first number nums[i] 3. Use collision pointers in remaining portion to find two numbers summing to -nums[i] 4. Skip duplicates to ensure unique triplets

Python Implementation

def threeSum(nums):
    # Sort array: enables two-pointer technique, O(n log n)
    # Note: Sorting changes element positions, but problem doesn't require indices
    nums.sort()  # O(n log n)
    result = []
    n = len(nums)
  
    # Fix first number, use two pointers for remaining two numbers
    for i in range(n - 2):
        # Deduplication: skip duplicate first numbers
        # If current number same as previous, skip to avoid duplicate triplets
        if i > 0 and nums[i] == nums[i-1]:
            continue
    
        # Early termination optimization: if smallest number > 0, all following are positive
        # Three positive numbers cannot sum to 0, exit directly
        if nums[i] > 0:
            break
    
        # Use collision pointers for remaining two numbers
        left, right = i + 1, n - 1
        # Target value = -nums[i], because nums[i] + nums[left] + nums[right] = 0
        target = -nums[i]
    
        while left < right:
            current_sum = nums[left] + nums[right]
            
            if current_sum == target:
                # Found a solution, add to result
                result.append([nums[i], nums[left], nums[right]])
                
                # Key: skip duplicate second and third numbers
                # Must skip here to avoid duplicate triplets
                while left < right and nums[left] == nums[left+1]:
                    left += 1  # Skip all duplicate left pointer values
                while left < right and nums[right] == nums[right-1]:
                    right -= 1  # Skip all duplicate right pointer values
            
                # Move pointers to continue searching for next solution
                left += 1
                right -= 1
            elif current_sum < target:
                # Sum too small, move left pointer right (increase sum)
                left += 1
            else:
                # Sum too large, move right pointer left (decrease sum)
                right -= 1
  
    return result

Complexity Analysis

Time: - Sorting: - Outer loop: - Inner two pointers: - Total:
Space:to(sorting stack space)

Deep Dive

Algorithm Principle: Why Does This Algorithm Work?

Core Idea: Convert three sum problem to two sum. After fixing the first number nums[i], the problem becomes: find two numbers in nums[i+1:] that sum to -nums[i]. After sorting, we can use collision pointers efficiently.

Deduplication Strategy: Must deduplicate at three positions: 1. First number: if i > 0 and nums[i] == nums[i-1]: continue 2. Second number: After finding solution, skip all duplicate nums[left] 3. Third number: After finding solution, skip all duplicate nums[right]

Why three-level deduplication: - If only deduplicate first number: [-1,-1,0,1] may produce [-1,0,1] twice - If don't deduplicate second/third: [-2,0,0,2] may produce [-2,0,2] twice

Time Complexity Proof: Why O(n ²)?

Sorting:
Outer loop: Fix first number,iterations
Inner two pointers: At mostoperations per iteration
Total time: Optimization effect: Compared to brute force, optimized to, significant improvement.

Space Optimization: Is There a More Space-Efficient Method?

Method 1: In-place sorting - Use in-place sorting algorithm:stack space - Already optimal

Method 2: Without sorting (hash table) - Use hash table to store two-sum pairs:time,space - Same time but more space, not recommended

Trade-off: Current method is optimal in both time and space.

Common Mistakes Analysis

Mistake Type	Wrong Code	Problem	Correct Approach
Wrong deduplication position	Skip duplicates before `if`	May skip valid solutions	Skip after finding solution
Forget to move pointers	Don't move after finding solution	Infinite loop	`left += 1; right -= 1`
Wrong early termination	`if nums[i] >= 0`	May miss negative solutions	`if nums[i] > 0`

Variant Extensions

Four Sum: Add another outer loop, fix two numbers
3Sum Closest: Find triplet with sum closest to target
3Sum (BST): Search in binary search tree

Deduplication Strategy Explained

Dedup Point 1: First Number

1 2	if i > 0 and nums[i] == nums[i-1]: continue

Example: nums = [-1, -1, 0, 1, 2]

At, process nums[0] = -1
At, skip (since nums[1] = nums[0] = -1)

Dedup Points 2 & 3: Second and Third Numbers

while left < right and nums[left] == nums[left+1]:
    left += 1
while left < right and nums[right] == nums[right-1]:
    right -= 1

Example: nums = [-4, -1, -1, 0, 1, 2], fix nums[0] = -4

After finding solution [-4, -1, 5]
left skips all duplicate -1s
right skips all duplicate 5s (if any)

Optimization Techniques

Optimization 1: Early Termination

1 2	if nums[i] > 0: break

Reason: Array sorted, if smallest number > 0, all following are positive, impossible to sum to 0

Optimization 2: Maximum Value Pruning

1 2	if nums[i] + nums[i+1] + nums[i+2] > 0: break

Reason: Current three smallest numbers already sum > 0, no point continuing

Optimization 3: Minimum Value Pruning

1 2	if nums[i] + nums[n-2] + nums[n-1] < 0: continue

Reason: Current number with two largest numbers still sum < 0, skip this iteration

Extension: 4Sum, kSum

4Sum: Add another outer loop, fix two numbers then two-pointer for remaining two. Time: kSum (generalized):

def kSum(nums, target, k):
    def helper(start, k, target):
        if k == 2:
            # Two-pointer base case
            left, right = start, len(nums) - 1
            while left < right:
                s = nums[left] + nums[right]
                if s < target:
                    left += 1
                elif s > target:
                    right -= 1
                else:
                    result.append(path + [nums[left], nums[right]])
                    left += 1
                    right -= 1
                    while left < right and nums[left] == nums[left-1]:
                        left += 1
        else:
            # Recursive case
            for i in range(start, len(nums) - k + 1):
                if i > start and nums[i] == nums[i-1]:
                    continue
                path.append(nums[i])
                helper(i + 1, k - 1, target - nums[i])
                path.pop()
    
    nums.sort()
    result = []
    path = []
    helper(0, k, target)
    return result

Pattern 2: Fast-Slow Pointers

Core Characteristics

Fast pointer moves multiple steps per iteration (usually 2)
Slow pointer moves fewer steps per iteration (usually 1)
Used for cycle detection, finding middle, specific positions

Real-World Analogy

Two runners on a circular track:

Fast runner: 2 meters/second
Slow runner: 1 meter/second
If track is circular, fast runner will eventually lap slow runner
If track has an endpoint, fast runner will reach end first

LeetCode 141: Linked List Cycle

Problem Statement

Given a linked list, determine if it has a cycle. A cycle exists if some node can be reached again by continuously following the next pointer.

Follow-up: Can you solve it usingspace?

Example:

Input: head = [3,2,0,-4], tail connects to node at index 1
Output: true

Core Insight: Floyd's Cycle Detection

Tortoise and Hare:

Slow pointer (tortoise) moves 1 step per iteration
Fast pointer (hare) moves 2 steps per iteration
If cycle exists, fast pointer will eventually catch up to slow pointer
If no cycle, fast pointer will reach end of list

Python Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def hasCycle(head):
    # Edge cases: empty list or single node cannot have cycle
    if not head or not head.next:
        return False
    
    # Initialize fast and slow pointers
    # Slow pointer: moves 1 step per iteration
    slow = head
    # Fast pointer: moves 2 steps per iteration (start from head.next to ensure different initial positions)
    fast = head.next
    
    # Loop until pointers meet or fast pointer reaches end
    while slow != fast:
        # Check if fast pointer reaches end (no cycle case)
        # Need to check both fast and fast.next because fast moves 2 steps
        if not fast or not fast.next:
            return False  # No cycle
        
        # Move pointers
        slow = slow.next        # Slow pointer moves 1 step
        fast = fast.next.next   # Fast pointer moves 2 steps
    
    # If loop exits because slow == fast, there's a cycle
    return True

Alternative Implementation (Both Start at Head)

def hasCycle_v2(head):
    slow = fast = head
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    
    return False

Complexity Analysis

Time: - No cycle: Fast pointer takessteps to reach end
- Has cycle: Fast pointer catches slow withiniterations
Space:, only two pointers

Algorithm Visualization: The animation below demonstrates how fast and slow pointers detect cycles:

Why Does Fast Pointer Always Catch Slow?

Mathematical proof:

Assume cycle length is, and after slow pointer enters cycle, it has movedsteps. Fast pointer issteps behind slow pointer ().

Each iteration, fast pointer closes gap by 1 step
Distance changes fromto
After at mostiterations, distance becomes 0 (they meet)

Visualization: Think of clock hands - minute hand (fast) eventually laps hour hand (slow).

Advanced: Find Cycle Entry Point

Problem: Return the node where cycle begins.

Algorithm: 1. Use fast-slow pointers to find meeting point 2. Move one pointer back to head 3. Both pointers move at same speed, they'll meet at cycle entry

def detectCycle(head):
    if not head or not head.next:
        return None
    
    # Phase 1: Detect cycle
    slow = fast = head
    has_cycle = False
    
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            has_cycle = True
            break
    
    if not has_cycle:
        return None
    
    # Phase 2: Find entry point
    slow = head
    while slow != fast:
        slow = slow.next
        fast = fast.next
    
    return slow

Why does this work?

Let:

Distance from head to cycle entry:
Distance from cycle entry to meeting point:
Distance from meeting point back to cycle entry:When they meet:
Slow pointer traveled:
Fast pointer traveled:Since fast is 2x slow: So starting from head and meeting point, moving at same speed, they meet at entry!

LeetCode 202: Happy Number

Problem Statement

Write an algorithm to determine if a numberis "happy": repeatedly replacewith the sum of the squares of its digits. If this process results in 1, the number is happy. If it enters an infinite loop that doesn't include 1, it's not happy.

Example:

Input: n = 19
Output: true
Explanation: - - - -

Core Insight

Key observation: If not happy, numbers enter a cycle.

Convert to cycle detection:

Use fast-slow pointers to detect cycle
If fast pointer reaches 1, it's happy
If fast and slow meet (not at 1), it's not happy

Python Implementation

def getNext(n):
    """Calculate sum of squares of digits"""
    total = 0
    while n > 0:
        digit = n % 10
        total += digit ** 2
        n //= 10
    return total

def isHappy(n):
    slow = n
    fast = getNext(n)
    
    while fast != 1 and slow != fast:
        slow = getNext(slow)          # Slow moves 1 step
        fast = getNext(getNext(fast))  # Fast moves 2 steps
    
    return fast == 1

Complexity Analysis

Time: - Each operation roughly decreases number size (digit count decreases)
- Worst case enters cycle, cycle length is bounded
Space:

Why Not Use Hash Set?

Hash set approach:

def isHappy_hash(n):
    seen = set()
    while n != 1 and n not in seen:
        seen.add(n)
        n = getNext(n)
    return n == 1

Comparison:

Method	Time	Space	Advantage
Hash set			Simpler code
Fast-slow			Optimal space

Interview tip: Mention hash set first, then offer fast-slow as space optimization.

Pattern 3: Sliding Window

Core Characteristics

Maintain a variable-length or fixed-length window
Left pointer and right pointer define window boundaries
Dynamically adjust window size to satisfy conditions

Real-World Analogy

Reading a long book to find shortest consecutive chapters containing all key plot points:

Right pointer: Keep turning pages forward, expanding range
Left pointer: Once condition met, shrink from beginning
Eventually find shortest chapter sequence satisfying condition

LeetCode 3: Longest Substring Without Repeating Characters

Problem Statement

Given a string s, find the length of the longest substring without repeating characters.

Example:

Input: s = "abcabcbb"
Output: 3
Explanation: Longest substring is "abc"

Constraints:

- - s consists of English letters, digits, symbols and spaces

Core Insight

Sliding window + Hash set: 1. Use hash set to track characters in current window 2. Right pointer expands window, adding new character 3. If duplicate found, left pointer shrinks window until no duplicates 4. Track maximum window length throughout process

Python Implementation

def lengthOfLongestSubstring(s):
    # Use set to track characters in current window (O(1) lookup)
    char_set = set()
    left = 0  # Left pointer: window left boundary
    max_length = 0  # Track longest substring length
    
    # Right pointer: continuously expand window
    for right in range(len(s)):
        # If character at right pointer already in window (duplicate)
        # Need to shrink left boundary until no duplicates
        while s[right] in char_set:
            # Remove character at left pointer from set
            char_set.remove(s[left])
            # Move left pointer right, shrink window
            left += 1
        
        # Add current character to set (window)
        char_set.add(s[right])
        
        # Update maximum length
        # right - left + 1 is current window length
        max_length = max(max_length, right - left + 1)
    
    return max_length

Complexity Analysis

Time: - Each character visited at most twice (once by right, once by left)
Space: -is charset size (e.g., ASCII is 128)

Step-by-Step Example

Input: s = "abcabcbb"

Step	`right`	`s[right]`	`char_set`	Window	`max_length`	Action
0	0	`'a'`	`{'a'}`	`"a"`	1	Add `'a'`
1	1	`'b'`	`{'a','b'}`	`"ab"`	2	Add `'b'`
2	2	`'c'`	`{'a','b','c'}`	`"abc"`	3	Add `'c'`
3	3	`'a'`	`{'b','c'}`	`"bca"`	3	Remove `'a'`, add `'a'`
4	4	`'b'`	`{'c','a'}`	`"cab"`	3	Remove `'b'`, add `'b'`
5	5	`'c'`	`{'a','b'}`	`"abc"`	3	Remove `'c'`, add `'c'`
6	6	`'b'`	`{'a','c'}`	`"cb"`	3	Remove `'b'`, add `'b'`
7	7	`'b'`	`{'c'}`	`"b"`	3	Remove `'a'`, `'b'`, add `'b'`

Output: 3

Optimization: Hash Map with Index

Further optimization: Instead of removing characters one by one, jump directly to position after duplicate.

def lengthOfLongestSubstring_optimized(s):
    char_index = {}  # character -> most recent index
    left = 0
    max_length = 0
    
    for right in range(len(s)):
        if s[right] in char_index:
            # Jump to position after duplicate
            left = max(left, char_index[s[right]] + 1)
        
        char_index[s[right]] = right
        max_length = max(max_length, right - left + 1)
    
    return max_length

Why max(left, ...)?

Prevents left pointer from moving backward. Example: s = "abba"

At right = 3, encounter second 'a'
char_index['a'] = 0, naively would set left = 1
But left might already be at 2 (due to second 'b')
So need left = max(left, 1) to avoid regression

LeetCode 76: Minimum Window Substring

Problem Statement

Given strings s and t, return the minimum window substring of s containing all characters of t. If no such substring exists, return "".

Example:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"

Constraints:

- - s and t consist of English letters - Follow-up:time complexity

Core Insight

Sliding window + Frequency counting: 1. Use hash map to count frequency of each character in t 2. Expand right boundary, adding characters to window 3. When window contains all required characters, shrink left boundary to find minimum 4. Track minimum window's starting position and length

Python Implementation

from collections import Counter, defaultdict

def minWindow(s, t):
    # Edge case handling
    if not s or not t:
        return ""
    
    # Count frequency of each character in t (target frequency)
    target_count = Counter(t)
    # required: number of unique characters that need to satisfy frequency requirement
    # Example t="AAB", need 'A':2, 'B':1 satisfied, required=2
    required = len(target_count)  # Number of unique characters needed
    
    # Character frequency statistics in current window
    window_count = defaultdict(int)
    # formed: number of characters in window that already satisfy target frequency
    # When formed == required, window contains all required characters
    formed = 0  # Number of unique characters with desired frequency in window
    
    left = 0  # Left pointer: window left boundary
    min_len = float('inf')  # Minimum window length
    min_left = 0  # Starting position of minimum window
    
    # Right pointer: continuously expand window
    for right in range(len(s)):
        char = s[right]
        # Add character at right pointer to window
        window_count[char] += 1
        
        # Check if current character satisfies target frequency requirement
        # Only when frequency exactly equals target frequency does formed increase
        # If frequency exceeds target, formed doesn't increase (already satisfied)
        if char in target_count and window_count[char] == target_count[char]:
            formed += 1
        
        # When window contains all required characters, attempt to shrink window
        # Use while instead of if, because may shrink multiple times
        while left <= right and formed == required:
            # Update minimum window (if current window is smaller)
            if right - left + 1 < min_len:
                min_len = right - left + 1
                min_left = left  # Record starting position
            
            # Remove character at left pointer (shrink window)
            char = s[left]
            window_count[char] -= 1
            
            # If after removal, character's frequency below target frequency
            # formed decreases by 1, window no longer satisfies condition
            if char in target_count and window_count[char] < target_count[char]:
                formed -= 1
            
            # Move left pointer right, shrink window
            left += 1
    
    # If minimum window found, return substring; otherwise return empty string
    return "" if min_len == float('inf') else s[min_left:min_left + min_len]

Complexity Analysis

Time: -, - Each character visited at most twice
Space: - Hash maps store character frequencies

Deep Dive

Algorithm Principle: Why Does This Algorithm Work?

Core Idea: Maintain a window containing all required characters. Use formed variable to track number of characters in window that satisfy target frequency. Only when formed == required does window contain all required characters.

Why use formed instead of directly comparing frequency maps: - Directly comparing two frequency maps requirestime (is character set size) - Using formed counter, each update is - Total time optimized fromto Contraction condition: Only shrink when formed == required, ensuring window always contains all required characters.

Time Complexity Proof: Why O(m+n)?

Build target frequency map: Traverse t,
Main loop: Traverse s,
Inner while: Although nested, each character visited at most once by left pointer
Total time: Key: Left pointer monotonically increases, never moves backward, guaranteeing linear time complexity.

Space Optimization: Is There a More Space-Efficient Method?

Method 1: Use Array Instead of Dictionary (Only for Small Character Set) For lowercase English letters (26), can use array:

target_count = [0] * 26
for c in t:
    target_count[ord(c) - ord('a')] += 1
# Space: O(1) instead of O(n)

Method 2: Reuse Variables - Can reuse char variable, but space savings negligible

Trade-off: For general character sets, using Counter and defaultdict is reasonable.

Common Mistakes Analysis

Mistake Type	Wrong Code	Problem	Correct Approach
Wrong formed update	`if char in target_count: formed += 1`	Frequency may exceed target	Check `==` not `>=`
Use if instead of while	`if formed == required: left += 1`	Only shrink once, may not be minimum	Use `while` to keep shrinking
Forget to record start	Only record length	Cannot return substring	Also record `min_left`

Variant Extensions

Permutation in String: Find shortest substring containing permutation of target string
Find All Anagrams: Find all starting positions of substrings satisfying condition
Minimum Window Subsequence: Subsequence instead of substring (more complex)

Key Implementation Details

Detail 1: When to Increment `formed`

# ❌ Wrong: Only check existence
if char in target_count:
    formed += 1

# ✅ Correct: Check frequency matches
if char in target_count and window_count[char] == target_count[char]:
    formed += 1

Detail 2: Shrinking Condition

# ❌ Wrong: Shrink only once
if formed == required:
    left += 1

# ✅ Correct: Keep shrinking while condition holds
while left <= right and formed == required:
    # ...
    left += 1

Detail 3: Updating Minimum

# Track both start position and length
min_len = right - left + 1
min_left = left

# Final answer
s[min_left:min_left + min_len]

Two Pointers vs Hash Table: When to Choose?

Comparison Table

Dimension	Two Pointers	Hash Table
Time Complexity	or
Space Complexity
Applicable Scenarios	Sorted array, linked list, subarray	Unsorted array, frequency counting
Code Complexity	More boundary conditions	Relatively simpler
Requires Sorting	Usually yes	No

Selection Guidelines

Prefer Two Pointers When

Array is sorted or can be sorted
Need in-place operation (space)
Problem involves contiguous subarray/substring
Need to find specific element pairs (not just existence check)

Prefer Hash Table When

Array is unsorted and can't be sorted (need to preserve indices)
Need fast lookup for value existence
Frequency counting problems
Space is not a limiting factor

Hybrid Approach

Some problems benefit from combining both techniques:

Example: Sliding window (two pointers) + Hash table (frequency counting)

Minimum Window Substring
Permutation in String
Find All Anagrams in a String

Interview Communication Techniques

Template 1: Identifying Two-Pointer Opportunity

"I notice this problem involves sorted array/subarray/pairing, which suggests two pointers. I'll use left-right/fast-slow pointers with [specific movement strategy] to optimize the brute-forcesolution."

Template 2: Explaining Movement Logic

"When condition A holds, I move the left pointer to shrink window/decrease value; when condition B holds, I move the right pointer to expand window/increase value. This ensures each element is visited at most constant times, achievingcomplexity."

Template 3: Handling Edge Cases

"I need to check several edge cases: empty array, single element, all elements identical. For boundary conditions, I'll ensure pointers don't go out of bounds and correctly handle logic when they meet."

Template 4: Optimization Explanation

"The brute force is; two pointers optimize to. Though sorting increases complexity to, for large datasets this is still significant improvement. Space complexity is(excluding sorting stack space), better than hash table's."

Common Mistakes & Debugging Checklist

Mistake 1: Pointer Out of Bounds

# ❌ May go out of bounds
while left < len(nums) and right < len(nums):
    # ...
    right += 1

# ✅ Check right + 1
while left < right and right + 1 < len(nums):

Mistake 2: Infinite Loop

# ❌ Forgot to move pointers
while left < right:
    if condition:
        # Processing logic
        pass  # No pointer movement!

# ✅ Ensure every branch moves pointers
while left < right:
    if condition:
        left += 1
    else:
        right -= 1

Mistake 3: Boundary Condition Handling

# ❌ Inappropriate handling when pointers meet
while left < right:
    # ...

# ✅ Decide < or <= based on problem
while left <= right:  # Allow pointers to overlap
    # ...

Debugging Checklist

✅ Before coding: 1. Determine pattern (collision/fast-slow/sliding window) 2. Clarify initial position of each pointer 3. Define movement and termination conditions 4. Consider edge cases (empty, single element, all same)

✅ After coding: 1. Manually simulate each step with small example 2. Print pointer positions and window contents each iteration 3. Test empty input, single element, boundary values 4. Check handling when pointers meet 5. Verify complexity meets expectation

Practice Problems (10 Recommended)

Collision Pointers

Two Sum II - Input Array Is Sorted (LeetCode 167) Easy
Container With Most Water (LeetCode 11) ← Covered Medium
3Sum (LeetCode 15) ← Covered Medium

Fast-Slow Pointers

Linked List Cycle (LeetCode 141) ← Covered Easy
Linked List Cycle II (LeetCode 142) Medium
Happy Number (LeetCode 202) ← Covered Easy

Sliding Window

Longest Substring Without Repeating Characters (LeetCode 3) ← Covered Medium
Minimum Window Substring (LeetCode 76) ← Covered Hard
Minimum Size Subarray Sum (LeetCode 209) Medium
Permutation in String (LeetCode 567) Medium

Summary: Two Pointers Essence in One Page

Three Pattern Quick Reference

Pattern	Mnemonic	Typical Problems
Collision Pointers	Squeeze from ends, adjust sum/diff	Container With Water, 3Sum
Fast-Slow Pointers	Speed differential, detect cycles	List Cycle, Happy Number
Sliding Window	Expand right shrink left, dynamic interval	Longest Substring, Min Window

When to Use?

Consider two pointers when seeing these keywords:

"Sorted array"
"Contiguous subarray/substring"
"Pairing/triplets"
"Linked list cycle/middle"
"space"

Common Pitfalls

Pointer out of bounds: Always check right + 1 < len
Infinite loop: Every branch must move pointer
Boundary confusion: < vs <=, depends on problem
Duplicate elements: Skip duplicates after sorting

Interview Golden Phrase

"This problem's brute force is, but I notice [sorted/subarray/pairing] characteristics, which suggests [collision/fast-slow/sliding window] two pointers can optimize to, withspace complexity. This is the optimal balance of time and space."

Memory Cheat

Collision squeezes adjust sum/diff, fast-slow catches finds cycles, sliding window expands shrinks seeks intervals, two pointers clever saves space!

What's Next?

In LeetCode (3) Linked List Operations, we'll dive into:

Reverse Linked List: Iterative vs Recursive
Merge Lists: Applying merge sort thinking
List Sorting:timespace
Fast-Slow Advanced: Find middle, k-th from end

Thought question: How to perform merge sort on linked list inspace? Answer in next part!

Books:
- "Cracking the Coding Interview" (Chapter 2: Linked Lists & Two Pointers)
- "Introduction to Algorithms" (Chapter 10: Basic Data Structures)
Papers:
- Floyd's Cycle Detection Algorithm (1967)
Visualization:
- VisuAlgo - Linked Lists & Two Pointers: https://visualgo.net/en/list
LeetCode: Two Pointers tag (150+ problems)

Two pointers isn't a fancy trick — it's deep understanding of data structure properties. Master it, and you'll solve many seemingly complex problems in linear time!

❓ Q&A: Two Pointers Interview Tips

Q1: Fast/Slow Pointer vs Opposite-End Pointers - When to Use Each?

Answer: The choice depends on the problem structure and what you're trying to achieve.

Fast-Slow Pointers (different speeds):

Use when: Working with linked lists, cycle detection, finding middle elements, or problems where you need to track relative positions
Key insight: The speed differential creates a "chasing" effect that naturally detects cycles or finds specific positions
Example: Linked List Cycle - fast pointer moves 2 steps, slow moves 1 step. If there's a cycle, fast will eventually catch slow.

# Fast-slow pattern
slow = fast = head
while fast and fast.next:
    slow = slow.next      # Move 1 step
    fast = fast.next.next # Move 2 steps
    if slow == fast:
        return True  # Cycle detected

Opposite-End Pointers (collision pointers):

Use when: Working with sorted arrays, finding pairs/triplets, or problems where you can make decisions based on both ends
Key insight: Starting from both ends allows you to eliminate half the search space with each comparison
Example: Two Sum II - if sum too small, move left pointer right; if too large, move right pointer left.

# Collision pattern
left, right = 0, len(nums) - 1
while left < right:
    if nums[left] + nums[right] == target:
        return [left, right]
    elif nums[left] + nums[right] < target:
        left += 1  # Need larger sum
    else:
        right -= 1  # Need smaller sum

Decision Tree:

Linked list problem → Fast-slow pointers
Sorted array + pairs/triplets → Collision pointers
Need to find middle → Fast-slow pointers
Need to optimize sum/difference → Collision pointers

Complexity: Both achievetime andspace, but fast-slow is more intuitive for linked lists while collision is more natural for arrays.

Q2: Sliding Window vs Two Pointers - What's the Difference?

Answer: Sliding window is actually a specialized form of two pointers optimized for contiguous subarray/substring problems.

Two Pointers (General):

Pointers can move independently or converge
Used for: pairing, cycle detection, finding specific positions
Movement: Often moves based on comparison (e.g., sum too small/large)

Sliding Window:

Maintains a contiguous interval between pointers
Used for: subarray/substring problems with constraints
Movement: Right pointer expands window, left pointer shrinks when condition met
Key characteristic: Window size can be fixed or variable

Visual Comparison:

Two Pointers (Collision):
[1, 2, 3, 4, 5, 6]
 ↑              ↑
left          right
(converging toward center)

Sliding Window:
[1, 2, 3, 4, 5, 6]
 ↑  ↑
left right
(window expands right, shrinks left)

When to Use Sliding Window:

Keywords: "subarray", "substring", "contiguous", "window"
Need to track elements within a range
Problem asks for minimum/maximum length satisfying condition

Example: Longest Substring Without Repeating Characters

Sliding window: Maintain window of unique characters
Not collision pointers: We're not converging from ends
Not fast-slow: Both pointers move forward, just at different rates

Complexity: Sliding window typically achievestime since each element is visited at most twice (once by each pointer).

Q3: How to Avoid Infinite Loops in Two-Pointer Algorithms?

Answer: Ensure every code path moves at least one pointer and termination condition is always reachable.

Common Causes:

Forgotten pointer movement:

# ❌ BAD: Infinite loop risk
while left < right:
    if nums[left] + nums[right] == target:
        # Found solution, but forgot to move pointers!
        pass

# ✅ GOOD: Always move pointers
while left < right:
    if nums[left] + nums[right] == target:
        result.append([left, right])
        left += 1      # Must move!
        right -= 1     # Must move!
    elif nums[left] + nums[right] < target:
        left += 1
    else:
        right -= 1

Termination condition never met:

# ❌ BAD: Condition might never be false
while True:
    if some_condition:
        break  # But what if condition never becomes true?

# ✅ GOOD: Explicit termination
while left < right:  # Natural termination when pointers meet
    # ... logic that guarantees left or right moves

Pointer movement in wrong direction:

# ❌ BAD: Pointers moving toward each other but logic prevents meeting
while left < right:
    if condition:
        left += 1
    else:
        left += 1  # Both branches move same pointer!

# ✅ GOOD: At least one pointer always moves toward the other
while left < right:
    if condition:
        left += 1   # Moves toward right
    else:
        right -= 1  # Moves toward left

Debugging Checklist:

✅ Every if/elif/else branch moves at least one pointer
✅ Termination condition (left < right or left <= right) will eventually be false
✅ Pointer movements are in correct direction (converging, not diverging)
✅ No early returns that skip pointer updates

Test Cases to Catch Infinite Loops:

Empty array: []
Single element: [1]
All elements identical: [2, 2, 2, 2]
Edge case where pointers meet immediately

Q4: What Are Common Edge Cases in Two-Pointer Problems?

Answer: Edge cases often involve boundary conditions and special input patterns. Always test these systematically.

Critical Edge Cases:

Empty Array:

def twoSum(nums, target):
    if not nums:  # ✅ Check first!
        return []
    left, right = 0, len(nums) - 1
    # ... rest of logic

Single Element:

# For collision pointers: left == right immediately
# For fast-slow: fast.next might be None immediately
def hasCycle(head):
    if not head or not head.next:  # ✅ Single node can't have cycle
        return False

All Elements Identical:

# Example: nums = [2, 2, 2, 2], target = 4
# Need to handle duplicates correctly
while left < right:
    if nums[left] + nums[right] == target:
        result.append([left, right])
        # ✅ Skip duplicates
        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

Pointers Meet at Boundary:

# What if solution is at indices [0, 1] or [n-2, n-1]?
# Ensure loop handles first and last elements
while left < right:  # ✅ Allows left=0, right=1
    # ... logic

No Valid Solution:

# Example: Sorted array, but no pair sums to target
# Should return empty result, not crash
def twoSum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        # ... logic
    return []  # ✅ No solution found

Array with Duplicates (3Sum/4Sum):

# Must skip duplicates at THREE levels:
# 1. First number
if i > 0 and nums[i] == nums[i-1]:
    continue
# 2. Second number (left pointer)
while left < right and nums[left] == nums[left+1]:
    left += 1
# 3. Third number (right pointer)
while left < right and nums[right] == nums[right-1]:
    right -= 1

Edge Case Testing Template:

test_cases = [
    [],                    # Empty
    [1],                   # Single element
    [1, 1],                # Two identical
    [1, 1, 1, 1],          # All identical
    [1, 2, 3, 4, 5],       # Normal case
    [1, 2],                # Minimum size
    [1] * 10000,           # Large input, all same
]

Interview Tip: Always mention edge cases before coding: "I'll need to handle empty array, single element, and duplicate elements. Let me code the main logic first, then add these checks."

Q5: Two Pointers in Linked Lists vs Arrays - Key Differences?

Answer: The fundamental difference is random access vs sequential access, which affects how pointers move and what operations are possible.

Arrays (Random Access):

Can jump to any index: nums[i], nums[j]
Pointers are indices: left = 0, right = len(nums) - 1
Can move backward: right -= 1
Can calculate distance: right - left
Typical patterns: Collision pointers, sliding window

# Array: Easy to move in both directions
left, right = 0, len(nums) - 1
while left < right:
    # Can access nums[left] and nums[right] directly
    if nums[left] + nums[right] == target:
        return [left, right]
    left += 1   # Move forward
    right -= 1  # Move backward

Linked Lists (Sequential Access):

Must traverse from head: node = node.next
Pointers are node references: slow = head, fast = head
Can only move forward: node = node.next (no node.prev in singly-linked list)
Cannot calculate distance easily (need to traverse)
Typical patterns: Fast-slow pointers, cycle detection

# Linked list: Can only move forward
slow = fast = head
while fast and fast.next:
    slow = slow.next      # Must follow .next
    fast = fast.next.next # Can't jump to arbitrary position
    if slow == fast:
        return True

Key Differences Table:

Aspect	Arrays	Linked Lists
Access Pattern	Random (O(1))	Sequential (O(n))
Pointer Type	Integer indices	Node references
Movement	Bidirectional	Forward only (singly-linked)
Distance Calculation	`right - left`	Must traverse
Common Pattern	Collision pointers	Fast-slow pointers
Boundary Check	`left < len(nums)`	`node is not None`

When Arrays Are Better:

Need to compare elements at both ends
Problem requires sorting (arrays easier to sort)
Need to calculate distances or indices

When Linked Lists Are Better:

Problem involves cycles (fast-slow naturally detects)
Need to find middle without knowing length
Dynamic size (insertions/deletions)

Hybrid Approach Example: Some problems convert linked list to array first:

# Convert to array, then use collision pointers
def isPalindrome(head):
    values = []
    while head:
        values.append(head.val)
        head = head.next
    # Now use array two pointers
    left, right = 0, len(values) - 1
    while left < right:
        if values[left] != values[right]:
            return False
        left += 1
        right -= 1
    return True

Complexity Trade-off: Converting to array usesextra space but makes two-pointer logic simpler. Sometimes worth it for code clarity.

Q6: What Is the Three Pointers Technique?

Answer: Three pointers extend two-pointer logic to handle three-way partitioning or problems requiring three simultaneous references.

Common Use Cases:

Dutch National Flag Problem (3-way partition):

# Sort array with three colors: 0 (red), 1 (white), 2 (blue)
def sortColors(nums):
    # Three pointers:
    # left: boundary of 0s (everything before left is 0)
    # right: boundary of 2s (everything after right is 2)
    # curr: current element being processed
    left = curr = 0
    right = len(nums) - 1
    
    while curr <= right:
        if nums[curr] == 0:
            nums[left], nums[curr] = nums[curr], nums[left]
            left += 1
            curr += 1
        elif nums[curr] == 2:
            nums[curr], nums[right] = nums[right], nums[curr]
            right -= 1
            # Don't increment curr! Need to check swapped element
        else:  # nums[curr] == 1
            curr += 1

Visualization:

Initial: [2, 0, 2, 1, 1, 0]
         ↑  ↑           ↑
        left curr      right

After:   [0, 0, 1, 1, 2, 2]
              ↑  ↑
            left right
            (curr finished)

Partition Array (pivot-based):

# Partition so elements < pivot on left, = pivot in middle, > pivot on right
def partition(nums, pivot):
    left = curr = 0
    right = len(nums) - 1
    
    while curr <= right:
        if nums[curr] < pivot:
            nums[left], nums[curr] = nums[curr], nums[left]
            left += 1
            curr += 1
        elif nums[curr] > pivot:
            nums[curr], nums[right] = nums[right], nums[curr]
            right -= 1
        else:
            curr += 1

4Sum Problem (nested two pointers):

# Fix two numbers, then use two pointers for remaining two
def fourSum(nums, target):
    nums.sort()
    result = []
    n = len(nums)
    
    for i in range(n - 3):  # First pointer
        for j in range(i + 1, n - 2):  # Second pointer
            left = j + 1    # Third pointer
            right = n - 1   # Fourth pointer
            
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    result.append([nums[i], nums[j], nums[left], nums[right]])
                    # Skip duplicates...
                elif total < target:
                    left += 1
                else:
                    right -= 1

Key Insight: Three pointers often maintain three regions:

Region 1: Elements processed and placed correctly (before left)
Region 2: Elements being processed (left to curr)
Region 3: Elements processed and placed correctly (after right)

Complexity: Stilltime,space - just more pointers to manage.

When to Use:

Problem requires three-way partitioning
Need to track three boundaries simultaneously
Extending two-pointer logic to handle three elements (like 3Sum → 4Sum)

Q7: Two Pointers with Sorting - What Are the Trade-offs?

Answer: Sorting enables two-pointer techniques but addspreprocessing cost. The trade-off is usually worth it for space optimization.

Trade-off Analysis:

Without Sorting (Hash Table Approach):

# Two Sum - unsorted array
def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i

- Time:

- Space:

for hash table - Preserves: Original indices

With Sorting (Two Pointers):

# Two Sum II - sorted array
def twoSum(nums, target):
    nums.sort()  # O(n log n)
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == target:
            return [left, right]  # But these are NEW indices after sort!
        elif current_sum < target:
            left += 1
        else:
            right -= 1

- Time:

for sorting +

for two pointers =

- Space:

extra (excluding sorting stack space

) - Loses: Original indices (unless you store them)

When Sorting Is Worth It:

✅ Use sorting + two pointers when:

Problem asks for values, not indices (like 3Sum, 4Sum)
Space is constrained (vsmatters)
Problem requires multiple queries (sort once, query many times)
Need to find all pairs/triplets (hash table gets complex)

❌ Avoid sorting when:

Problem requires original indices (Two Sum original)
Array is already sorted (use two pointers directly!)
Single query and space isn't concern (hash table simpler)

Hybrid Approach (Best of Both Worlds):

# Store original indices before sorting
def twoSumWithIndices(nums, target):
    indexed = [(nums[i], i) for i in range(len(nums))]
    indexed.sort(key=lambda x: x[0])  # Sort by value
    
    left, right = 0, len(indexed) - 1
    while left < right:
        current_sum = indexed[left][0] + indexed[right][0]
        if current_sum == target:
            return [indexed[left][1], indexed[right][1]]  # Original indices!
        elif current_sum < target:
            left += 1
        else:
            right -= 1

- Time:

- Space:

for storing indices - Benefit: Gets two-pointer efficiency + preserves indices

Complexity Comparison:

Approach	Time	Space	Preserves Indices
Hash Table			✅ Yes
Sort + Two Pointers			❌ No
Sort + Store Indices			✅ Yes

Interview Communication: > "I can solve this with a hash table intime andspace, which is optimal for time. Alternatively, I could sort first and use two pointers fortime butspace. Since this problem asks for values not indices, I'll go with sorting + two pointers to optimize space."

Q8: How to Optimize Space Complexity with Two Pointers?

Answer: Two pointers naturally achievespace by using only pointer variables instead of auxiliary data structures. Key: avoiding hash tables, arrays, or recursion stacks.

Space Optimization Techniques:

Replace Hash Table with Two Pointers:

# ❌ Hash table: O(n) space
def hasDuplicate(nums):
    seen = set()  # O(n) space
    for num in nums:
        if num in seen:
            return True
        seen.add(num)
    return False

# ✅ Two pointers (if sorted): O(1) space
def hasDuplicate(nums):
    nums.sort()  # In-place, O(log n) stack space
    for i in range(len(nums) - 1):
        if nums[i] == nums[i+1]:  # Adjacent comparison
            return True
    return False

In-Place Array Modification:

# Remove duplicates in-place
def removeDuplicates(nums):
    if not nums:
        return 0
    
    # Two pointers: write pointer and read pointer
    write = 0  # Position to write next unique element
    for read in range(1, len(nums)):
        if nums[read] != nums[write]:
            write += 1
            nums[write] = nums[read]  # In-place modification
    return write + 1

Space:(only two integer pointers)
Alternative: Create new array →space

Avoid Recursion Stack:

# ❌ Recursive: O(n) stack space
def reverseList(head):
    if not head or not head.next:
        return head
    new_head = reverseList(head.next)  # Recursion stack
    head.next.next = head
    head.next = None
    return new_head

# ✅ Iterative two pointers: O(1) space
def reverseList(head):
    prev = None
    curr = head
    while curr:
        next_temp = curr.next
        curr.next = prev
        prev = curr
        curr = next_temp
    return prev

Sliding Window Without Hash Table (when possible):

# For problems with limited character set, use array instead of hash map
def lengthOfLongestSubstring(s):
    # ASCII has 128 characters, so array[128] is O(1) space
    # vs hash map which is O(min(n, 128)) but with overhead
    char_count = [0] * 128  # Fixed size, O(1) space
    left = 0
    max_len = 0
    
    for right in range(len(s)):
        char_count[ord(s[right])] += 1
        
        # Shrink window if duplicate
        while char_count[ord(s[right])] > 1:
            char_count[ord(s[left])] -= 1
            left += 1
        
        max_len = max(max_len, right - left + 1)
    
    return max_len

Space Complexity Breakdown:

Technique	Space Complexity	Notes
Two pointers (basic)		Only pointer variables
Two pointers + sorting		Recursive sort stack space
Two pointers + hash table		Defeats space optimization
Sliding window + array		= character set size (often constant)
Sliding window + hash map		= character set size

WhenSpace Matters:

Memory-constrained environments (embedded systems)
Large datasets whereextra space is prohibitive
Interview optimization (shows understanding of trade-offs)
In-place algorithms required by problem statement

Trade-off Awareness: Sometimesspace comes at cost:

Sorting requirement: Addstime preprocessing
Code complexity: Two pointers can be trickier than hash table
Index preservation: May lose original positions

Interview Tip: Always mention both approaches: > "I can solve this with a hash table intime andspace, or with two pointers after sorting intime butspace. Given the constraints [mention which], I'll choose [approach]."

Q9: Interview Communication Tips for Two-Pointer Problems

Answer: Effective communication demonstrates problem-solving process and trade-off awareness. Structure your explanation clearly.

Template 1: Problem Recognition: > "I notice this problem involves [sorted array / subarray / cycle detection], which suggests two pointers could optimize the brute-forcesolution. Let me think about which pattern fits best..."

Template 2: Pattern Selection: > "Given that [array is sorted / we need contiguous subarray / we're working with linked list], I'll use [collision pointers / sliding window / fast-slow pointers] because [specific reason]."

Template 3: Algorithm Explanation: > "I'll maintain two pointers: [left/right or slow/fast]. The [left/slow] pointer will [specific movement], and the [right/fast] pointer will [specific movement]. When [condition], I'll [action], which ensures [invariant/maintains correctness]."

Template 4: Complexity Analysis: > "Time complexity isbecause each element is visited at most [once/twice]. Space complexity issince we only use [number] pointer variables, compared to the hash table approach which would requirespace."

Template 5: Edge Cases: > "Before coding, I should handle: [1] empty input, [2] single element, [3] all elements identical, [4] no valid solution. Let me code the main logic first, then add these checks."

Template 6: Optimization Discussion: > "The brute force would beby checking all pairs. Two pointers reduce this toby [eliminating half the search space / visiting each element once]. Though we need to sort first (), for large inputs this is still better than."

Common Phrases to Use:

"I'll use a greedy approach where..."
"This maintains the invariant that..."
"Each iteration eliminates [portion] of remaining possibilities..."
"The key insight is that we can [decision] based on [comparison]..."

What Interviewers Want to Hear:

✅ Good Communication:

Explains why you chose two pointers
Mentions alternatives (hash table, brute force)
Discusses trade-offs (time vs space)
Identifies edge cases proactively
Walks through example step-by-step

❌ Poor Communication:

Jumps straight to code without explanation
Doesn't mention alternatives
Ignores edge cases until asked
Can't explain why algorithm is correct
Doesn't analyze complexity

Example Full Explanation: > "This is a classic two-pointer problem. The brute force would check all pairs intime. Since the array is sorted, I can use collision pointers starting from both ends. If the sum is too small, I move the left pointer right to increase it. If too large, I move the right pointer left to decrease it. This eliminates half the remaining pairs with each comparison, givingtime. Space issince we only use two pointers. Edge cases to consider: empty array, single element, and no valid solution. Let me code this..."

Body Language Tips:

Think out loud: Don't code silently
Draw diagrams: Visualize pointer movements
Ask clarifying questions: "Should I handle duplicates?" "Do you want indices or values?"
Test with example: Walk through small input manually

Red Flags to Avoid:

❌ "I'll just use two pointers" (too vague)
❌ Coding without explaining (interviewer can't follow)
❌ Ignoring follow-up questions
❌ Not testing edge cases

Q10: How to Debug Two-Pointer Algorithms?

Answer: Systematic debugging involves manual tracing, print statements, and systematic test cases. Most bugs come from boundary conditions or pointer movement logic.

Debugging Strategy:

Manual Step-by-Step Tracing:

# Example: Two Sum
nums = [2, 7, 11, 15], target = 9

# Trace each iteration:
# Iteration 1: left=0, right=3
#   nums[0] + nums[3] = 2 + 15 = 17 > 9
#   → Move right: right = 2
# Iteration 2: left=0, right=2
#   nums[0] + nums[2] = 2 + 11 = 13 > 9
#   → Move right: right = 1
# Iteration 3: left=0, right=1
#   nums[0] + nums[1] = 2 + 7 = 9 == target
#   → Return [0, 1] ✓

Add Print Statements:

def twoSum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        print(f"left={left}, right={right}, sum={current_sum}")  # Debug
        
        if current_sum == target:
            return [left, right]
        elif current_sum < target:
            left += 1
            print(f"Moving left to {left}")  # Debug
        else:
            right -= 1
            print(f"Moving right to {right}")  # Debug

Check Invariants:

# What should always be true?
def maxArea(height):
    left, right = 0, len(height) - 1
    max_area = 0
    
    while left < right:
        # Invariant: left < right (check this!)
        assert left < right, f"Invariant violated: left={left}, right={right}"
        
        width = right - left
        current_area = min(height[left], height[right]) * width
        max_area = max(max_area, current_area)
        
        if height[left] < height[right]:
            left += 1
        else:
            right -= 1
    
    return max_area

Test Edge Cases Systematically:

def test_twoSum():
    test_cases = [
        ([], 5, []),                    # Empty
        ([1], 1, []),                   # Single element
        ([1, 2], 3, [0, 1]),            # Two elements
        ([1, 1, 1], 2, [0, 1]),         # All same
        ([1, 2, 3, 4], 10, []),         # No solution
        ([1, 2, 3, 4], 7, [2, 3]),      # Normal case
    ]
    
    for nums, target, expected in test_cases:
        result = twoSum(nums, target)
        assert result == expected, f"Failed: {nums}, target={target}"
        print(f"✓ Passed: {nums}")

Common Bugs and Fixes:

Bug 1: Off-by-One Error:

# ❌ BAD: Might skip last element
for i in range(len(nums) - 1):
    if nums[i] + nums[i+1] == target:
        return [i, i+1]

# ✅ GOOD: Check boundary
for i in range(len(nums)):
    if i + 1 < len(nums) and nums[i] + nums[i+1] == target:
        return [i, i+1]

Bug 2: Pointer Not Moving:

# ❌ BAD: Infinite loop
while left < right:
    if nums[left] + nums[right] == target:
        # Forgot to move pointers!
        pass

# ✅ GOOD: Always move
while left < right:
    if nums[left] + nums[right] == target:
        return [left, right]
    elif nums[left] + nums[right] < target:
        left += 1
    else:
        right -= 1

Bug 3: Wrong Comparison:

# ❌ BAD: Moving wrong pointer
if nums[left] + nums[right] < target:
    right -= 1  # Wrong! Should move left

# ✅ GOOD: Move pointer that increases sum
if nums[left] + nums[right] < target:
    left += 1  # Increase sum

Debugging Checklist:

Print pointer values each iteration
Check termination condition will eventually be false
Verify pointer movements are correct direction
Test empty input, single element, edge cases
Manually trace through small example
Check array bounds before access
Verify invariants hold throughout loop

Interview Debugging Tips: 1. Don't panic: Bugs are normal, show debugging process 2. Explain your thinking: "I think the issue might be..." 3. Test incrementally: Add one test case at a time 4. Use examples: Walk through concrete input 5. Check assumptions: "I assumed the array was sorted, is that correct?"

🎓 Summary: Two Pointers Cheat Sheet

Quick Pattern Recognition

Problem Type	Pattern	Initialization	Movement Strategy
Sorted array pairs	Collision	`left=0, right=n-1`	Sum too small → `left++`, too large → `right--`
Linked list cycle	Fast-slow	`slow=fast=head`	`slow=slow.next`, `fast=fast.next.next`
Subarray/substring	Sliding window	`left=0, right=0`	Expand `right`, shrink `left` when condition met
Three-way partition	Three pointers	`left=curr=0, right=n-1`	Move `curr`, swap with `left` or `right`

Complexity Cheat Sheet

Pattern	Space	When Optimal
Collision pointers		Sorted array, pairing problems
Fast-slow pointers		Cycle detection, finding middle
Sliding window	or	Contiguous subarray problems
Sort + two pointers		When space optimization needed

Common Templates

Template 1: Collision Pointers

left, right = 0, len(nums) - 1
while left < right:
    # Process current pair
    if condition:
        # Found solution or update result
        left += 1
        right -= 1
    elif condition:
        left += 1
    else:
        right -= 1

Template 2: Fast-Slow Pointers

slow = fast = head
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        # Cycle detected or found position
        break

Template 3: Sliding Window

left = 0
for right in range(len(nums)):
    # Expand window: add nums[right]
    while condition_not_met:
        # Shrink window: remove nums[left]
        left += 1
    # Update result

Edge Cases Checklist

Debugging Quick Reference

Print pointers: print(f"left={left}, right={right}")
Check bounds: if left < len(nums) and right >= 0
Verify movement: Every branch moves at least one pointer
Test termination: Will left < right eventually be false?
Manual trace: Walk through small example step-by-step

Interview Phrases

"I notice [characteristic], which suggests two pointers..."
"The brute force is, but two pointers optimize to..."
"I'll use [pattern] because [reason]..."
"Edge cases to consider: [list]..."
"Time issince each element visited once, space is..."

Memory Mnemonics

Collision: "Squeeze from ends, adjust sum/diff"
Fast-slow: "Speed differential, detect cycles"
Sliding window: "Expand right, shrink left, dynamic interval"

Final Thought: Two pointers isn't about memorizing templates — it's about recognizing when eliminating half the search space or maintaining invariants can optimize your solution. Master the three core patterns, handle edge cases systematically, and communicate your reasoning clearly. With practice, you'll spot two-pointer opportunities instinctively!

Post title：LeetCode (2): Two Pointers - Collision, Fast-Slow & Sliding Window Complete Guide
Post author：Chen Kai
Create time：2023-04-18 00:00:00
Post link：https://www.chenk.top/en/leetcode-two-pointers/
Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.

Series Navigation

Core Concept of Two Pointers

Why Do We Need Two Pointers?

Three Core Patterns

Pattern 1: Collision Pointers

Core Characteristics

Real-World Analogy

LeetCode 11: Container With Most Water

Problem Analysis

Problem Statement

Core Insight

Python Implementation

Java Implementation

Complexity Analysis

Deep Dive

Algorithm Principle: Why Is the Greedy Strategy Correct?

Time Complexity Proof: Why O(n)?

Space Optimization: Is There a More Space-Efficient Method?

Common Mistakes Analysis

Variant Extensions

Why Is This Greedy Strategy Correct?

Mathematical Proof

Common Pitfalls

Pitfall 1: Try All Pairs

Pitfall 2: Move Taller Pointer

Pitfall 3: Sort First

LeetCode 15: 3Sum

Problem Analysis

Problem Statement

Core Insight

Python Implementation

Complexity Analysis

Deep Dive

Algorithm Principle: Why Does This Algorithm Work?

Time Complexity Proof: Why O(n ²)?

Space Optimization: Is There a More Space-Efficient Method?

Common Mistakes Analysis

Variant Extensions

Deduplication Strategy Explained

Dedup Point 1: First Number

Dedup Points 2 & 3: Second and Third Numbers

Optimization Techniques

Optimization 1: Early Termination

Optimization 2: Maximum Value Pruning

Optimization 3: Minimum Value Pruning

Extension: 4Sum, kSum

Pattern 2: Fast-Slow Pointers

Core Characteristics

Real-World Analogy

LeetCode 141: Linked List Cycle

Problem Statement

Core Insight: Floyd's Cycle Detection

Python Implementation

Alternative Implementation (Both Start at Head)

Complexity Analysis

Why Does Fast Pointer Always Catch Slow?

Advanced: Find Cycle Entry Point

LeetCode 202: Happy Number

Problem Statement

Core Insight

Python Implementation

Complexity Analysis

Why Not Use Hash Set?

Pattern 3: Sliding Window

Core Characteristics

Real-World Analogy

LeetCode 3: Longest Substring Without Repeating Characters

Problem Statement

Core Insight

Python Implementation

Complexity Analysis

Step-by-Step Example

Optimization: Hash Map with Index

LeetCode 76: Minimum Window Substring

Problem Statement

Core Insight

Python Implementation

Complexity Analysis

Deep Dive

Algorithm Principle: Why Does This Algorithm Work?

Detail 1: When to Increment `formed`