0Pricing
DSA Interview Prep · Pelajaran

Dua Pointer: Lambat dan Cepat

Terapkan pola pointer lambat-cepat untuk menghapus duplikat secara in-place, memindahkan nol, dan membagi array berdasarkan nilai pivot.

Dua Pointer: Lambat dan Cepat adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 4 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Penjelasan Penunjuk Lambat dan Cepat

Pola penunjuk lambat-cepat (juga disebut kura-kura dan kelinci) menggunakan dua penunjuk yang bergerak dengan kecepatan berbeda melalui urutan yang sama. Berbeda dari penunjuk ujung berlawanan, keduanya mulai dari awal. Penunjuk lambat maju satu langkah setiap kali; penunjuk cepat maju dua langkah (atau lebih). Perbedaan kecepatan ini menciptakan invarian yang berguna: penunjuk lambat melacak "awalan valid", sedangkan penunjuk cepat memindai ke depan untuk mencari kondisi tertentu.

# Slow pointer marks the write position;
# Fast pointer scans for next non-duplicate.

def remove_duplicates(nums):
    if not nums: return 0
    slow = 0  # next position to write a unique value
    for fast in range(1, len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1  # new length

nums = [1, 1, 2, 3, 3, 3, 4]
k = remove_duplicates(nums)
print(nums[:k])  # [1, 2, 3, 4]

Menghapus Duplikat dari Larik Terurut

Dalam larik terurut, duplikat berada berdampingan. Penunjuk lambat melacak nilai unik terakhir yang ditulis; penunjuk cepat memindai ke depan. Setiap kali penunjuk cepat mencapai nilai yang berbeda dari nums[slow], majukan penunjuk lambat dan salin nilai baru tersebut. Algoritme langsung di tempat ini berjalan dalam waktu O(n) dengan ruang tambahan O(1) — soal wawancara standar yang menguji penguasaan pola penunjuk baca-tulis.

def remove_duplicates_v2(nums):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != nums[slow]:
            slow += 1
            nums[slow] = nums[fast]
    return slow + 1

# Allow at most 2 occurrences
def remove_duplicates_k2(nums):
    slow = 0
    for fast in range(len(nums)):
        if slow < 2 or nums[fast] != nums[slow - 2]:
            nums[slow] = nums[fast]
            slow += 1
    return slow

print(remove_duplicates_k2([1,1,1,2,2,3]))
# Result: 5, nums[:5] = [1,1,2,2,3]

Memindahkan Nol dengan Penunjuk Lambat-Cepat

Pindahkan semua angka nol ke akhir dengan tetap mempertahankan urutan relatif elemen yang bukan nol. Penunjuk lambat menandai posisi berikutnya untuk elemen bukan nol. Penunjuk cepat memindai nilai-nilai bukan nol. Saat penunjuk cepat menemukan salah satunya, salin nilai tersebut ke posisi penunjuk lambat dan majukan keduanya. Setelah pemindaian selesai, isi posisi dari penunjuk lambat hingga akhir dengan angka nol. Waktu O(n), ruang O(1).

def move_zeroes(nums):
    slow = 0  # next position for a non-zero
    for fast in range(len(nums)):
        if nums[fast] != 0:
            nums[slow] = nums[fast]
            slow += 1
    # Fill rest with zeroes
    while slow < len(nums):
        nums[slow] = 0
        slow += 1

nums = [0, 1, 0, 3, 12]
move_zeroes(nums)
print(nums)  # [1, 3, 12, 0, 0]

Mempartisi Larik di Sekitar Pivot

Sublangkah partisi dalam quick sort mengatur ulang elemen secara langsung di tempat sehingga semua nilai < pivot berada sebelum nilai >= pivot. Skema Lomuto menggunakan penunjuk lambat (yang menandai posisi terakhir elemen kecil) dan penunjuk cepat (yang memindai ke depan). Saat penunjuk cepat menemukan elemen kecil, naikkan penunjuk lambat lalu tukar kedua elemen. Proses ini berjalan dalam waktu O(n) dengan ruang tambahan O(1).

def lomuto_partition(nums, low, high):
    pivot = nums[high]
    slow = low - 1  # last position of small element
    for fast in range(low, high):
        if nums[fast] <= pivot:
            slow += 1
            nums[slow], nums[fast] = nums[fast], nums[slow]
    # Place pivot in final position
    nums[slow+1], nums[high] = nums[high], nums[slow+1]
    return slow + 1  # pivot's final index

arr = [3, 1, 4, 1, 5, 9, 2, 6]
p = lomuto_partition(arr, 0, len(arr)-1)
print(arr)   # elements before p are <= pivot

Menemukan Titik Tengah Daftar Berantai

Dengan penunjuk lambat-cepat pada daftar berantai, penunjuk cepat maju melewati dua simpul setiap langkah, sedangkan penunjuk lambat maju satu simpul. Saat penunjuk cepat mencapai ujung, penunjuk lambat berada di tengah. Pendekatan satu lintasan O(n) ini jauh lebih sederhana daripada menghitung jumlah simpul lalu berjalan hingga pertengahan. Pendekatan ini digunakan sebagai sublangkah dalam merge sort untuk daftar berantai dan dalam deteksi palindrom pada daftar berantai.

class Node:
    def __init__(self, val, nxt=None):
        self.val = val
        self.next = nxt

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # slow is at middle

# Build 1->2->3->4->5
h = Node(1, Node(2, Node(3, Node(4, Node(5)))))
mid = find_middle(h)
print(mid.val)  # 3  (middle of 5 nodes)

Deteksi Siklus: Kura-kura dan Kelinci Floyd

Deteksi siklus Floyd menempatkan penunjuk lambat dan cepat di kepala daftar berantai. Penunjuk lambat maju satu simpul; penunjuk cepat maju dua simpul. Jika ada siklus, penunjuk cepat pada akhirnya akan menyusul penunjuk lambat dan keduanya bertemu di dalam siklus. Jika penunjuk cepat mencapai None, tidak ada siklus. Pertemuan ini pasti terjadi karena penunjuk cepat memperoleh keunggulan satu langkah atas penunjuk lambat pada setiap iterasi — dalam siklus sepanjang k, keduanya bertemu dalam paling banyak k langkah setelah penunjuk lambat memasuki siklus.

class ListNode:
    def __init__(self, val=0, nxt=None):
        self.val = val
        self.next = nxt

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:  # identity check (same object)
            return True
    return False

# 1->2->3->4->2 (cycle at node 2)
n1 = ListNode(1)
n2 = ListNode(2)
n3 = ListNode(3)
n4 = ListNode(4)
n1.next=n2; n2.next=n3; n3.next=n4; n4.next=n2
print(has_cycle(n1))  # True

Menemukan Titik Masuk Siklus

Setelah mendeteksi siklus (slow == fast), atur ulang salah satu penunjuk ke kepala. Sekarang majukan kedua penunjuk satu langkah setiap kali. Keduanya akan bertemu di titik masuk siklus. Cara ini menggunakan sifat matematis bahwa jarak dari kepala ke titik masuk siklus sama dengan jarak dari titik pertemuan ke titik masuk siklus (modulo panjang siklus). Ini adalah hasil matematis yang indah dan sering muncul dalam soal wawancara yang sulit.

def detect_cycle(head):
    slow = fast = head
    # Phase 1: detect
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None  # no cycle
    # Phase 2: find entry
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next
    return slow  # cycle entry node

# Using same cycled list as previous scene
print(detect_cycle(n1).val)  # 2  (cycle entry)

Penunjuk Lambat-Cepat untuk Bilangan Bahagia

Penunjuk lambat-cepat dapat diterapkan di luar daftar berantai pada proses apa pun yang mengalami siklus. Bilangan bahagia berputar melalui jumlah kuadrat digit — jika n bukan bilangan bahagia, urutannya pada akhirnya berulang. Deteksi perulangan tersebut dengan penunjuk lambat (satu langkah = satu kuadrat digit) dan penunjuk cepat (dua langkah). Jika keduanya bertemu di 1, n adalah bilangan bahagia; jika tidak, n terjebak dalam siklus yang tidak memuat 1. Ini adalah algoritme Floyd yang diterapkan pada daftar berantai virtual berisi nilai.

def is_happy(n):
    def next_val(x):
        total = 0
        while x:
            x, d = divmod(x, 10)
            total += d * d
        return total

    slow = n
    fast = next_val(n)
    while fast != 1 and slow != fast:
        slow = next_val(slow)
        fast = next_val(next_val(fast))
    return fast == 1

print(is_happy(19))   # True  (1->9->...->1)
print(is_happy(2))    # False (enters a cycle)

Simpul ke-N dari Akhir Daftar

Temukan simpul ke-n dari akhir daftar berantai dalam satu lintasan menggunakan dua penunjuk. Majukan penunjuk cepat sebanyak n langkah. Kemudian majukan kedua penunjuk bersama-sama hingga penunjuk cepat mencapai ujung — penunjuk lambat sekarang berada di simpul ke-n dari akhir. Untuk menghapus simpul ini, pertahankan penunjuk "prev" satu langkah di belakang penunjuk lambat. Ini adalah soal daftar berantai satu lintasan klasik yang tidak perlu menghitung panjang total terlebih dahulu.

def remove_nth_from_end(head, n):
    dummy = ListNode(0)
    dummy.next = head
    fast = slow = dummy
    # Advance fast n+1 steps
    for _ in range(n + 1):
        fast = fast.next
    # Advance together
    while fast:
        slow = slow.next
        fast = fast.next
    # slow.next is the nth from end
    slow.next = slow.next.next
    return dummy.next

# Build 1->2->3->4->5, remove 2nd from end
h2 = ListNode(1,ListNode(2,ListNode(3,ListNode(4,ListNode(5)))))
result = remove_nth_from_end(h2, 2)
# Should give 1->2->3->5

Penunjuk Lambat-Cepat dalam Soal Teks

Pemikiran lambat-cepat juga berlaku pada soal larik dan teks. Saat memadatkan teks berkode panjang-runtun, penunjuk lambat menandai posisi penulisan dan penunjuk cepat memindai hingga akhir setiap runtun. Saat semua karakter dalam runtun sama dengan karakter penunjuk lambat, majukan penunjuk cepat; jika tidak, catat runtun tersebut dan perbarui penunjuk lambat. Cara ini mencapai O(n) dalam satu lintasan dengan ruang O(1).

def compress(chars):
    slow = fast = 0
    while fast < len(chars):
        char = chars[fast]
        count = 0
        # Count the run
        while fast < len(chars) and chars[fast] == char:
            fast += 1
            count += 1
        chars[slow] = char
        slow += 1
        if count > 1:
            for c in str(count):
                chars[slow] = c
                slow += 1
    return slow

chars = list('aabcccccaa')
print(compress(chars))  # 6
print(chars[:6])        # ['a','2','b','c','5','a']... wait
# Actually: ['a','2','b','c','5','a','2']

Memilih antara Penunjuk Lambat-Cepat dan Ujung Berlawanan

Gunakan penunjuk ujung berlawanan saat soal melibatkan pasangan yang jumlahnya sama dengan sasaran, pemeriksaan palindrom, atau penyempitan jendela dari kedua sisi. Gunakan penunjuk lambat-cepat saat Anda memerlukan penunjuk penulisan (untuk menghapus atau memindahkan elemen), saat memproses struktur daftar berantai (tengah, siklus), atau saat mendeteksi siklus dalam urutan nilai apa pun. Keduanya menghilangkan perulangan bersarang dan mencapai O(n) — faktor penentunya adalah struktur lintasan.

# Pattern matcher:
# 1. Sorted array, target sum -> OPPOSITE ENDS
# 2. Remove/filter elements in-place -> SLOW-FAST (read-write)
# 3. Linked list middle/cycle -> SLOW-FAST (1x vs 2x speed)
# 4. Detect cycle in value sequence -> SLOW-FAST (Floyd)

# Example: given sorted array, remove val in-place
def remove_sorted(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

nums = [0,1,2,2,3,0,4,2]
print(remove_sorted(nums, 2))  # 5

Pemeriksaan Singkat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.

Rangkuman Pelajaran

Dalam pelajaran ini Anda mempelajari bahwa: pola lambat-cepat (baca-tulis) mempertahankan penunjuk penulisan pada posisi valid berikutnya sementara penunjuk cepat memindai ke depan — menjadi dasar penghapusan, deduplikasi, dan pemindahan nol secara langsung di tempat, kura-kura dan kelinci Floyd mendeteksi siklus dalam waktu O(n) dan ruang O(1) dengan memanfaatkan perbedaan kecepatan antara dua penunjuk, dan setelah mendeteksi siklus, mengatur ulang salah satu penunjuk ke kepala lalu memajukan keduanya dengan kecepatan yang sama akan menemukan titik masuk siklus berdasarkan kesamaan jarak yang dapat dibuktikan. Selanjutnya, kita akan membahas API teks Python untuk wawancara.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Dua Pointer: Lambat dan Cepat” gratis?

Ya — teks lengkap “Dua Pointer: Lambat dan Cepat” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Dua Pointer: Lambat dan Cepat”?

Terapkan pola pointer lambat-cepat untuk menghapus duplikat secara in-place, memindahkan nol, dan membagi array berdasarkan nilai pivot. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?

Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 4 dari 4.

Berapa lama pelajaran “Dua Pointer: Lambat dan Cepat” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Dasar Array dan Operasi In-Place
  2. Jumlah Awalan dan Total Berjalan
  3. Dua Pointer: Ujung Berlawanan
  4. Dua Pointer: Lambat dan Cepat
← Kembali ke DSA Interview Prep