PatternsBeginner8 minO(n) time · O(1) spaceFree
Pattern - Two Pointers
One array, two indices, O(n). The pattern behind Two Sum II, Valid Palindrome, Container With Most Water, and 3Sum.
01 / 05
What is Two Pointers?
Instead of nested loops comparing every pair - O(n^2) - you keep two indices into the array and move them toward each other or forward together. Each element is visited at most once, so work collapses to O(n).
Two pointers turns an O(n^2) pair scan into…