Two pointer

Pemeriksaan semua pasangan elemen adalah biaya termahal yang paling sering muncul pada soal array. Pola two pointer, yaitu pengerjaan soal dengan dua penunjuk indeks yang bergerak terkendali, adalah cara paling umum untuk menurunkannya. Dua indeks diposisikan di kedua ujung array, lalu keduanya bergerak saling mendekat, dengan satu keputusan pada setiap langkah. Setelah topik ini, pemeriksaan pasangan yang semula berbiaya $O(n^2)$ dapat diubah menjadi satu lintasan $O(n)$ pada dua soal klasik, yaitu pemeriksaan palindrom dan two sum pada array terurut, lengkap dengan bukti pengukurannya.

Dua penunjuk yang saling mendekat#

Bentuk paling umum dari two pointer memakai dua indeks sekaligus, biasanya diberi nama kiri dan kanan. Indeks kiri berangkat dari posisi 0, indeks kanan berangkat dari posisi terakhir, dan setiap putaran memeriksa pasangan nilai pada kedua posisi itu. Pemeriksaan kemudian melahirkan keputusan, majukan kiri, mundurkan kanan, atau langsung menyatakan jawaban ditemukan. Karena setiap langkah mengurangi jarak keduanya satu, jumlah putaran tidak pernah melebihi panjang array, sehingga biaya waktunya $O(n)$ dengan memori tambahan $O(1)$.

Bandingkan dengan perulangan bersarang yang mencoba semua pasangan tanpa penghematan. Array dengan $n$ elemen memuat $n(n-1)/2$ pasangan indeks berbeda, dan semuanya diperiksa pada pendekatan brute force, yaitu mencoba semua kemungkinan sampai jawaban ditemukan. Diagram berikut menunjukkan dua penunjuk yang baru mulai bergerak pada array terurut, beserta titik temu di tengahnya.

Garis putus-putus pada diagram adalah batas alami perulangannya, yaitu kondisi kiri < kanan. Selama jaraknya masih positif, masih ada pasangan baru yang layak diperiksa, dan begitu keduanya bertemu, seluruh kemungkinan tanpa pengulangan indeks sudah tercakup. Bentuk perulangan yang sama dipakai pada semua contoh topik ini, dan yang berubah hanyalah dasar keputusannya.

Palindrom, pasangan paling simetris#

Palindrom adalah kata yang dibaca sama dari depan dan dari belakang, dan sifat simetrinya memberi dasar keputusan yang paling polos. Karakter pada posisi kiri wajib sama dengan karakter pada posisi kanan, karena keduanya adalah cermin satu sama lain. Satu pasangan yang tidak cocok cukup untuk menyatakan seluruh kata bukan palindrom, sedangkan pasangan yang cocok boleh segera dilupakan. Fungsi yang sama juga aman untuk string kosong maupun satu karakter, karena kondisi kiri < kanan langsung gagal sebelum perbandingan pertama. Berkas berikut menguji empat kata dengan pola tersebut.

# Palindrom diperiksa dengan dua pointer dari kedua ujung string.

def palindrom(teks):
    kiri, kanan = 0, len(teks) - 1
    while kiri < kanan:
        if teks[kiri] != teks[kanan]:
            return False
        kiri += 1
        kanan -= 1
    return True

kata_uji = ["kasurrusak", "malam", "katak", "pintu"]
for kata in kata_uji:
    print(f"{kata:12} -> {palindrom(kata)}")

kasurrusak   -> True
malam        -> True
katak        -> True
pintu        -> False

Kata pintu berhenti pada pasangan pertama karena p dan u berbeda, sehingga pemeriksaannya tamat dalam satu langkah. Kata yang memang palindrom menempuh kira-kira setengah panjang kata, karena kedua penunjuk bertemu di tengah. Panjang ganjil menyisakan satu karakter tengah yang tidak pernah dipasangkan, dan kondisi kiri < kanan membiarkannya begitu karena satu karakter mana pun otomatis cocok dengan dirinya sendiri. Setiap karakter diperiksa paling banyak satu kali, sehingga biayanya $O(n)$ tanpa membuat salinan string maupun membaliknya lebih dahulu.

Syarat satu sisi boleh dibuang#

Pola two pointer hanya benar bila setiap langkah mampu membuang satu sisi tanpa risiko kehilangan jawaban. Palindrom mendapat dasarnya dari simetri, sedangkan keluarga two-sum pada array terurut mendapat dasarnya dari urutan. Pada array yang terurut menaik, nilai terkecil yang tersisa selalu berada di ujung kiri dan nilai terbesarnya di ujung kanan, sehingga satu perbandingan jumlah sudah cukup untuk menyimpulkan nasib salah satu penunjuk.

Misalkan jumlah kedua ujung lebih kecil dari target. Dengan kanan tetap, memasangkan angka[kiri] dengan elemen mana pun yang tersisa tidak mungkin menghasilkan jumlah yang lebih besar, karena angka[kiri] adalah nilai terkecil yang masih dipertimbangkan. Satu-satunya harapan mencapai target adalah mengganti nilai kiri dengan yang lebih besar, sehingga kiri maju. Sebaliknya, ketika jumlahnya melebihi target, angka[kanan] adalah nilai terbesar yang masih dipertimbangkan, sehingga pasangan apa pun untuknya tidak mungkin menghasilkan jumlah yang lebih kecil dan kanan mundur. Berkas berikut mencatat setiap keputusan pada array delapan elemen dengan target 31.

# Two sum pada array terurut dengan dua pointer konvergen.
# Setiap gerakan penunjuk dicatat agar keputusannya terlihat.

def dua_sum_terurut(angka, target):
    kiri, kanan = 0, len(angka) - 1
    catatan = []
    while kiri < kanan:
        jumlah = angka[kiri] + angka[kanan]
        if jumlah == target:
            catatan.append(f"indeks {kiri} + indeks {kanan} = {target}")
            return (kiri, kanan), catatan
        if jumlah < target:
            catatan.append(f"jumlah {jumlah} < {target}, kiri maju")
            kiri += 1
        else:
            catatan.append(f"jumlah {jumlah} > {target}, kanan mundur")
            kanan -= 1
    catatan.append("tidak ada pasangan yang cocok")
    return None, catatan

data = [2, 5, 9, 13, 18, 21, 27, 34]
pasangan, catatan = dua_sum_terurut(data, 31)
print("array  :", data)
print("target :", 31)
for baris in catatan:
    print(baris)
print("hasil  :", pasangan)

array  : [2, 5, 9, 13, 18, 21, 27, 34]
target : 31
jumlah 36 > 31, kanan mundur
jumlah 29 < 31, kiri maju
jumlah 32 > 31, kanan mundur
jumlah 26 < 31, kiri maju
jumlah 30 < 31, kiri maju
jumlah 34 > 31, kanan mundur
indeks 3 + indeks 4 = 31
hasil  : (3, 4)

Jejaknya memperlihatkan pola zig-zag yang wajar, kanan mundur dan kiri maju bergantian, sampai jumlah 13 + 18 tepat memenuhi target. Logika yang sama ditulis ulang pada Java berikut tanpa perubahan keputusan apa pun, lengkap dengan penghitung perbandingannya.

// Two sum pada array terurut dengan dua pointer konvergen.
// Program utuh: jalankan dengan `java DuaPenunjuk.java`.

public class DuaPenunjuk {
    public static void main(String[] args) {
        int[] angka = {2, 5, 9, 13, 18, 21, 27, 34};
        int target = 31;
        int kiri = 0;
        int kanan = angka.length - 1;
        int perbandingan = 0;
        Integer kiriHasil = null;
        Integer kananHasil = null;
        while (kiri < kanan) {
            perbandingan++;
            int jumlah = angka[kiri] + angka[kanan];
            if (jumlah == target) {
                kiriHasil = kiri;
                kananHasil = kanan;
                break;
            } else if (jumlah < target) {
                kiri++;
            } else {
                kanan--;
            }
        }
        System.out.println("array  : " + java.util.Arrays.toString(angka));
        System.out.println("target : " + target);
        if (kiriHasil != null) {
            System.out.println("pasangan: indeks " + kiriHasil + " dan " + kananHasil
                    + " (nilai " + angka[kiriHasil] + " + " + angka[kananHasil] + ")");
        } else {
            System.out.println("pasangan: tidak ada");
        }
        System.out.println("perbandingan: " + perbandingan);
    }
}

array  : [2, 5, 9, 13, 18, 21, 27, 34]
target : 31
pasangan: indeks 3 dan 4 (nilai 13 + 18)
perbandingan: 7

Program Java dijalankan dalam satu perintah java DuaPenunjuk.java tanpa tahap kompilasi terpisah. Kedua versi menghabiskan tujuh perbandingan untuk menemukan indeks 3 dan 4, enam di antaranya keputusan pembuangan dan satu kecocokan. Angka sekecil ini adalah wajah dari $O(n)$, dan selisihnya terhadap perulangan bersarang diukur pada bagian penutup.

Mengukur selisihnya pada masukan yang sama#

Klaim $O(n^2)$ lawan $O(n)$ tidak perlu dibiarkan sebagai teori, karena jumlah perbandingan keduanya dapat dihitung pada array yang sama. Berkas berikut mencari pasangan dengan jumlah 148 pada array lima puluh nilai genap terurut, sekali dengan perulangan bersarang dan sekali dengan dua penunjuk, lalu mencatat jumlah perbandingannya.

# Penghitung perbandingan: perulangan bersarang versus dua pointer
# pada array terurut yang sama dengan target yang sama.

def perbandingan_bersarang(angka, target):
    perbandingan = 0
    for i in range(len(angka)):
        for j in range(i + 1, len(angka)):
            perbandingan += 1
            if angka[i] + angka[j] == target:
                return perbandingan
    return perbandingan

def perbandingan_dua_pointer(angka, target):
    kiri, kanan = 0, len(angka) - 1
    perbandingan = 0
    while kiri < kanan:
        perbandingan += 1
        jumlah = angka[kiri] + angka[kanan]
        if jumlah == target:
            return perbandingan
        if jumlah < target:
            kiri += 1
        else:
            kanan -= 1
    return perbandingan

data = list(range(2, 102, 2))  # 50 nilai genap: 2, 4, ..., 100
target = 148
print("panjang array        :", len(data))
print("perulangan bersarang :", perbandingan_bersarang(data, target), "perbandingan")
print("dua pointer          :", perbandingan_dua_pointer(data, target), "perbandingan")

panjang array        : 50
perulangan bersarang : 900 perbandingan
dua pointer          : 24 perbandingan

Perulangan bersarang menghabiskan 900 perbandingan, karena pasangan yang cocok baru muncul ketika nilai 48 dipasangkan dengan 100 di ujung array. Dua penunjuk hanya butuh 24 perbandingan untuk sampai pada jawaban yang sama. Ketika targetnya tidak memiliki pasangan sama sekali, kedua pendekatan sama-sama menempuh jatah penuhnya, sekitar 1.225 perbandingan untuk bersarang lawan paling banyak 49 untuk dua penunjuk pada array ini. Selisih yang sama melebar ketika masukan membesar: pada array sepuluh ribu elemen, perulangan bersarang dapat menyentuh sekitar lima puluh juta perbandingan, sedangkan dua penunjuk berhenti paling banyak pada sepuluh ribu langkah. Notasi $O(n^2)$ dan $O(n)$ pada bagian awal topik kini punya angka pendampingnya.

Kesalahan umum#

1. Memakai dasar keputusan pada array yang tidak terurut. Jumlah kedua ujung yang terlalu kecil tidak menyimpulkan apa pun bila nilainya berserakan, karena nilai terkecil tidak lagi pasti berada di ujung kiri. Urutkan dahulu bila indeks asli tidak diminta, atau kembali ke hash map seperti pada modul array.
2. Memakai kondisi kiri <= kanan pada pencarian pasangan. Kedua penunjuk yang bertemu akan membandingkan elemen dengan dirinya sendiri, sehingga target dua kali satu nilai dilaporkan dengan indeks yang sama dua kali. Kondisi kiri < kanan menjaga kedua elemen selalu berbeda.
3. Menggerakkan kedua penunjuk sekaligus tanpa alasan. Langkah tanpa dasar membuang pasangan yang belum diperiksa, dan jawaban yang sah bisa terlewat begitu saja. Setiap langkah wajib punya dasar yang membuat satu sisi aman dilupakan.
4. Melupakan jalur ketika tidak ada pasangan. Perulangan yang tamat tanpa kecocokan tetap harus menjawab, misalnya mengembalikan None atau menyatakan tidak ditemukan, agar pemanggil tidak menebak-nebak hasilnya.

Ringkasan#

• Two pointer konvergen menempatkan dua indeks di kedua ujung array dan membuang satu sisi pada setiap langkah, sehingga biaya turun dari $O(n^2)$ menjadi $O(n)$ dengan memori tambahan $O(1)$.
• Simetri memberi dasar keputusan pada pemeriksaan palindrom, sedangkan urutan memberi dasarnya pada two sum pada array terurut.
• Demo lima puluh elemen mencatat 900 perbandingan untuk perulangan bersarang lawan 24 untuk dua penunjuk pada target yang sama.
• Versi Java dan Python berbagi logika yang sama persis dan sama-sama selesai dalam tujuh perbandingan pada array delapan elemen.

Referensi#

• Built-in Types — Python Software Foundation — dokumentasi urutan dan pengindeksan string yang dipakai pada demo palindrom.
• NeetCode Roadmap — NeetCode — peta latihan yang memuat keluarga soal two pointer dan Two Sum II.