[Leetcode Pattern] Two Pointers

Two pointers are very commonly used in leetcode problems. The purpose is mostly to turn nested loop traversal solvable in linear mode.

# not covering binary search / sliding window / slow fast pointers

respectively cover different arrays

ex: Merge Sorted Array

# i @ nums1, j @ nums 2
while i<m and j<n:
    do something with current nums[i] and nums[j]
    nums[i] vs nums[j]
    shift i or j
if j out, traverse i
if i out, traverse j

Init at opposite sides and converge

This is similar with binary search only except pointers are shifted linearly.

ex: 3Sum, Squares of a Sorted Array, Container With Most Water

i, j = 0, n-1
while i<=j:
    do something with current nums[i] and nums[j]
    nums[i] vs nums[j]
    shift i or j

Sometimes the stoping condition can be customized according to problem

ex: Find K Closest Elements

i, j = 0, n-1
while j-i+1>k:
    do something with current nums[i] and nums[j]
    nums[i] vs nums[j]
    shift i or j