Penjelasan teknik two pointers dan sliding window

Masalah apa yang diselesaikan teknik ini

Banyak soal array dan string menanyakan pasangan atau rentang berurutan: dua angka yang jumlahnya sama dengan target, substring terpanjang tanpa karakter berulang, subarray terpendek dengan jumlah minimal k. Memeriksa setiap pasangan atau setiap rentang berbiaya O(n²) atau lebih. Two pointers menghindarinya dengan memanfaatkan sifat data, seperti urutan terurut atau fakta bahwa window hanya butuh pembaruan kecil, untuk menyingkirkan banyak kandidat sekaligus.

Pointer dua ujung: jumlah pasangan pada array terurut

Cari dua angka dalam list terurut [1, 3, 4, 6, 8, 11] yang jumlahnya 10. Mulai dari yang terkecil dan terbesar. Jika jumlahnya terlalu kecil, satu-satunya cara menaikkannya adalah menggeser left ke kanan; jika terlalu besar, geser right ke kiri.

def pair_with_sum(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return left, right
        if s < target:
            left += 1
        else:
            right -= 1
    return None
print(pair_with_sum([1, 3, 4, 6, 8, 11], 10))   # (2, 3)
print(pair_with_sum([1, 3, 4, 6, 8, 11], 2))    # None

Setiap langkah menggeser satu pointer ke dalam, sehingga paling banyak ada n − 1 langkah: waktu O(n) dan ruang O(1). Bentuk yang sama dipakai untuk memeriksa apakah string palindrom, membalik array di tempat, dan, di dalam perulangan luar, menyelesaikan 3Sum dalam O(n²) alih-alih O(n³).

Pointer cepat dan lambat: memfilter di tempat

Pointer lambat menandai posisi untuk elemen berikutnya yang dipertahankan; pointer cepat memindai setiap elemen. Cara ini menghapus duplikat dari list terurut tanpa memori tambahan.

def dedupe_sorted(nums):
    """Remove duplicates in place; return the new length."""
    if not nums:
        return 0
    slow = 0
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1
a = [1, 1, 2, 3, 3, 3, 5]
k = dedupe_sorted(a)
print(k, a[:k])   # 4 [1, 2, 3, 5]

Pada linked list, pointer cepat bergerak dua node per langkah dan pointer lambat satu node. Jika keduanya bertemu, berarti list memiliki siklus (deteksi siklus Floyd); ketika pointer cepat mencapai ujung, pointer lambat berada di tengah.

Sliding window: substring terpanjang tanpa pengulangan

Sliding window menjaga rentang s[left:right + 1] tetap valid. Majukan right satu karakter setiap kali. Ketika karakter baru melanggar aturan, majukan left sampai window valid lagi. Catat window terbaik sepanjang jalan.

def longest_unique(s):
    last_seen = {}          # char -> last index
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last_seen and last_seen[ch] >= left:
            left = last_seen[ch] + 1   # jump past the repeat
        last_seen[ch] = right
        best = max(best, right - left + 1)
    return best
print(longest_unique("abcabcbb"))   # 3  ("abc")
print(longest_unique("pwwkew"))     # 3  ("wke")
print(longest_unique(""))           # 0

Window ada dua jenis. Window berukuran tetap k elemen menambahkan elemen yang masuk di kanan dan membuang elemen yang keluar di kiri, misalnya untuk menghitung rata-rata bergerak. Window berukuran variabel membesar dan mengecil untuk memenuhi suatu kondisi, seperti contoh di atas.

def min_len_subarray(nums, k):
    """Shortest subarray with sum >= k (non-negative nums)."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(nums):
        total += x
        while total >= k:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best
print(min_len_subarray([2, 3, 1, 2, 4, 3], 7))   # 2  ([4, 3])

Kompleksitas waktu dan ruang

Alasan sliding window berkompleksitas O(n) walaupun ada perulangan while bersarang: left dan right masing-masing maju paling banyak n kali secara total, sehingga total pekerjaannya paling banyak 2n langkah.

Kesalahan umum

• Memakai pointer dua ujung pada data tak terurut. Keputusan menggeser ke kiri atau kanan hanya benar karena array-nya terurut.
• Memakai sliding window berbasis jumlah ketika angka bisa negatif. Mempersempit window tidak lagi selalu menurunkan jumlah; pakai prefix sum dengan hash map sebagai gantinya.
• Panjang window off-by-one: window left..right inklusif memiliki right - left + 1 elemen.
• Lupa berhenti pada left < right, yang membuat satu elemen berpasangan dengan dirinya sendiri.
• Menggeser left mundur. Pada contoh substring, pengecekan last_seen[ch] >= left mencegah lompatan kembali ke posisi lama.

Kapan memakainya, dan soal wawancara yang umum

Gunakan two pointers ketika input terurut (atau bisa diurutkan dengan murah) dan Anda mencari pasangan, atau ketika perlu memodifikasi array di tempat. Gunakan sliding window ketika soal menyebut subarray atau substring yang berurutan dan meminta yang terpanjang, terpendek, maksimum, atau jumlah dengan kondisi yang berubah secara terprediksi saat window membesar. Jika datanya tak terurut dan Anda butuh pasangan, hash set biasanya lebih sederhana dan juga O(n).

• Two Sum II (input terurut), 3Sum, Container With Most Water, Trapping Rain Water.
• Valid Palindrome, Reverse String, Move Zeroes, Remove Duplicates from Sorted Array.
• Longest Substring Without Repeating Characters, Minimum Window Substring, Sliding Window Maximum (dengan deque).
• Linked List Cycle, Middle of the Linked List.

Di luar wawancara, ide yang sama muncul pada penggabungan file terurut, protokol jaringan yang melacak window paket yang belum dikonfirmasi (TCP sliding window), rate limiter yang menghitung kejadian dalam N detik terakhir, dan rata-rata bergerak pada data deret waktu.