Two Pointers

Two pointers adalah teknik yang menempatkan dua indeks pada array dan menggerakkan keduanya secara terkoordinasi. Chapter Two Pointers di Section Array sudah membahas pola dasar (bertemu di tengah, paralel dari kiri). Pada Chapter ini kita akan fokus pada variasi lanjutan: partition (memisahkan elemen berdasarkan predikat), sorted intersection (irisan dua array terurut), dan container with most water (optimisasi area). Tujuan kita adalah mengenali kapan two pointers dapat menggantikan struktur data berat seperti hash set dengan kompleksitas yang sama atau lebih baik.

Recap: Kapan Two Pointers Berlaku #

Two pointers cocok ketika array memiliki struktur yang dapat dimanfaatkan:

• Array sorted → pointer kiri dan kanan dapat konvergen berdasarkan komparasi.
• Soal invariant → pertahankan properti (misal “tidak ada duplikat”) saat kedua pointer bergerak.
• Soal partisi → gunakan satu pointer lambat (slow) dan satu cepat (fast).

Variasi 1: Partition (Lomuto / Hoare) #

Aturan #

Diberikan array a dan predikat P, susun ulang elemen sehingga semua elemen yang memenuhi P berada di depan. Contoh kanonik: partition pada quick sort.

Kode: Lomuto Partition #

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

int partition(std::vector<int>& a, int lo, int hi, int pivot) {
    int i = lo;
    for (int j = lo; j < hi; ++j) {
        if (a[j] < pivot) {
            std::swap(a[i], a[j]);
            ++i;
        }
    }
    std::swap(a[i], a[hi]);
    return i;  // posisi pivot final
}

int main() {
    std::vector<int> a = {5, 2, 8, 1, 9, 3, 7, 4, 6};
    int pivot = a.back();
    std::cout << "pivot = " << pivot << '\n';
    int p = partition(a, 0, static_cast<int>(a.size()) - 1, pivot);
    std::cout << "partition index = " << p << '\n';
    std::cout << "array setelah partition: ";
    for (int x : a) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

pivot = 6
partition index = 5
array setelah partition: 5 2 1 3 4 6 7 9 8

1. Baris int i = lo;: pointer i menandai batas antara elemen < pivot dan ≥ pivot. Semua elemen a[lo..i-1] sudah < pivot.
2. Baris for (int j = lo; j < hi; ++j): pointer j memindai array. Saat menemukan elemen < pivot, tukar ke posisi i lalu increment i.
3. Baris std::swap(a[i], a[hi]);: taruh pivot ke posisi akhirnya — di antara elemen < pivot dan ≥ pivot.
4. Baris return i;: kembalikan indeks pivot final. Digunakan oleh quick sort untuk rekursi ke kiri dan kanan.
5. Hasil partition index = 5: elemen a[0..4] = {5,2,1,3,4} semuanya < 6. Elemen a[6..8] = {7,9,8} semuanya > 6. Sesuai.

Variasi 2: Sorted Intersection #

Aturan #

Diberikan dua array sorted a dan b, temukan irisan (elemen yang muncul di keduanya). Karena sorted, kita bisa pakai two pointers paralel tanpa hash set.

Kode: Intersection dengan Two Pointers #

#include <iostream>
#include <vector>

std::vector<int> intersect(const std::vector<int>& a, const std::vector<int>& b) {
    std::vector<int> result;
    int i = 0, j = 0;
    while (i < (int)a.size() && j < (int)b.size()) {
        if (a[i] < b[j]) {
            ++i;
        } else if (a[i] > b[j]) {
            ++j;
        } else {
            if (result.empty() || result.back() != a[i]) {
                result.push_back(a[i]);
            }
            ++i; ++j;
        }
    }
    return result;
}

int main() {
    std::vector<int> a = {1, 2, 2, 3, 5, 7, 9};
    std::vector<int> b = {2, 2, 4, 5, 6, 7, 8, 9};
    auto r = intersect(a, b);
    std::cout << "intersection: ";
    for (int x : r) std::cout << x << ' ';
    std::cout << '\n';
    return 0;
}

Output yang Dihasilkan:

intersection: 2 5 7 9

1. Baris while (i < a.size() && j < b.size()): loop sampai salah satu pointer habis.
2. Baris if (a[i] < b[j]) ++i;: bila elemen a lebih kecil, majukan i — a[i] tidak mungkin ada di b[j..] karena b sorted.
3. Baris else if (a[i] > b[j]) ++j;: simetri — bila b[j] lebih kecil, majukan j.
4. Baris if (result.empty() || result.back() != a[i]): cegah duplikat di hasil. Bila a dan b punya duplikat, kita ambil satu kali saja.
5. Baris ++i; ++j;: kedua pointer maju setelah menemukan elemen yang sama.
6. Hasil 2 5 7 9: irisan {1,2,2,3,5,7,9} ∩ {2,2,4,5,6,7,8,9} = {2,5,7,9}. Sesuai.

Variasi 3: Container With Most Water #

Aturan #

Diberikan array height berisi tinggi dinding, cari dua indeks i < j yang memaksimalkan area (j - i) · min(height[i], height[j]). Soal klasik LeetCode #11.

Mekanisme: Konvergen dari Kedua Ujung #

Mulai dengan left = 0, right = n-1 (lebar maksimum). Untuk setiap pasangan, hitung area, lalu majukan pointer yang menunjuk ke dinding lebih pendek — karena bila kita pindah yang lebih tinggi, area hanya bisa mengecil (lebar berkurang, tinggi tetap = dinding pendek).

Kode: Container With Most Water #

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

int max_area(const std::vector<int>& height) {
    int best = 0;
    int left = 0;
    int right = static_cast<int>(height.size()) - 1;
    while (left < right) {
        int h = std::min(height[left], height[right]);
        int w = right - left;
        best = std::max(best, h * w);
        if (height[left] < height[right]) ++left;
        else --right;
    }
    return best;
}

int main() {
    std::vector<std::vector<int>> tests = {
        {1, 8, 6, 2, 5, 4, 8, 3, 7},
        {1, 1},
        {4, 3, 2, 1, 4},
        {1, 2, 1}
    };
    for (const auto& h : tests) {
        std::cout << "max_area = " << max_area(h) << '\n';
    }
    return 0;
}

Output yang Dihasilkan:

max_area = 49
max_area = 1
max_area = 16
max_area = 2

1. Baris int h = std::min(height[left], height[right]);: tinggi efektif container = dinding yang lebih pendek.
2. Baris int w = right - left;: lebar = jarak antar dinding.
3. Baris best = std::max(best, h * w);: simpan area maksimum.
4. Baris if (height[left] < height[right]) ++left; else --right;: pindahkan pointer yang menunjuk ke dinding pendek. Strategi ini memastikan kita tidak kehilangan kemungkinan area yang lebih besar.
5. Hasil 49 untuk {1,8,6,2,5,4,8,3,7}: dinding indeks 1 (tinggi 8) dan indeks 8 (tinggi 7). Area = 7 × (8-1) = 49. Sesuai.

Kapan Two Pointers Kurang Cocok #

Ringkasan #

• Two pointers cocok untuk array sorted atau dengan invariant yang dapat dipertahankan.
• Lomuto partition: satu pointer lambat (i) menandai batas elemen < pivot, satu pointer cepat (j) memindai. O(n).
• Sorted intersection: dua pointer paralel, majukan yang menunjuk ke nilai lebih kecil. O(n + m).
• Container with most water: konvergen dari kedua ujung, pindahkan pointer dinding pendek. O(n) dengan bukti via pertukaran lebar-tinggi.
• Two pointers tidak selalu cocok — bila pointer harus mundur, ganti ke sliding window atau struktur lain.