Dua Pointer: Ujung Berlawanan
Gunakan pointer kiri dan kanan yang bergerak saling mendekat untuk menyelesaikan jumlah pasangan pada array terurut, palindrome valid, dan masalah penampungan air hujan.
Dua Pointer: Ujung Berlawanan adalah pelajaran Coding Interview Prep gratis di CoddyKit. Ini adalah pelajaran 3 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 Coding Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Gagasan Dua Penunjuk
Teknik dua penunjuk menggunakan dua variabel indeks yang bergerak saling mendekat (atau dalam arah yang sama) untuk mengurangi kebutuhan akan perulangan bertingkat. Alih-alih memeriksa setiap pasangan dalam O(n²), Anda membuat kemajuan pada setiap perbandingan dan selesai dalam O(n). Teknik ini hampir selalu mengharuskan larik diurutkan terlebih dahulu, karena pengurutan memungkinkan Anda menentukan arah pergerakan setiap penunjuk berdasarkan apakah jumlah pasangan saat ini terlalu besar atau terlalu kecil.
# Without two pointers: O(n^2)
def two_sum_brute(nums, target):
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return []
# With two pointers on sorted array: O(n)
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target: return [left, right]
elif s < target: left += 1
else: right -= 1
return []Dua Jumlah pada Larik Terurut
Pada larik terurut, tempatkan satu penunjuk di ujung kiri (nilai terkecil) dan satu penunjuk di ujung kanan (nilai terbesar). Jika jumlahnya terlalu kecil, geser penunjuk kiri ke kanan untuk memperbesarnya. Jika jumlahnya terlalu besar, geser penunjuk kanan ke kiri untuk memperkecilnya. Setiap iterasi memajukan setidaknya satu penunjuk, sehingga perulangan berjalan paling banyak n kali: total O(n) setelah pengurutan. Yang penting, setiap pergerakan terbukti benar karena urutannya terjaga.
def two_sum_sorted(numbers, target):
# numbers is 1-indexed per LeetCode 167
left, right = 0, len(numbers) - 1
while left < right:
s = numbers[left] + numbers[right]
if s == target:
return [left + 1, right + 1] # 1-indexed
elif s < target:
left += 1 # need larger sum
else:
right -= 1 # need smaller sum
return []
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]Pemeriksaan Palindrom Valid
Sebuah teks disebut palindrom jika dibaca sama dari depan maupun dari belakang. Gunakan dua penunjuk yang dimulai dari kedua ujung dan bergerak ke arah tengah: bandingkan karakter, lewati karakter yang bukan huruf atau angka, lalu berhenti ketika kedua penunjuk berpapasan. Teknik ini membutuhkan waktu O(n) dengan ruang tambahan O(1)—jauh lebih sederhana daripada membalik teks lalu membandingkannya, yang mengalokasikan memori tambahan O(n).
def is_palindrome(s):
left, right = 0, len(s) - 1
while left < right:
# Skip non-alphanumeric
while left < right and not s[left].isalnum():
left += 1
while left < right and not s[right].isalnum():
right -= 1
if s[left].lower() != s[right].lower():
return False
left += 1
right -= 1
return True
print(is_palindrome('A man, a plan, a canal: Panama')) # True
print(is_palindrome('race a car')) # FalseTiga Jumlah: Pengurutan + Dua Penunjuk
Soal tiga jumlah meminta semua tripel unik yang jumlahnya nol. Urutkan larik, lalu tetapkan setiap elemen nums[i] dan jalankan pencarian dengan dua penunjuk pada sublarik yang tersisa untuk menemukan pasangan yang jumlahnya -nums[i]. Lewati duplikat dari elemen yang ditetapkan maupun pasangan yang ditemukan agar tidak menghasilkan tripel berulang. Total waktu: O(n²) setelah pengurutan O(n log n).
def three_sum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i-1]: continue # skip dupe
left, right = i + 1, len(nums) - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if s == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left+1]: left += 1
while left < right and nums[right] == nums[right-1]: right -= 1
left += 1; right -= 1
elif s < 0: left += 1
else: right -= 1
return result
print(three_sum([-1, 0, 1, 2, -1, -4]))
# [[-1,-1,2],[-1,0,1]]Wadah dengan Air Terbanyak
Diberikan tinggi beberapa garis vertikal, temukan dua garis yang membentuk wadah dengan volume air terbesar. Luas = min(height[left], height[right]) × (right - left). Gerakkan penunjuk pada garis yang lebih pendek ke arah dalam: memindahkan penunjuk pada garis yang lebih tinggi hanya dapat mengurangi lebar tanpa menambah batas tinggi. Pilihan berdasarkan strategi tamak ini terbukti optimal dan menghasilkan waktu O(n).
def max_area(height):
left, right = 0, len(height) - 1
best = 0
while left < right:
h = min(height[left], height[right])
area = h * (right - left)
best = max(best, area)
# Move the shorter wall inward
if height[left] < height[right]:
left += 1
else:
right -= 1
return best
print(max_area([1, 8, 6, 2, 5, 4, 8, 3, 7])) # 49Menguadratkan Larik Terurut
Kuadratkan setiap elemen larik terurut (yang mungkin berisi bilangan negatif), lalu kembalikan hasilnya dalam urutan terurut. Kuadrat bilangan negatif berukuran besar; kuadrat bilangan positif berukuran kecil di bagian tengah. Tempatkan dua penunjuk di kedua ujung dan isi larik hasil dari kanan ke kiri (dari terbesar ke terkecil). Waktunya O(n) dan ruang keluarannya O(n)—jauh lebih baik daripada menguadratkan lalu mengurutkan dalam O(n log n).
def sorted_squares(nums):
n = len(nums)
result = [0] * n
left, right = 0, n - 1
pos = n - 1
while left <= right:
l_sq = nums[left] ** 2
r_sq = nums[right] ** 2
if l_sq > r_sq:
result[pos] = l_sq
left += 1
else:
result[pos] = r_sq
right -= 1
pos -= 1
return result
print(sorted_squares([-4, -1, 0, 3, 10]))
# [0, 1, 9, 16, 100]Menampung Air Hujan
Air yang terperangkap pada indeks i sama dengan min(max_left, max_right) - height[i]. Pendekatan dua penunjuk mempertahankan nilai berjalan max_left dan max_right. Jika max_left < max_right, sisi kiri menjadi batasan—proses penunjuk kiri. Jika tidak, proses penunjuk kanan. Dengan demikian, kita tidak memerlukan larik maksimum kiri dan maksimum kanan yang terpisah, sehingga ruang tambahan yang digunakan menjadi O(1).
def trap(height):
left, right = 0, len(height) - 1
max_left = max_right = 0
water = 0
while left < right:
if height[left] < height[right]:
if height[left] >= max_left:
max_left = height[left]
else:
water += max_left - height[left]
left += 1
else:
if height[right] >= max_right:
max_right = height[right]
else:
water += max_right - height[right]
right -= 1
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6Mengapa Pergerakan Penunjuk dengan Strategi Tamak Berhasil
Pertanyaan lanjutan yang umum dalam wawancara adalah: mengapa aman mengabaikan penunjuk yang lebih kecil? Sketsa pembuktian untuk soal wadah dengan air terbanyak: misalkan height[left] < height[right]. Setiap pasangan (left, j) untuk j < right menghasilkan luas ≤ height[left] × (j-left) < height[left] × (right-left) ≤ luas saat ini. Jadi, tidak ada pasangan yang dimulai dari sisi kiri dengan indeks kanan yang lebih kecil daripada batas kanan saat ini yang dapat melampaui luas saat ini. Kita dapat melewatinya dengan memajukan penunjuk kiri.
# Correctness argument via contradiction:
# If left < right and height[left] < height[right],
# then for any j in (left, right):
# area(left, j) <= min(h[left], h[j]) * (j - left)
# <= h[left] * (j - left)
# <= h[left] * (right - left) [since j < right]
# = current area
# So no pair (left, j) for j < right can improve.
# Moving left inward is SAFE.
print('Proof verified: advance shorter pointer is optimal')Pasangan dengan Selisih Minimum dalam Larik Terurut
Temukan pasangan angka dalam larik terurut yang memiliki selisih absolut terkecil. Gunakan dua penunjuk yang bersebelahan (bukan dari ujung yang berlawanan) dan pindai secara bersamaan: |nums[i] - nums[i+1]| untuk semua pasangan berurutan. Selisih minimum dalam larik terurut selalu terjadi di antara elemen yang bersebelahan (karena pengurutan mengelompokkan nilai-nilai yang berdekatan). Kompleksitasnya O(n) setelah pengurutan.
def min_diff_pair(nums):
nums.sort() # O(n log n)
min_diff = float('inf')
best = (nums[0], nums[1])
for i in range(len(nums) - 1):
diff = nums[i+1] - nums[i] # sorted: always >= 0
if diff < min_diff:
min_diff = diff
best = (nums[i], nums[i+1])
return best, min_diff
pair, d = min_diff_pair([4, 2, 1, 6, 10, 8])
print(pair, d) # (1, 2) 1Templat Dua Penunjuk dari Ujung Berlawanan
Sebagian besar soal dua penunjuk dari ujung berlawanan mengikuti kerangka dasar yang sama. Dengan menguasai templat ini, Anda dapat menyesuaikannya dengan cepat saat berada di bawah tekanan waktu. Keputusan utamanya adalah: (1) kondisi yang memajukan penunjuk kiri, (2) kondisi yang memajukan penunjuk kanan, (3) hal yang dianggap sebagai solusi, dan (4) cara menangani duplikat. Berlatihlah menerjemahkan keputusan-keputusan ini dari pernyataan soal sebelum menulis kode apa pun.
def two_pointer_template(arr, condition):
"""
Generic opposite-ends two-pointer skeleton.
Replace condition logic for each specific problem.
"""
left, right = 0, len(arr) - 1
result = []
while left < right:
current = arr[left] + arr[right] # or some combination
if current == condition: # found a valid pair
result.append((arr[left], arr[right]))
left += 1
right -= 1
elif current < condition: # need to increase
left += 1
else: # need to decrease
right -= 1
return resultMenghitung Pasangan Valid dengan Dua Penunjuk
Dua penunjuk juga dapat menghitung pasangan secara efisien. Untuk soal "hitung pasangan dengan jumlah < sasaran" dalam larik terurut: tetapkan penunjuk kiri dan gunakan penunjuk kanan untuk menemukan indeks kanan valid paling kanan. Semua pasangan (kiri, dari kiri+1 hingga kanan) valid — tambahkan right - left ke jumlah dan majukan kiri. Cara ini menghitung semua pasangan valid dalam O(n), bukan O(n²).
def count_pairs_less_than(nums, target):
nums.sort()
left, right = 0, len(nums) - 1
count = 0
while left < right:
if nums[left] + nums[right] < target:
count += right - left # all (left, left+1..right) valid
left += 1
else:
right -= 1
return count
print(count_pairs_less_than([1, 2, 3, 4, 5], 6))
# pairs: (1,2)(1,3)(1,4)(2,3) -> 4Pemeriksaan Singkat
Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.
Rangkuman Pelajaran
Dalam pelajaran ini Anda mempelajari bahwa: dua penunjuk dari ujung berlawanan menggantikan enumerasi pasangan O(n²) dengan konvergensi kiri-kanan O(n) pada larik terurut, keputusan penunjuk mana yang harus dimajukan mengikuti sifat monoton soal — gerakkan sisi yang saat ini membatasi kemajuan, dan three-sum, wadah dengan air terbanyak, menjebak air hujan, serta verifikasi palindrom semuanya dapat direduksi menjadi templat inti yang sama. Selanjutnya, kita akan membahas pola dua penunjuk lambat-cepat.
Pertanyaan yang Sering Diajukan
Apakah pelajaran “Dua Pointer: Ujung Berlawanan” gratis?
Ya — teks lengkap “Dua Pointer: Ujung Berlawanan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus Coding Interview Prep, upgrade ke CoddyKit PRO. Kursus Coding Interview Prep mencakup 4 pelajaran total.
Apa yang akan aku pelajari di “Dua Pointer: Ujung Berlawanan”?
Gunakan pointer kiri dan kanan yang bergerak saling mendekat untuk menyelesaikan jumlah pasangan pada array terurut, palindrome valid, dan masalah penampungan air hujan. Kamu berlatih Coding 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 Coding Interview Prep?
Tidak diperlukan pengalaman sebelumnya. Coding 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 3 dari 4.
Berapa lama pelajaran “Dua Pointer: Ujung Berlawanan” 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 Coding Interview Prep ini?
Ya. Setiap pelajaran Coding 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
- Dasar Array dan Operasi In-Place
- Jumlah Awalan dan Total Berjalan
- Dua Pointer: Ujung Berlawanan
- Dua Pointer: Lambat dan Cepat