Pengenalan Two Pointers

Nested loop dulu jadi solusi andalan saya buat soal array, sampai saya kenal teknik two pointers. Dua index bisa membuang sekelompok pasangan yang nggak mungkin sekaligus, asalkan input-nya punya urutan yang berguna.

Pergerakan pointer

Two pointers adalah index atau reference yang menelusuri sebuah data structure bareng-bareng, terpisah, atau dengan kecepatan yang berbeda. Bagian pentingnya ada di aturan geraknya. Aturan itu harus memanfaatkan sifat dari input, misalnya urutan yang udah sorted, supaya nggak mengecek ulang pasangan yang sama.

Waktu itu saya mencoba mencari dua angka di sebuah sorted array yang jumlahnya sama dengan target. Percobaan pertama saya pakai nested loop:

function twoSumNaive(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return [];
}

Cara ini mengecek setiap pasangan, jadi time complexity-nya O(n²).

Scan di array sorted dan gerakan yang aman

Karena array-nya sorted, saya bisa mulai dari kedua ujung lalu bergerak ke tengah:

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

  while (left < right) {
    const sum = nums[left] + nums[right];

    if (sum === target) {
      return [left, right];
    } else if (sum < target) {
      left++; // Need a larger sum, move left pointer right
    } else {
      right--; // Sum too large, move right pointer left
    }
  }

  return []; // No solution found
}

Kalau jumlahnya terlalu kecil, semua pasangan tersisa dengan nilai left yang sekarang juga pasti terlalu kecil. Algoritmanya memajukan left. Kalau jumlahnya terlalu besar, semua pasangan tersisa dengan nilai right yang sekarang juga pasti terlalu besar. Algoritmanya memundurkan right. Tiap pointer cuma bergerak ke satu arah, jadi scan-nya butuh waktu O(n) dan extra space O(1).

Kegunaan dan aturan gerak

Menurut saya pattern ini berguna untuk mencari pair atau triplet di data yang sorted, mengecek palindrome dari kedua ujung, partitioning, dan cycle detection fast and slow. Aturan geraknya berubah tergantung soalnya, tapi tujuannya tetap sama: mengeliminasi kandidat, bukan mengetes semuanya.

Two pointers mengajari saya untuk mencari keputusan yang monotonic dulu sebelum menulis nested loop. Data yang sorted sering kali memberi bukti yang persis dibutuhkan untuk menggeser satu sisi tanpa kehilangan jawaban yang valid.

Two pointers bisa memangkas pencarian pasangan dari O(n²) jadi O(n) kalau input-nya mendukung aturan gerak yang aman. Sebelum pakai pattern ini, cari dulu urutan atau invariant yang membenarkan setiap update pada pointer.