Two Pointers

Two pointers adalah teknik yang menggunakan dua variabel indeks (left dan right, atau i dan j) untuk menjelajah array dalam satu pass. Bayangkan mencari pasangan yang berjumlah target pada array terurut — naif: cek semua pasangan O(n²). Two pointers: mulai dari ujung-ujung, geser berdasarkan hasil perbandingan — O(n). Pada Chapter ini kita akan mempelajari dua varian utama: opposite-direction (dua pointer bergerak saling mendekat) dan same-direction (dua pointer bergerak ke arah yang sama). Kita juga akan membandingkannya dengan sliding window untuk melihat kapan memilih yang mana.

Kapan Two Pointers Bekerja #

Teknik two pointers efektif bila salah satu kondisi berikut terpenuhi:

1. Array terurut — memungkinkan kita memutuskan pointer mana yang harus digeser berdasarkan perbandingan.
2. Invariants terjaga — ada hubungan tertentu antara nilai pada dua pointer yang ingin kita pertahankan.
3. Pencarian pasangan atau partisi — soal yang meminta kita menemukan dua elemen atau mempartisi array berdasarkan kriteria.

Bila ketiga kondisi tidak terpenuhi, two pointers biasanya tidak lebih baik daripada brute force.

Opposite-Direction: Two Sum (Sorted) #

Aturan #

Diberikan array terurut dan target, cari dua elemen yang berjumlah target.

Mekanisme: Bandingkan dan Geser #

Pointer left dimulai dari indeks 0, pointer right dari indeks n-1. Hitung sum = a[left] + a[right]:

• Bila sum == target: ketemu.
• Bila sum < target: perbesar sum dengan geser left ke kanan.
• Bila sum > target: perkecil sum dengan geser right ke kiri.

Kode: Two Sum Sorted #

#include <iostream>
#include <vector>
#include <optional>

std::optional<std::pair<int,int>> two_sum_sorted(
    const std::vector<int>& a, int target)
{
    int left = 0;
    int right = static_cast<int>(a.size()) - 1;
    while (left < right) {
        int sum = a[left] + a[right];
        if (sum == target) return std::make_pair(left, right);
        else if (sum < target) ++left;
        else                  --right;
    }
    return std::nullopt;
}

int main() {
    std::vector<int> a = {1, 2, 3, 4, 5, 6, 8};
    auto res = two_sum_sorted(a, 9);
    if (res) {
        auto [i, j] = *res;
        std::cout << "a[" << i << "] + a[" << j << "] = "
                  << a[i] << " + " << a[j] << " = 9\n";
    } else {
        std::cout << "tidak ketemu\n";
    }

    res = two_sum_sorted(a, 100);
    std::cout << "two_sum(100): "
              << (res ? "ketemu" : "tidak ketemu") << '\n';
    return 0;
}

Output yang Dihasilkan:

a[0] + a[6] = 1 + 8 = 9
two_sum(100): tidak ketemu

1. Baris int left = 0, right = a.size() - 1;: dua pointer dimulai dari ujung-ujung array. Mereka akan bergerak saling mendekat.
2. Baris if (sum == target) return ...;: kasus ketemu — kembalikan pasangan indeks.
3. Baris else if (sum < target) ++left;: sum terlalu kecil. Karena array terurut menaik, satu-satunya cara memperbesar sum adalah memajukan left ke elemen yang lebih besar.
4. Baris else --right;: sum terlalu besar. Geser right ke kiri untuk elemen yang lebih kecil.
5. Kompleksitas: O(n) — setiap iterasi salah satu pointer bergerak. Total gerakan left + right ≤ n.

Same-Direction: Remove Duplicates In-Place #

Aturan #

Diberikan array terurut, hapus duplikat in-place sehingga elemen unik berada di awal. Kembalikan panjang bagian unik.

Mekanisme: Slow and Fast Pointer #

Pointer slow menunjuk posisi penulisan elemen unik berikutnya. Pointer fast menjelajah array. Bila a[fast] != a[slow-1], artinya kita menemukan elemen baru — tulis ke a[slow] lalu majukan slow.

Kode: Remove Duplicates In-Place #

#include <iostream>
#include <vector>

int remove_duplicates(std::vector<int>& a) {
    if (a.empty()) return 0;
    int slow = 1;
    for (int fast = 1; fast < static_cast<int>(a.size()); ++fast) {
        if (a[fast] != a[slow - 1]) {
            a[slow] = a[fast];
            ++slow;
        }
    }
    return slow;
}

int main() {
    std::vector<int> a = {1, 1, 2, 3, 3, 3, 4, 5, 5};
    int len = remove_duplicates(a);
    std::cout << "panjang unik = " << len << '\n';
    std::cout << "array (sebagian): ";
    for (int i = 0; i < len; ++i) std::cout << a[i] << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

panjang unik = 5
array (sebagian): 1 2 3 4 5

1. Baris if (a.empty()) return 0;: kasus khusus array kosong. Tidak ada elemen untuk dibandingkan.
2. Baris int slow = 1;: slow mulai dari 1 — a[0] pasti unik (elemen pertama).
3. Baris if (a[fast] != a[slow - 1]): bandingkan elemen saat ini dengan elemen unik terakhir. Bila berbeda, elemen baru ditemukan.
4. Baris a[slow] = a[fast]; ++slow;: tulis elemen baru ke posisi slow, lalu majukan slow. Memodifikasi array in-place.
5. Kompleksitas: O(n) — satu pass. Memori: O(1) — tidak ada array tambahan.

Same-Direction: Partition (Dutch National Flag Variasi) #

Aturan #

Partisi array sehingga elemen < pivot di kiri, == pivot di tengah, > pivot di kanan — varian tiga arah dari quicksort partition. Algoritma klasik Dutch National Flag oleh Dijkstra.

Kode: Three-Way Partition #

#include <iostream>
#include <vector>

void three_way_partition(std::vector<int>& a, int pivot) {
    int i = 0;        // batas kiri [< pivot]
    int j = 0;        // penjelajah
    int k = static_cast<int>(a.size()) - 1;  // batas kanan [> pivot]

    while (j <= k) {
        if (a[j] < pivot) {
            std::swap(a[i], a[j]);
            ++i; ++j;
        } else if (a[j] > pivot) {
            std::swap(a[j], a[k]);
            --k;
            // j tidak maju — elemen baru di posisi j belum diperiksa
        } else {
            ++j;  // a[j] == pivot, biarkan di tengah
        }
    }
}

int main() {
    std::vector<int> a = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5};
    int pivot = 5;
    three_way_partition(a, pivot);

    std::cout << "setelah partition pivot=" << pivot << ": ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

setelah partition pivot=5: 3 1 4 1 2 3 5 5 5 6 9

1. Baris int i = 0, j = 0, k = a.size() - 1;: tiga pointer. i adalah batas kiri elemen < pivot, j penjelajah, k batas kanan elemen > pivot.
2. Baris if (a[j] < pivot): elemen < pivot harus di kiri. Tukar dengan a[i], lalu majukan keduanya — a[i] sebelumnya adalah elemen == pivot atau elemen < pivot yang sudah aman.
3. Baris else if (a[j] > pivot): elemen > pivot harus di kanan. Tukar dengan a[k]. Jangan majukan j — elemen yang baru ditukar ke a[j] belum diperiksa.
4. Baris else ++j;: elemen == pivot, biarkan di tengah. Majukan j.
5. Hasil: elemen < 5 (3, 1, 4, 1, 2, 3) di kiri, elemen == 5 di tengah (5, 5, 5), elemen > 5 (9, 6) di kanan. Sesuai.

Two Pointers vs Sliding Window #

Kedua teknik sering tertukar — keduanya menggunakan dua variabel indeks. Perbedaan inti:

Three Sum (Variasi Lanjutan) #

Aturan #

Diberikan array, cari semua triple unik yang berjumlah target. Solusi naif O(n³). Dengan two pointers pada array terurut: O(n²).

Kode: Three Sum #

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

std::vector<std::vector<int>> three_sum(std::vector<int>& a, int target) {
    std::sort(a.begin(), a.end());
    std::set<std::vector<int>> hasil;
    int n = static_cast<int>(a.size());

    for (int i = 0; i < n - 2; ++i) {
        int left = i + 1;
        int right = n - 1;
        while (left < right) {
            int sum = a[i] + a[left] + a[right];
            if (sum == target) {
                hasil.insert({a[i], a[left], a[right]});
                ++left;
                --right;
            } else if (sum < target) {
                ++left;
            } else {
                --right;
            }
        }
    }
    return std::vector<std::vector<int>>(hasil.begin(), hasil.end());
}

int main() {
    std::vector<int> a = {-1, 0, 1, 2, -1, -4};
    auto triples = three_sum(a, 0);
    std::cout << "triple yang berjumlah 0:\n";
    for (const auto& t : triples) {
        std::cout << "  " << t[0] << ' ' << t[1] << ' ' << t[2] << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

triple yang berjumlah 0:
  -1 -1 2
  -1 0 1

1. Baris std::sort(a.begin(), a.end());: array harus terurut agar two pointers bekerja. Sorting O(n log n) — dominan oleh O(n²) loop utama.
2. Baris for (int i = 0; i < n - 2; ++i): fix elemen pertama a[i], lalu cari pasangan dengan two pointers di a[i+1..n-1] yang berjumlah target - a[i].
3. Baris hasil.insert({a[i], a[left], a[right]});: std::set otomatis menghilangkan duplikat. Setiap triple disimpan sebagai vector terurut, sehingga triple yang sama dari pasangan berbeda otomatis dianggap duplikat.
4. Hasil: dua triple unik berjumlah 0. Sesuai.

Ringkasan #

• Two pointers menggunakan dua variabel indeks untuk menjelajah array dalam satu pass O(n).
• Opposite-direction (left dari 0, right dari n-1) cocok untuk soal pada array terurut — two sum, palindrome, container with most water.
• Same-direction (slow dan fast) cocok untuk partisi in-place — remove duplicates, move zeros, Dutch flag.
• Two pointers vs sliding window: pilih two pointers bila soal tentang pasangan/partisi; sliding window bila tentang subarray kontigu optimal.
• Untuk soal three sum, fix satu elemen lalu gunakan two pointers untuk sisanya — O(n²) total.