Scribd
Upload
14 views5 pages

Two Pointer and Sliding Window Patterns

Uploaded by

mycollegelifeankit
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
14 views5 pages

Two Pointer and Sliding Window Patterns

Uploaded by

mycollegelifeankit
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Pattern Problems I.

Two Pointer Patterns Pattern 1: Two Pointers - Converging (Sorted Array Target
Sum) 1. Two Sum, 11. Container With Most Water, 15. 3Sum, 16. 3Sum Closest, 18. 4Sum, 167. Two
Sum II - Input Array Is Sorted, 349. Intersection of Two Arrays, 392. Is Subsequence, 881. Boats to
Save People, 977. Squares of a Sorted Array, 259. 3Sum Smaller Pattern 2: Two Pointers - Fast &
Slow (Cycle Detection) 141. Linked List Cycle, 202. Happy Number, 287. Find the Duplicate Number
Pattern 3: Two Pointers - Fixed Separation (Nth Node from End) 19. Remove Nth Node From End of
List, 876. Middle of the Linked List, 2095. Delete the Middle Node of a Linked List Pattern 4: Two
Pointers - In-place Array Modification 26. Remove Duplicates from Sorted Array, 27. Remove
Element, 75. Sort Colors, 80. Remove Duplicates from Sorted Array II, 283. Move Zeroes, 443. String
Compression, 905. Sort Array By Parity, 2337. Move Pieces to Obtain a String, 2938. Separate Black
and White Balls Pattern 5: Two Pointers - String Comparison with Backspaces 844. Backspace String
Compare Pattern 6: Two Pointers - Expanding From Center (Palindromes) 5. Longest Palindromic
Substring, 647. Palindromic Substrings Pattern 7: Two Pointers - String Reversal 151. Reverse Words
in a String, 344. Reverse String, 345. Reverse Vowels of a String, 541. Reverse String II

II. Sliding Window Patterns Pattern 8: Sliding Window - Fixed Size (Subarray Calculation) 346. Moving
Average from Data Stream, 643. Maximum Average Subarray I, 2985. Calculate Compressed Mean,
3254. Find the Power of K-Size Subarrays I, 3318. Find X-Sum of All K-Long Subarrays I Pattern 9:
Sliding Window - Variable Size (Condition-Based) 3. Longest Substring Without Repeating Characters,
76. Minimum Window Substring, 209. Minimum Size Subarray Sum, 219. Contains Duplicate II, 424.
Longest Repeating Character Replacement, 713. Subarray Product Less Than K, 904. Fruit Into
Baskets, 1004. Max Consecutive Ones III, 1438. Longest Continuous Subarray With Absolute Diff Less
Than or Equal to Limit, 1493. Longest Subarray of 1's After Deleting One Element, 1 1658. Minimum
Operations to Reduce X to Zero, 1838Pattern 10: Sliding Window - Monotonic Queue for Max/Min
239. Sliding Window Maximum, 862. Shortest Subarray with Sum at Least K, 1696. Jump Game VI
Pattern 11: Sliding Window - Character Frequency Matching 438. Find All Anagrams in a String, 567.
Permutation in String

III. Tree Traversal Patterns (DFS & BFS) Pattern 12: Tree BFS - Level Order Traversal 102. Binary Tree
Level Order Traversal, 103. Binary Tree Zigzag Level Order Traversal, 199. Binary Tree Right Side
View, 515. Find Largest Value in Each Tree Row, 1161. Maximum Level Sum of a Binary Tree Pattern
13: Tree DFS - Recursive Preorder Traversal 100. Same Tree, 101. Symmetric Tree, 105. Construct
Binary Tree from Preorder and Inorder Traversal, 114. Flatten Binary Tree to Linked List, 226. Invert
Binary Tree, 257. Binary Tree Paths, 988. Smallest String Starting From Leaf Pattern 14: Tree DFS -
Recursive Inorder Traversal 94. Binary Tree Inorder Traversal, 98. Validate Binary Search Tree, 173.
Binary Search Tree Iterator, 230. Kth Smallest Element in a BST, 501. Find Mode in Binary Search
Tree, 530. Minimum Absolute Difference in BST Pattern 15: Tree DFS - Recursive Postorder Traversal
104. Maximum Depth of Binary Tree, 110. Balanced Binary Tree, 124. Binary Tree Maximum Path
Sum, 145. Binary Tree Postorder Traversal, 337. House Robber III, 366. Find Leaves of Binary Tree,
543. Diameter of Binary Tree, 863. All Nodes Distance K in Binary Tree, 1110. Delete Nodes And
Return Forest, 2458. Height of Binary Tree After Subtree Removal Queries Pattern 17: Tree - Lowest
Common Ancestor (LCA) Finding 235. Lowest Common Ancestor of a Binary Search Tree, 236. Lowest
Common Ancestor of a Binary Tree Pattern 18: Tree - Serialization and Deserialization 297. Serialize
and Deserialize Binary Tree, 572. Subtree of Another Tree, 652. Find Duplicate Subtrees
IV. Graph Traversal Patterns (DFS & BFS) Pattern 19: Graph DFS - Connected Components / Island
Counting 130. Surrounded Regions, 200. Number of Islands, 417. Pacific Atlantic Water Flow, 547.
Number of Provinces, 695. Max Area of Island, 733. Flood Fill, 841. Keys and Rooms, 1020. Number
of Enclaves, 1254. Number of Closed Islands, 1905. Count Sub Islands, 2101. Detonate the Maximum
Bombs Pattern 20: Graph BFS - Connected Components / Island Counting 127. Word Ladder, 542. 01
Matrix, 994. Rotting Oranges, 1091. Shortest Path in Binary Matrix Pattern 21: Graph DFS - Cycle
Detection (Directed Graph) 207. Course Schedule, 210. Course Schedule II, 802. Find Eventual Safe
States, 1059. All Paths from Source Lead to Destination Pattern 22: Graph BFS - Topological Sort
(Kahn's Algorithm) 207. Course Schedule, 210. Course Schedule II, 269. Alien Dictionary, 310.
Minimum Height Trees, 444. Sequence Reconstruction, 1136. Parallel Courses, 1857. Largest Color
Value in a Directed Graph, 2050. Parallel Courses III, 2115. Find All Possible Recipes from Given
Supplies, 2392. Build a Matrix With Conditions Pattern 23: Graph - Deep Copy / Cloning 133. Clone
Graph Pattern 24: Graph - Shortest Path (Dijkstra's Algorithm) 743. Network Delay Time, 778. Swim
in Rising Water, 1514. Path with Maximum Probability, 1631. Path With Minimum Effort, 1976.
Number of Ways to Arrive at Destination, 2045. Second Minimum Time to Reach Destination, 2203.
Minimum Weighted Subgraph With the Required Paths, 2290. Minimum Obstacle Removal to Reach
Corner, 2577. Minimum Time to Visit a Cell In a Grid, 2812. Find the Safest Path in a Grid Pattern 25:
Graph - Shortest Path (Bellman-Ford / BFS+K) 787. Cheapest Flights Within K Stops Pattern 26: Graph
- Union-Find (Disjoint Set Union - DSU) 200. Number of Islands, 261. Graph Valid Tree, 305. Number
of Islands II, 323. Number of Connected Components in an Undirected Graph, 3 547. Number of
Provinces, 684. Redundant Connection, 4 721. Accounts Merge, 737. Sentence Similarity II, 947.
Most Stones Removed with Same Row or Column, 952. Largest Component Size by Common Factor,
959. Regions Cut By Slashes, 1101. The Earliest Moment When Everyone Become Frien

V. Dynamic Programming (DP) Patterns Pattern 27: DP - 1D Array (Fibonacci Style) 70. Climbing
Stairs, 91. Decode Ways, 198. House Robber, 213. House Robber II, 337. House Robber III, 509.
Fibonacci Number, 740. Delete and Earn, 746. Min Cost Climbing Stairs Pattern 28: DP - 1D Array
(Kadane's Algorithm for Max/Min Subarray) 53. Maximum Subarray Pattern 29: DP - 1D Array (Coin
Change / Unbounded Knapsack Style) 322. Coin Change, 377. Combination Sum IV, 518. Coin Change
II Pattern 30: DP - 1D Array (0/1 Knapsack Subset Sum Style) 416. Partition Equal Subset Sum, 494.
Target Sum Pattern 31: DP - 1D Array (Word Break Style) 139. Word Break, 140. Word Break II
Pattern 32: DP - 2D Array (Longest Common Subsequence - LCS) 583. Delete Operation for Two
Strings, 1143. Longest Common Subsequence Pattern 33: DP - 2D Array (Edit Distance / Levenshtein
Distance) 72. Edit Distance Pattern 34: DP - 2D Array (Unique Paths on Grid) 62. Unique Paths, 63.
Unique Paths II, 64. Minimum Path Sum, 120. Triangle, 221. Maximal Square, 931. Minimum Falling
Path Sum, 1277. Count Square Submatrices with All Ones Pattern 35: DP - Interval DP 312. Burst
Balloons, 546. Remove Boxes Pattern 36: DP - Catalan Numbers 95. Unique Binary Search Trees II,
96. Unique Binary Search Trees, 241. Different Ways to Add Parentheses Pattern 37: DP - Longest
Increasing Subsequence (LIS) 300. Longest Increasing Subsequence, 354. Russian Doll Envelopes,
1671. Minimum Number of Removals to Make Mountain Array, 2407. Longest Increasing
Subsequence II

VI. Heap (Priority Queue) Patterns Pattern 38: Heap - Top K Elements (Selection/Frequency) 215. Kth
Largest Element in an Array, 347. Top K Frequent Elements, 451. Sort Characters By Frequency, 506.
Relative Ranks, 703. Kth Largest Element in a Stream, 973. K Closest Points to Origin, 1046. Last
Stone Weight, 2558. Take Gifts From the Richest Pile Pattern 39: Heap - Two Heaps for Median
Finding 295. Find Median from Data Stream, 1825. Finding MK Average Pattern 40: Heap - K-way
Merge 23. Merge k Sorted Lists, 373. Find K Pairs with Smallest Sums, 378. Kth Smallest Element in a
Sorted Matrix, 632. Smallest Range Covering Elements from K Lists Pattern 41: Heap - Scheduling /
Minimum Cost (Greedy with Priority Queue) 253. Meeting Rooms II, 767. Reorganize String, 857.
Minimum Cost to Hire K Workers, 1642. Furthest Building You Can Reach, 1792. Maximum Average
Pass Ratio, 1834. Single-Threaded CPU, 1942. The Number of the Smallest Unoccupied Chair, 2402.
Meeting Rooms III

VII. Backtracking Patterns Pattern 42: Backtracking - Subsets (Include/Exclude) 17. Letter
Combinations of a Phone Number, 77. Combinations, 78. Subsets, 90. Subsets II Pattern 43:
Backtracking - Permutations 31. Next Permutation, 46. Permutations, 60. Permutation Sequence
Pattern 44: Backtracking - Combination Sum 39. Combination Sum, 40. Combination Sum II Pattern
45: Backtracking - Parentheses Generation 22. Generate Parentheses, 301. Remove Invalid
Parentheses Pattern 46: Backtracking - Word Search / Path Finding in Grid 79. Word Search, 212.
Word Search II, 2018. Check if Word Can Be Placed In Crossword Pattern 47: Backtracking - N-
Queens / Constraint Satisfaction 37. Sudoku Solver, 51. N-Queens Pattern 48: Backtracking -
Palindrome Partitioning 131. Palindrome Partitioning

VIII. Greedy Patterns Pattern 49: Greedy - Interval Merging/Scheduling 56. Merge Intervals, 57.
Insert Interval, 759. Employee Free Time, 986. Interval List Intersections, 2406. Divide Intervals Into
Minimum Number of Groups Pattern 51: Greedy - Jump Game Reachability/Minimization 45. Jump
Game II, 55. Jump Game Pattern 52: Greedy - Buy/Sell Stock 121. Best Time to Buy and Sell Stock,
122. Best Time to Buy and Sell Stock II Pattern 53: Greedy - Gas Station Circuit 134. Gas Station
Pattern 54: Greedy - Task Scheduling (Frequency Based) 621. Task Scheduler

IX. Binary Search Patterns Pattern 55: Binary Search - On Sorted Array/List 35. Search Insert Position,
69. Sqrt(x), 74. Search a 2D Matrix, 278. First Bad Version, 374. Guess Number Higher or Lower, 540.
Single Element in a Sorted Array, 704. Binary Search, 1539. Kth Missing Positive Number Pattern 56:
Binary Search - Find Min/Max in Rotated Sorted Array 33. Search in Rotated Sorted Array, 81. Search
in Rotated Sorted Array II, 153. Find Minimum in Rotated Sorted Array, 5 162. Find Peak Element,
852. Peak Index in a Mountain Array, 1095. Find in Mountain Array Pattern 57: Binary Search - On
Answer / Condition Function 410. Split Array Largest Sum, 774. Minimize Max Distance to Gas
Station, 875. Koko Eating Bananas, 1011. Capacity To Ship Packages 6 Within D Days, 1482. Minimum
Number of Days to Make m Bouquets, 1760. Minimum Limit of Balls in a Bag, 2064. Minimized
Maximum of Products Distributed to Any Store, 2226. Maximum Candies Allocated to K Children
Pattern 58: Binary Search - Find First/Last Occurrence 34. Find First and Last Position of Element in
Sorted Array, 658. Find K Closest Elements Pattern 59: Binary Search - Median of Two Sorted Arrays
4. Median of Two Sorted Arrays
X. Stack Patterns Pattern 60: Stack - Valid Parentheses Matching 20. Valid Parentheses, 32. Longest
Valid Parentheses, 921. Minimum Add to Make Parentheses Valid, 1249. Minimum Remove to Make
Valid Parentheses, 1963. Minimum Number of Swaps to Make the String Balanced Pattern 61: Stack -
Monotonic Stack 402. Remove K Digits, 496. Next Greater Element I, 503. Next Greater Element II,
739. Daily Temperatures, 901. Online Stock Span, 907. Sum of Subarray Minimums, 962. Maximum
Width Ramp, 1475. Final Prices With a Special Discount in a Shop, 1673. Find the Most Competitive
Subsequence Pattern 62: Stack - Expression Evaluation (RPN/Infix) 150. Evaluate Reverse Polish
Notation, 224. Basic Calculator, 227. Basic Calculator II, 772. Basic Calculator III Pattern 63: Stack -
Simulation / Backtracking Helper 71. Simplify Path, 394. Decode String, 735. Asteroid Collision
Pattern 64: Stack - Min Stack Design 155. Min Stack Pattern 65: Stack - Largest Rectangle in
Histogram 84. Largest Rectangle in Histogram, 85. Maximal Rectangle

XI. Bit Manipulation Patterns Pattern 66: Bitwise XOR - Finding Single/Missing Number 136. Single
Number, 137. Single Number II, 268. Missing Number, 389. Find the Difference Pattern 67: Bitwise
AND - Counting Set Bits (Hamming Weight) 191. Number of 1 Bits Pattern 70: Bitwise DP - Counting
Bits Optimization 338. Counting Bits Pattern 69: Bitwise Operations - Power of Two/Four Check 231.
Power of Two, 342. Power of Four

XII. Linked List Manipulation Patterns Pattern 71: Linked List - In-place Reversal 83. Remove
Duplicates from Sorted List, 92. Reverse Linked List II, 206. Reverse Linked List, 25. Reverse Nodes in
k-Group, 234. Palindrome Linked List, 82. Remove Duplicates from Sorted List II Pattern 72: Linked
List - Merging Two Sorted Lists 21. Merge Two Sorted Lists Pattern 73: Linked List - Addition of
Numbers 2. Add Two Numbers, 369. Plus One Linked List Pattern 74: Linked List - Intersection
Detection 160. Intersection of Two Linked Lists Pattern 75: Linked List - Reordering / Partitioning 24.
Swap Nodes in Pairs, 61. Rotate List, 86. Partition List, 143. Reorder List, 328. Odd Even Linked List

XIII. Array/Matrix Manipulation Patterns Pattern 76: Array/Matrix - In-place Rotation 48. Rotate
Image, 189. Rotate Array Pattern 77: Array/Matrix - Spiral Traversal 54. Spiral Matrix, 885. Spiral
Matrix III, 2326. Spiral Matrix IV Pattern 78: Array/Matrix - Set Matrix Zeroes (In-place Marking) 73.
Set Matrix Zeroes Pattern 79: Array - Product Except Self (Prefix/Suffix Products) 238. Product of
Array Except Self Pattern 80: Array - Plus One (Handling Carry) 66. Plus One Pattern 81: Array -
Merge Sorted Array (In-place from End) 88. Merge Sorted Array Pattern 82: Array - Cyclic Sort 41.
First Missing Positive, 268. Missing Number, 287. Find the Duplicate Number, 442. Find All Duplicates
in an Array, 448. Find All Numbers Disappeared in an Array Pattern 83: Array - Kadane's Variant for
Maximum Product 152. Maximum Product Subarray

XIV. String Manipulation Patterns Pattern 84: String - Palindrome Check (Two Pointers / Reverse) 9.
Palindrome Number, 125. Valid Palindrome, 680. Valid Palindrome II Pattern 85: String - Anagram
Check (Frequency Count/Sort) 49. Group Anagrams, 242. Valid Anagram Pattern 86: String - Roman
to Integer Conversion 13. Roman to Integer Pattern 87: String - String to Integer (atoi) 8. String to
Integer (atoi) Pattern 88: String - Multiply Strings (Manual Simulation) 43. Multiply Strings Pattern
89: String Matching - Naive / KMP / Rabin-Karp 28. Find the Index of the First Occurrence in a String,
214. Shortest Palindrome, 686. Repeated String Match, 796. Rotate String, 3008. Find Beautiful
Indices in the Given Array II Pattern 90: String - Repeated Substring Pattern Detection 459. Repeated
Substring Pattern

XV. Design Patterns Pattern 91: Design (General/Specific) 146. LRU Cache, 155. Min Stack, 208.
Implement Trie (Prefix Tree), 211. Design Add and Search Words Data Structure, 225. Implement
Stack using Queues, 232. Implement Queue using Stacks, 251. Flatten 2D Vector, 271. Encode and
Decode Strings, 295. Find Median from Data Stream, 341. Flatten Nested List Iterator, 346. Moving
Average from Data Stream, 353. Design Snake Game, 359. Logger Rate Limiter, 362. Design Hit
Counter, 379. Design Phone Directory, 380. Inse

Common questions

Powered by AI

In-place array modification using two pointers improves algorithms such as removing duplicates by minimizing the need for additional space while efficiently traversing and manipulating the array. One pointer iterates over each element to check for conditions (e.g., duplicates), while the other pointer tracks the position to overwrite elements. This reduces the space complexity to O(1) and time complexity to O(n), making it suitable for scenarios with memory constraints .

The sliding window approach offers significant advantages in analyzing subarray problems by providing a dynamic way to handle variable-sized subarrays or manage fixed-sized subarrays efficiently. Unlike traditional methods that require recalculating sums or averages completely when the position changes, sliding window maintains a running sum or other variables, updating them as the window slides across the array. This reduces the overall complexity from O(n^2) to O(n) in many cases, thus optimizing both time and space usage .

In solving constraint satisfaction problems like n-Queens, strategies such as forward checking, constraint propagation, and heuristic ordering (e.g., minimum remaining values) are employed. Forward checking reduces domains for future variables as choices are made, and constraint propagation further narrows possibilities by applying choice consequences early. Heuristic ordering dynamically chooses variables likely to constrain the search space, increasing backtracking efficiency. These strategies collaboratively prune the search tree and optimize search efficacy .

Dynamic programming is essential in solving maximum path sum problems in binary trees as it allows storing intermediate results of sub-path computations, preventing redundant calculations. It integrates with recursive traversal by computing maximum path sums at each node, utilizing previously computed values from child nodes. This approach combines recursion's top-down nature with bottom-up dynamic computations, ensuring consistent and optimal solutions leveraging both strategies .

Fast and slow pointers play a crucial role in detecting cycles within linked lists by utilizing the idea that if a cycle exists, a fast pointer (advancing two nodes at a time) will eventually meet a slow pointer (advancing one node at a time) within the cycle. This is based on the principle that the fast pointer gains on the slow pointer by one node per step, guaranteeing a meeting point if a cycle is present, thus confirming its existence .

The Bit Manipulation pattern applies bitwise operations like XOR to uniquely identify problems like finding a missing number by exploiting the properties of XOR (commutative, associative and x^x = 0). Using XOR, all numbers are combined with their indices, leaving only the missing number as non-zero. This approach leverages the ability of XOR to 'cancel out' paired elements, providing an O(n) solution that avoids extra space, unlike other methods .

Yes, the Union-Find data structure can be used to detect cycles in undirected graphs by maintaining and merging sets of elements, effectively tracking connectedness. In its application, each edge is checked to determine if it connects two nodes already in the same set (i.e., a single cycle would result). This approach leverages path compression and union by rank to efficiently manage and check connectivity, thus identifying cycles during the construction phases .

The LRU Cache design pattern optimizes performance by ensuring only the most recently accessed items remain in cache, contributing to efficient memory use and access speed, particularly in graph traversal scenarios with limited memory. Its primary components include a hash map for quick access to nodes and a doubly linked list that maintains the order of elements from most to least recently used, allowing constant time updates for cache hits/misses and evictions .

Monotonic queues enhance the efficiency of the Sliding Window Maximum problem by maintaining a deque that holds potential max elements in a way that the front of the deque always contains the maximum element for the current window. As the window slides, elements that are out of bounds are removed, and new elements are added while maintaining the queue's order. This strategy allows each element of the array to be processed in constant time, leading to an overall linear complexity O(n) instead of the O(n^2) complexity that results from a naive approach .

The Two Pointers - Converging pattern optimizes array target sum problems by reducing the time complexity from O(n^2), found in traditional nested loop approaches, to O(n). This is achieved by using two pointers, one starting at the beginning and one at the end of the sorted array, and adjusting their positions based on whether the current sum is less than or greater than the target. This method effectively narrows down potential pairs without redundantly processing each combination as in a nested loop .

You might also like