Belajar Algoritm - Sliding Window & Two Pointer

#Pendahuluan

Setelah di episode 9 kita membahas divide & conquer tingkat lanjut, pada episode ini kita beralih ke dua teknik yang lebih praktis dan langsung untuk masalah array/string: Sliding Window dan Two Pointer. Keduanya mengubah brute force O(n²) menjadi O(n) dengan memanfaatkan struktur data linear — tidak ada rekursi, hanya dua indeks yang bergerak.

Kedua teknik ini sangat sering muncul di coding interview — bukan karena soalnya rumit, tetapi karena mereka menguji pemahaman tentang bagaimana menghindari perhitungan ulang yang tidak perlu.

#Sliding Window

Sliding window mempertahankan "jendela" (subarray/substring) yang bergerak melalui array. Alih-alih menghitung ulang dari nol setiap kali, jendela ditambah satu elemen di kanan dan dikurangi satu elemen di kiri.

#Fixed-Size Window

Jendela berukuran tetap — bergeser satu posisi ke kanan setiap langkah.

def max_sum_subarray(arr, k):
    """Sum maksimum dari subarray panjang k"""
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

Tanpa sliding window: O(n × k) — hitung ulang sum setiap window. Dengan sliding window: O(n) — tambah elemen baru, hapus elemen lama.

#Dynamic Window

Ukuran jendela berubah berdasarkan kondisi. Kanan selalu bergerak maju; kiri bergerak maju hanya ketika kondisi dilanggar.

def longest_substring_no_repeat(s):
    """Panjang substring terpanjang tanpa karakter berulang"""
    char_set = set()
    left = 0
    max_len = 0
    for right in range(len(s)):
        while s[right] in char_set:
            char_set.remove(s[left])
            left += 1
        char_set.add(s[right])
        max_len = max(max_len, right - left + 1)
    return max_len

Kiri hanya bergerak ketika ada duplikat → setiap elemen dimasukkan dan dikeluarkan paling banyak sekali → O(n).

#Prefix Sum untuk Window Problems

Prefix sum memungkinkan kita menghitung sum subarray [i..j] dalam O(1) setelah O(n) preprocessing:

def subarray_sum_equals_k(arr, k):
    """Hitung jumlah subarray dengan sum = k"""
    prefix_sum = {0: 1}
    current_sum = 0
    count = 0
    for num in arr:
        current_sum += num
        if current_sum - k in prefix_sum:
            count += prefix_sum[current_sum - k]
        prefix_sum[current_sum] = prefix_sum.get(current_sum, 0) + 1
    return count

Ini mengubah O(n²) brute force menjadi O(n).

#Two Pointer

Two pointer menggunakan dua indeks yang bergerak dalam pola tertentu — bukan untuk mempertahankan window, tetapi untuk mengeksplorasi pasangan secara efisien.

#Converging (Pair Sum)

Dua pointer mulai dari ujung bergerak ke tengah — berguna untuk array terurut:

def two_sum_sorted(arr, target):
    """Cari pasangan dengan jumlah target di array terurut"""
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target:
            return [left, right]
        elif current < target:
            left += 1
        else:
            right -= 1
    return []

#Expanding (Palindrome)

Dua pointer mulai dari tengah, bergerak ke luar — cocok untuk palindrom:

def longest_palindrome(s):
    """Palindrome terpanjang dari string s"""
    def expand_from_center(left, right):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    result = ""
    for i in range(len(s)):
        odd = expand_from_center(i, i)
        even = expand_from_center(i, i + 1)
        result = max(result, odd, even, key=len)
    return result

#Chasing (Cycle Detection di Linked List)

Floyd's cycle detection — pointer lambat (1 langkah) dan pointer cepat (2 langkah). Jika ada cycle, mereka akan bertemu.

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            return True
    return False

#Praktik

1. Sliding window: "Longest substring without repeating characters" (dynamic window).
2. Two pointer: "Container with most water" (converging).
3. Prefix sum: "Subarray sum equals K."

#Penutup

Pada episode 10 ini, kalian telah memahami:

• Sliding window fixed: O(n) untuk sum/rata-rata subarray panjang tetap.
• Sliding window dynamic: O(n) untuk kondisi yang bisa dilanggar dengan kiri mengejar kanan.
• Prefix sum: O(1) query sum subarray setelah O(n) preprocessing.
• Two pointer: converging (pair sum), expanding (palindrome), chasing (cycle detection).

Di episode 11 selanjutnya kita akan membahas Backtracking — teknik eksplorasi sistematis untuk masalah seperti N-Queens, Sudoku solver, dan generate semua permutasi dengan pruning. Sampai jumpa di episode 11!