LeetCode Grinding
Data Structures2 menit baca

Pengenalan Two Pointers

Pakai dua posisi di array untuk mengurangi pencarian berulang, kalau struktur input-nya memungkinkan.

Di artikel ini 3 bagian

Dalam array yang terurut, dua index bisa mengeliminasi beberapa pasangan lewat satu perbandingan. Aku memakai urutan itu untuk mencari dua angka yang jumlahnya sama dengan target tanpa mengecek setiap pasangan.

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.

Pencarian per pasangan bisa menyelesaikan soal ini, bahkan kalau array-nya belum terurut:

javascript
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, aku bisa mulai dari kedua ujung lalu bergerak ke tengah:

javascript
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 aku 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.

Sebelum menggeser pointer, aku mengecek pasangan mana yang dilewati dan kenapa semuanya nggak mungkin jadi jawaban. Untuk soal penjumlahan ini, urutan array memberi alasan itu.

Topik

Makasih udah baca

Gimana menurutmu?

Kasih reaksi atau komentar di bawah.

Memuat reaksi…

Bagikan tulisan ini

Memuat komentar...

Tulisan terkait

Semua tulisan