Two-Pointer-Algorithm

Given a sorted integer array, remove some duplicates in-place such that each unique element appears at most twice. Maintain the relative order of the elements. If there are \(k\) elements after removing the duplicates, the first \(k\) elements of the array should hold the final result.

This a two-pointer problem, where we have a tortoise and a hare. Establishing an invariant that must be maintained throughout the array is useful to avoid tripping up on index arithmetic. In this case, let tortoise be the index whose final value needs to be determined in the current iteration. [..., tortoise-1] (inclusive) is the processed range that won’t change. #two-pointer-algorithm