Sliding Window & Two Pointers Master Map 🎯¶

Overview¶

• Core Techniques
• Sliding Window (SubstringSlidingWindow API Kernel)
• Two Pointers (TwoPointersTraversal & FastSlowPointers & TwoPointerPartition)
• Use Cases
• Substring / subarray optimization
• In-place array modification
• Pair / k-sum / palindrome / merge
• Cycle detection
• Roadmaps
• Sliding Window: sliding_window_path
• Two Pointers: two_pointers_path
• General: neetcode_150, blind_75, grind_75, leetcode_top_100

Sliding Window Patterns 🔍¶

Core Concept¶

• API Kernel: SubstringSlidingWindow
• Maintain window [left, right] over sequence
• State: hash map / counters / running sum
• Invariant: property that must hold for current window
• Operations
• Expand: right++
• Contract: left++ while invariant violated (or while still valid, if minimizing)
• Complexity
• Time: \(O(n)\)
• Space: typically \(O(\sigma)\) or \(O(K)\)

Canonical Template¶

left = 0
state = init_state()
answer = init_answer()

for right, x in enumerate(seq):
    add(state, x)          # expand

    while invalid(state):  # or while valid(state) when minimizing
        remove(state, seq[left])
        left += 1

    answer = update(answer, left, right, state)
return answer

1. Unique Characters Window (Base) 🎓¶

• Pattern: sliding_window_unique
• Invariant: all chars in window are unique
• State: last_seen_index[char]
• Optimization: jump left instead of while-loop
• Problem:
• LeetCode 3 - Longest Substring Without Repeating Characters
• Snippet: 0003_base.md
• Family: substring_window
• Topics: string, hash_table, sliding_window
• Roadmaps: neetcode_150, blind_75, grind_75, leetcode_top_100, sliding_window_path
• ✅ Best first sliding window problem

2. At Most K Distinct Characters¶

• Pattern: sliding_window_at_most_k_distinct
• Invariant: #distinct_chars(window) ≤ K
• State: frequency map (char -> count)
• Contract: while len(freq) > K
• Problem:
• LeetCode 340 - Longest Substring with At Most K Distinct Characters
• Snippet: 0340_k_distinct.md
• Family: substring_window

3. Frequency Cover (Min / Exact Cover) 🧬¶

• Pattern: sliding_window_freq_cover
• Invariants:
• Cover: window has at least required freq for each char in t
• Often minimize length once cover is achieved
• State:
• need_frequency (from pattern string)
• have_frequency or window_frequency
• chars_satisfied vs chars_required
• Problems:
• LeetCode 76 - Minimum Window Substring
  • Min-length window containing all chars of t
• LeetCode 438 - Find All Anagrams in a String
  • All positions where window is an anagram of p
• LeetCode 567 - Permutation in String
  • Boolean: does any permutation of s1 appear in s2?
• Snippets:
• 0076_min_window.md
• 0438_anagrams.md
• 0567_permutation.md
• Families: substring_window
• Topics: string, hash_table, sliding_window

Sub-Variants¶

• Fixed-size window (anagram / permutation)
• Window size = len(pattern)
• Slide, maintain counts, compare or track chars_matched
• Variable-size window (min window)
• Expand until all requirements met
• Then contract while still valid to minimize

4. Cost-Bounded / Sum-Bounded Window 💰¶

• Pattern: sliding_window_cost_bounded
• Invariant: numeric property (sum / cost) respects constraint
• State: scalar sum or cost
• Example:
• LeetCode 209 - Minimum Size Subarray Sum
  • Invariant: window_sum ≥ target
  • Goal: minimize window length
• Snippet: 0209_min_subarray.md
• Family: substring_window
• Topics: array, sliding_window, prefix_sum, binary_search (alt solution)

5. Sliding Window Quick Comparison 📋¶

• Snippet: _comparison.md
• Table Summary

6. When to Use Sliding Window ❓¶

• Snippet: _decision.md
• ✅ Indicators
• Answer is a contiguous substring/subarray
• Want to minimize/maximize length/value
• Can incrementally update state when left/right move in \(O(1)\)
• ❌ Avoid when
• Need non-contiguous selection → DP / combinatorics
• State depends on global information → prefix sums + binary search, etc.
• Flow:
• Contiguous? → Yes → Incremental state? → Yes → Sliding window
• Roadmap: sliding_window_path

7. Sliding Window Templates Cheat Sheet¶

• Snippet: _templates.md
• Maximize variable window
• Minimize variable window
• Fixed-size window

Two Pointers Patterns ↔️¶

Core Concept¶

• Algorithm: two_pointers (technique)
• API Kernels:
• TwoPointersTraversal
• FastSlowPointers
• TwoPointerPartition
• MergeSortedSequences
• Sub-Patterns
• Opposite pointers
• Same-direction (reader/writer)
• Fast–slow (cycle / midpoint)
• Partition / Dutch flag
• Multi-sum enumeration
• Merge two sorted sequences

1. Opposite Pointers (Two-End) ⬅️➡️¶

• Patterns:
• two_pointer_opposite
• two_pointer_opposite_search
• two_pointer_opposite_palindrome
• two_pointer_opposite_maximize
• Initialize: left = 0, right = n-1
• Move:
• Based on comparison vs target or geometry
• Monotonic property required (often sorted array)
• Use Cases:
• Two-sum on sorted array
• Palindrome checks
• Maximize/minimize function of pair (like area)
• Problems:
• LeetCode 1 - Two Sum (here: pattern tagged but typical optimal uses hash map; opposite pointers after sorting is a variant)
• LeetCode 11 - Container With Most Water
• LeetCode 15 - 3Sum (inner loop)
• LeetCode 16 - 3Sum Closest
• LeetCode 125 - Valid Palindrome
• LeetCode 680 - Valid Palindrome II
• LeetCode 977 - Squares of a Sorted Array (from ends)
• Families:
• two_pointers_optimization
• multi_sum_enumeration
• palindrome_validation
• sequence_merge

2. Same-Direction Pointers (Reader/Writer) ✏️¶

• Patterns:
• two_pointer_same_direction
• two_pointer_writer_dedup
• two_pointer_writer_remove
• two_pointer_writer_compact
• Invariant: arr[0:write] holds all kept elements
• Use Cases:
• In-place deduplication
• Remove elements by condition
• Compaction (e.g., move zeroes)
• Problems:
• LeetCode 26 - Remove Duplicates from Sorted Array
• LeetCode 27 - Remove Element
• LeetCode 80 - Remove Duplicates from Sorted Array II
• LeetCode 283 - Move Zeroes
• Family: in_place_array_modification
• Topics: array, two_pointers

3. Fast–Slow Pointers (Cycle / Midpoint) 🐢🐇¶

• API Kernel: FastSlowPointers
• Patterns:
• fast_slow_cycle_detect
• fast_slow_cycle_start
• fast_slow_midpoint
• fast_slow_implicit_cycle
• Use Cases:
• Detect cycle in linked list
• Find start of cycle
• Find middle of list
• Implicit cycles in numeric sequences (e.g., happy number)
• Problems:
• LeetCode 141 - Linked List Cycle
• LeetCode 142 - Linked List Cycle II
• LeetCode 202 - Happy Number
• LeetCode 876 - Middle of the Linked List
• Families:
• linked_list_cycle
• linked_list_manipulation
• Topics: linked_list, two_pointers, math

4. Partitioning / Dutch National Flag 🚩¶

• API Kernel: TwoPointerPartition
• Patterns:
• dutch_flag_partition
• two_way_partition
• quickselect_partition
• Invariant:
• Maintain segments like < pivot | == pivot | > pivot
• Or separate by parity / sign
• Use Cases:
• 3-way partition (colors)
• Partition by parity
• Quickselect for kth element
• Problems:
• LeetCode 75 - Sort Colors
• LeetCode 905 - Sort Array By Parity
• LeetCode 922 - Sort Array By Parity II
• LeetCode 215 - Kth Largest Element in an Array (quickselect variant)
• Families:
• array_partition
• heap_priority (for heap alternative)
• Topics: array, sorting, two_pointers, heap

5. Multi-Sum Enumeration (3Sum, 4Sum) ➕¶

• Patterns:
• two_pointer_three_sum
• two_pointer_k_sum
• Strategy:
• Sort array
• Fix one or more indices with outer loops
• Use opposite pointers internally
• Deduplicate by skipping equal neighbors
• Problems:
• LeetCode 15 - 3Sum
• LeetCode 16 - 3Sum Closest
• Family: multi_sum_enumeration
• Topics: array, sorting, two_pointers

6. Merge Sorted Sequences 🔀¶

• API Kernel: MergeSortedSequences
• Patterns:
• merge_two_sorted_lists
• merge_two_sorted_arrays
• merge_sorted_from_ends
• Use Cases:
• Merge two sorted linked lists
• Merge arrays in-place or into new array
• Merge from both ends (e.g., squares)
• Problems:
• LeetCode 21 - Merge Two Sorted Lists
• LeetCode 88 - Merge Sorted Array
• LeetCode 977 - Squares of a Sorted Array
• LeetCode 4 - Median of Two Sorted Arrays (merge-based intuition + binary search)
• Families: sequence_merge, merge_sorted
• Topics: linked_list, array, two_pointers

7. Two Pointers Comparison & Decision 📊¶

• Snippets:
• _comparison.md
• _decision.md
• _templates.md
• _mapping.md
• Comparison Table (summary)

• Decision Hints
• Sorted & need pair/tuple? → Opposite / multi-sum
• In-place modification? → Same-direction writer
• Cycle / midpoint? → Fast–slow
• Partition by property? → Dutch flag / two-way partition
• Merge sorted data? → Merge pattern

Linked List Manipulation (Bonus) 🔗¶

• API Kernels:
• LinkedListInPlaceReversal
• FastSlowPointers
• Key Patterns:
• linked_list_full_reversal
• linked_list_partial_reversal
• linked_list_k_group_reversal
• Representative Problem:
• LeetCode 25 - Reverse Nodes in k-Group

BFS Grid Wavefront (Bonus Anchor) 🌊¶

• API Kernel: GridBFSMultiSource
• Pattern: grid_bfs_propagation
• Problem:
• LeetCode 994 - Rotting Oranges
• Family: graph_wavefront, matrix_traversal
• Shows contrast: when BFS is more natural than two pointers/sliding window

Learning Path Checklist ✅¶

Sliding Window Path¶

• LeetCode 3 - Longest Substring Without Repeating Characters
• LeetCode 340 - Longest Substring with At Most K Distinct Characters
• LeetCode 209 - Minimum Size Subarray Sum
• LeetCode 76 - Minimum Window Substring
• LeetCode 567 - Permutation in String
• LeetCode 438 - Find All Anagrams in a String

Two Pointers Path¶

• Opposite / Optimization
• LeetCode 11 - Container With Most Water
• LeetCode 125 - Valid Palindrome
• LeetCode 680 - Valid Palindrome II
• Same-Direction / In-place
• LeetCode 26 - Remove Duplicates from Sorted Array
• LeetCode 27 - Remove Element
• LeetCode 283 - Move Zeroes
• Fast–Slow
• LeetCode 141 - Linked List Cycle
• LeetCode 142 - Linked List Cycle II
• LeetCode 876 - Middle of the Linked List
• Partition / Dutch Flag
• LeetCode 75 - Sort Colors
• LeetCode 905 - Sort Array By Parity
• LeetCode 922 - Sort Array By Parity II
• Merge
• LeetCode 21 - Merge Two Sorted Lists
• LeetCode 88 - Merge Sorted Array
• LeetCode 977 - Squares of a Sorted Array

Interview-Oriented Highlights 💼¶

• Must-know Sliding Window:
• LeetCode 3, LeetCode 209, LeetCode 76, LeetCode 567, LeetCode 438
• Must-know Two Pointers:
• Opposite: LeetCode 11, LeetCode 15, LeetCode 125
• Writer: LeetCode 26, LeetCode 283
• Fast–Slow: LeetCode 141, LeetCode 142
• Partition: LeetCode 75, LeetCode 215
• Merge: LeetCode 21, LeetCode 88