Two Pointers
Two pointers are useful when performing operations on a range: two indices traverse the data simultaneously and exploit the range’s structure. The technique can often reduce $\mathcal{O}(n^2)$ time complexity to $\mathcal{O}(n)$. Opposite-Direction Scan The left pointer starts at the beginning and continuously moves to the right, while the right pointer starts at the end and continuously moves to the left, until they meet and stop. This is generally used for problems involving sorted arrays or strings.
Read note →