Two Pointers & Sliding Window

Kenapa ini penting

Two pointers dan sliding window adalah dua pola yang membuat soal array dan string yang tampak butuh loop bersarang (O(n²)) bisa diselesaikan dengan satu kali jalan (O(n)), sering juga tanpa memori tambahan. Interviewer suka pola ini karena menunjukkan kamu bisa memanfaatkan struktur input (misalnya array sudah terurut) dan bisa menjaga invariant, yaitu kondisi yang selalu benar selama loop berjalan.

Analogi two pointers: dua orang membaca kata dari ujung kiri dan ujung kanan untuk mengecek palindrom, lalu bergerak saling mendekat. Analogi sliding window: jendela kereta yang bergerak di atas rel data. Kamu hanya melihat bagian yang ada di jendela; saat kereta maju, satu elemen masuk dari kanan dan satu keluar dari kiri. Kamu tidak perlu menghitung ulang seluruh isi jendela dari nol.

Konsep inti

Tiga bentuk two pointers

Kunci two pointers berlawanan arah: kamu harus bisa menjelaskan kenapa aman membuang satu sisi. Di Two Sum II yang terurut, kalau nums[l] + nums[r] < target, semua pasangan nums[l] dengan elemen lain di kiri r pasti lebih kecil lagi, jadi l aman dimajukan.

Dua bentuk sliding window

Ukuran tetap (k): jumlahkan k elemen pertama, lalu tiap langkah tambah elemen baru dan kurangi elemen yang keluar.

Ukuran dinamis: kanan selalu maju; kiri maju saat window melanggar syarat (atau saat syarat terpenuhi kalau mencari window terpendek). Template umumnya:

// Template sliding window dinamis (pseudo-template, isi sesuai soal)
function slidingWindow(arr) {
  let left = 0, best = 0;
  const state = new Map();                 // isi window: frekuensi, jumlah, dll.
  for (let right = 0; right < arr.length; right++) {
    // 1. masukkan arr[right] ke state
    // 2. while (window tidak valid) { keluarkan arr[left] dari state; left++; }
    // 3. update best dengan ukuran window (right - left + 1)
  }
  return best;
}

Kenapa ini O(n) walau ada while di dalam for? Karena left hanya pernah maju, total geraknya paling banyak n sepanjang seluruh run. Jadi totalnya 2n langkah. Ini pertanyaan lanjutan yang sangat sering muncul; jawab dengan kalimat: "Each element is added once and removed at most once, so it's amortized O(n)."

Kapan sliding window TIDAK bisa dipakai

Sliding window butuh sifat monoton: memperlebar window hanya membuat "lebih buruk" atau "lebih baik" ke satu arah. Kalau array berisi angka negatif dan kamu mencari jumlah tepat k, memperlebar window bisa menurunkan jumlah, jadi window tidak tahu harus menyusut atau melebar. Untuk kasus itu, pakai prefix sum + hash map dari modul sebelumnya.

Contoh percakapan interview: menjelaskan invariant

Interviewer sering menggali kenapa pointer boleh digeser. Jawaban yang meyakinkan menyebut invariant, bukan hanya "karena berhasil di contoh".

Interviewer: "In Container With Most Water, why is it safe to move the shorter side?"

Candidate: "The area is limited by the shorter line. If I move the taller side inward, the width shrinks and the height can't go above the shorter line, so the area can only get smaller or stay the same. Moving the shorter side is the only move that could possibly find a bigger area. So I never skip a pair that could be the answer."

Interviewer: "And the complexity?"

Candidate: "Each step moves one pointer inward, so there are at most n minus one steps. O(n) time, O(1) space."

Untuk sliding window, kalimat kunci yang perlu kamu latih: "I'll maintain a window that is always valid. The right pointer expands it, and whenever it becomes invalid, I shrink it from the left until it's valid again. Each character enters and leaves the window at most once, so it's O(n)." Kalau kamu bisa mengucapkan dua kalimat ini dengan lancar, sebagian besar soal window menjadi soal "isi template".

Tips latihan: sebelum menulis kode window, tulis dulu satu baris komentar berisi definisi window yang valid, misalnya // valid = tidak ada karakter berulang. Baris ini memaksa kamu memikirkan syarat menyusut, dan memudahkan interviewer mengikuti logikamu.

Contoh kode

// Two pointers (arah berlawanan): valid palindrome, abaikan non-alfanumerik
function isPalindrome(s) {
  const isAlnum = c => /[a-z0-9]/i.test(c);
  let l = 0, r = s.length - 1;
  while (l < r) {
    if (!isAlnum(s[l])) { l++; continue; }
    if (!isAlnum(s[r])) { r--; continue; }
    if (s[l].toLowerCase() !== s[r].toLowerCase()) return false;
    l++; r--;
  }
  return true;
}
console.log(isPalindrome('A man, a plan, a canal: Panama'), isPalindrome('race a car'), isPalindrome(' '));
// → true false true

// Two Sum II (array sudah terurut) -> O(1) ruang
function twoSumSorted(nums, target) {
  let l = 0, r = nums.length - 1;
  while (l < r) {
    const sum = nums[l] + nums[r];
    if (sum === target) return [l, r];
    if (sum < target) l++; else r--;
  }
  return [];
}
console.log(twoSumSorted([2, 7, 11, 15], 9), twoSumSorted([1, 3, 4, 6], 10), twoSumSorted([1, 2], 7));
// → [ 0, 1 ] [ 2, 3 ] []

// Container With Most Water
function maxArea(h) {
  let l = 0, r = h.length - 1, best = 0;
  while (l < r) {
    best = Math.max(best, Math.min(h[l], h[r]) * (r - l));
    if (h[l] < h[r]) l++; else r--;        // geser sisi yang lebih pendek
  }
  return best;
}
console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]), maxArea([1, 1]));
// → 49 1

// Two pointers searah: remove duplicates in-place dari array terurut
function removeDuplicates(nums) {
  if (nums.length === 0) return 0;
  let write = 1;
  for (let read = 1; read < nums.length; read++)
    if (nums[read] !== nums[write - 1]) nums[write++] = nums[read];
  return write;
}
const arr = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
const k = removeDuplicates(arr);
console.log(k, arr.slice(0, k));
// → 5 [ 0, 1, 2, 3, 4 ]

// Sliding window ukuran tetap: rata-rata maksimum subarray panjang k
function maxAverage(nums, k) {
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];
  let best = sum;
  for (let i = k; i < nums.length; i++) {
    sum += nums[i] - nums[i - k];          // masukkan kanan, buang kiri
    best = Math.max(best, sum);
  }
  return best / k;
}
console.log(maxAverage([1, 12, -5, -6, 50, 3], 4), maxAverage([5], 1));
// → 12.75 5

// Sliding window dinamis: longest substring without repeating characters
function lengthOfLongestSubstring(s) {
  const lastSeen = new Map();
  let left = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    const ch = s[right];
    // lompat left melewati kemunculan terakhir, tapi jangan pernah mundur
    if (lastSeen.has(ch) && lastSeen.get(ch) >= left) left = lastSeen.get(ch) + 1;
    lastSeen.set(ch, right);
    best = Math.max(best, right - left + 1);
  }
  return best;
}
console.log(lengthOfLongestSubstring('abcabcbb'), lengthOfLongestSubstring('bbbbb'), lengthOfLongestSubstring('pwwkew'), lengthOfLongestSubstring(''), lengthOfLongestSubstring('abba'));
// → 3 1 3 0 2

// Minimum size subarray sum (window menyusut saat syarat terpenuhi)
function minSubArrayLen(target, nums) {
  let left = 0, sum = 0, best = Infinity;
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];
    while (sum >= target) { best = Math.min(best, right - left + 1); sum -= nums[left++]; }
  }
  return best === Infinity ? 0 : best;
}
console.log(minSubArrayLen(7, [2, 3, 1, 2, 4, 3]), minSubArrayLen(4, [1, 4, 4]), minSubArrayLen(11, [1, 1, 1, 1]));
// → 2 1 0

Test case 'abba' di lengthOfLongestSubstring sengaja dimasukkan: tanpa syarat lastSeen.get(ch) >= left, pointer left akan mundur saat bertemu a kedua dan hasilnya salah (3, bukan 2). Test case seperti ini yang membedakan kandidat yang benar-benar menguji kodenya.

Kesalahan umum

1. Memakai two pointers berlawanan arah di array yang belum terurut. Logika "geser kiri kalau kurang" hanya valid kalau terurut. Cara benar: tanyakan "Is the input sorted?"; kalau tidak, sort dulu (O(n log n)) atau pakai hash map.
2. Off-by-one pada ukuran window. Ukuran window adalah right - left + 1, bukan right - left.
3. Pointer kiri mundur. Seperti kasus 'abba'. Cara benar: left = Math.max(left, ...) atau cek indeks terakhir >= left.
4. Memakai sliding window untuk angka negatif. Cara benar: prefix sum + hash map.
5. Menghitung ulang isi window dari nol. Itu kembali ke O(n·k). Cara benar: update state secara incremental (tambah yang masuk, kurangi yang keluar).

Latihan

1. Mudah, Balik array karakter secara in-place dengan O(1) ruang tambahan.
2. Sedang, moveZeroes(nums): pindahkan semua 0 ke akhir dengan urutan elemen bukan-nol tetap, in-place.
3. Menantang, characterReplacement(s, k): panjang substring terpanjang berisi huruf yang sama setelah mengganti paling banyak k huruf.

// 1. Two pointers berlawanan arah
function reverseChars(a) { let l = 0, r = a.length - 1; while (l < r) { [a[l], a[r]] = [a[r], a[l]]; l++; r--; } return a; }
console.log(reverseChars(['h', 'e', 'l', 'l', 'o']).join(''), JSON.stringify(reverseChars([])));
// → olleh []

// 2. Two pointers searah: w = posisi tulis berikutnya untuk angka bukan nol
function moveZeroes(nums) { let w = 0; for (let r = 0; r < nums.length; r++) if (nums[r] !== 0) { [nums[w], nums[r]] = [nums[r], nums[w]]; w++; } return nums; }
console.log(moveZeroes([0, 1, 0, 3, 12]), moveZeroes([0]), moveZeroes([1, 2]));
// → [ 1, 3, 12, 0, 0 ] [ 0 ] [ 1, 2 ]

// 3. Window valid jika (ukuran - frekuensi huruf terbanyak) <= k
function characterReplacement(s, k) {
  const count = {}; let left = 0, maxFreq = 0, best = 0;
  for (let right = 0; right < s.length; right++) {
    count[s[right]] = (count[s[right]] || 0) + 1;
    maxFreq = Math.max(maxFreq, count[s[right]]);
    while (right - left + 1 - maxFreq > k) { count[s[left]]--; left++; }
    best = Math.max(best, right - left + 1);
  }
  return best;
}
console.log(characterReplacement('ABAB', 2), characterReplacement('AABABBA', 1), characterReplacement('', 3));
// → 4 4 0

Ringkasan

• Two pointers berlawanan arah butuh alasan kenapa satu sisi aman dibuang, biasanya karena input terurut.
• Pointer searah (read/write) cocok untuk modifikasi in-place dengan O(1) ruang.
• Sliding window tetap: tambah yang masuk, kurangi yang keluar; dinamis: kanan maju, kiri menyusul.
• while di dalam for tetap O(n) kalau left hanya maju; jelaskan sebagai amortized O(n).
• Sliding window butuh sifat monoton; angka negatif dengan target jumlah tepat butuh prefix sum.