Two Pointer Technique — Algoritma

Two Pointer menggunakan dua pointer yang bergerak menuju satu sama lain (atau searah) untuk mengurangi kompleksitas dari O(n²) jadi O(n). Pola 1: Converging…

Two pointer adalah teknik memakai dua penunjuk posisi di array, lalu menggeser keduanya sesuai aturan. Pointer di sini cuma variabel biasa yang menyimpan index, misalnya left dan right. Di array yang sudah terurut, dua pointer dari dua ujung bisa menemukan pasangan angka dengan jumlah tertentu dalam satu kali jalan, tanpa mencoba semua pasangan, mirip dua orang yang mencari dari dua ujung rak lalu jalan saling mendekat.

🧪 Tebakan cepat: di [1, 3, 5, 7, 11, 13, 17], mencoba pasangan satu per satu butuh 10 percobaan sampai ketemu dua angka berjumlah 16. Two pointer butuh berapa? Tebak dulu, jawabannya ada di bagian "Dua ujung saling mendekat".

Dua ujung saling mendekat

Targetnya 16. left mulai di index 0 (angka terkecil), right di index terakhir, 6 (angka terbesar):

Langkah left (angka) right (angka) Jumlah Keputusan
1 0 (1) 6 (17) 18 kebesaran: right mundur
2 0 (1) 5 (13) 14 kekecilan: left maju
3 1 (3) 5 (13) 16 pas: ketemu

Cuma 3 langkah. Itu jawaban tebakannya.

function twoSum(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    const sum = arr[left] + arr[right];
    if (sum === target) return [left, right]; // pas: kembalikan posisinya
    if (sum < target) left++; // kekecilan: ambil angka yang lebih besar
    else right--; // kebesaran: ambil angka yang lebih kecil
  }
  return null; // pointer bertemu: gak ada pasangan
}

console.log(twoSum([1, 3, 5, 7, 11, 13, 17], 16)); // [1, 5]
console.log(twoSum([1, 3, 5, 7, 11, 13, 17], 19)); // null

Kenapa boleh menggeser?

Array-nya terurut dari kecil ke besar. Waktu 1 + 17 = 18 kebesaran, 17 dipasangkan dengan angka terkecil pun sudah kebesaran, jadi 17 gak mungkin jadi bagian jawaban: buang, right--. Waktu 1 + 13 = 14 kekecilan, 1 dipasangkan dengan angka terbesar yang tersisa pun masih kekecilan: buang, left++. Tiap langkah membuang satu angka dengan aman.

Jadi untuk n angka paling banyak n - 1 langkah. Ini O(n): data dua kali lipat, langkahnya kira-kira dua kali lipat. Mencoba semua pasangan pakai dua loop bersarang adalah O(n²), alias n × n: data dua kali lipat, kerjanya kira-kira empat kali lipat. Syarat utamanya, array harus sudah terurut. Di array acak, menggeser pointer gak ada artinya.

Pola lain: cek palindrom

Dua ujung juga bisa dibandingkan satu sama lain, misalnya untuk mengecek palindrom, kata yang sama kalau dibaca dari depan atau dari belakang.

function isPalindrome(str) {
  let left = 0;
  let right = str.length - 1;
  while (left < right) {
    if (str[left] !== str[right]) return false;
    left++;
    right--;
  }
  return true;
}

console.log(isPalindrome("katak")); // true
console.log(isPalindrome("kucing")); // false

Di sini dua pointer selalu bergerak bersamaan menuju tengah. Ada juga dua pointer yang searah: satu jalan pelan, satu jalan cepat, misalnya untuk membuang angka dobel dari array terurut tanpa bikin array baru.

⚠️ Jebakan yang sering ketemu

TL;DR: Two pointer memakai dua index, left di awal dan right di akhir array terurut. Jumlah kekecilan: left++. Kebesaran: right--. Pas: return [left, right]. Pointer bertemu (left < right gak lagi benar): return null. Tiap langkah membuang satu angka, jadi O(n), bukan O(n²) seperti mencoba semua pasangan. Pola yang sama dipakai untuk cek palindrom dari dua ujung.

Yang akan kamu pelajari