In-Place Tricks: Slow and Fast Pointers

Same direction, different speeds

Both pointers start on the left. The fast one looks at every item; the slow one marks where the next item to keep should go.

Think of it like this: Tidying a shelf: your right hand picks up each book (fast); your left hand marks the next spot for a book you keep (slow).

#include <iostream>
#include <vector>
using namespace std;

int main() {
    // remove duplicates from a sorted vector
    vector<int> a = {1, 1, 2, 3, 3, 3, 7};
    int slow = 0;
    for (int fast = 1; fast < (int)a.size(); fast++) {
        if (a[fast] != a[slow]) {
            slow++;
            a[slow] = a[fast];
        }
    }
    int unique = slow + 1;
    cout << unique << " unique:";
    for (int i = 0; i < unique; i++) cout << ' ' << a[i];
    cout << endl;

    // move zeros to the end
    vector<int> b = {0, 5, 0, 3, 12};
    slow = 0;
    for (int fast = 0; fast < (int)b.size(); fast++)
        if (b[fast] != 0) swap(b[slow++], b[fast]);
    for (int x : b) cout << x << ' ';
    cout << endl;
    return 0;
}

Output

4 unique: 1 2 3 7
5 3 12 0 0 

Both run in O(n) time with O(1) extra space.

Tip: The standard library has these too: unique() and stable_partition() in <algorithm>. Knowing how they work helps you use them correctly.