Wawancara Koding: Bagaimana Cara Menyelesaikan Trapping Rain Water dengan Two Pointers?

Masalah dan Skenario yang Berlaku

Diberikan sebuah array bilangan bulat non-negatif height dengan panjang n, height[i] adalah tinggi batang pada indeks i, dan setiap batang memiliki lebar 1. Hitung total air hujan yang tertampung oleh batang-batang ini. Sebagai contoh:

height = [4, 2, 0, 3, 2, 5]
result = 9

Targetnya adalah waktu O(n) dan ruang bantu O(1). Batasan standarnya adalah 1 <= n <= 20000 dan 0 <= height[i] <= 100000. Tinggi batang tidak pernah negatif, dan masalah utama tidak meminta air yang tersimpan di atas setiap batang secara terpisah.

Terdapat bukti wawancara publik langsung untuk pertanyaan ini. Laporan bulan Juni 2025 dari wawancara magang backend Go di Baidu mencantumkan Trapping Rain Water sebagai salah satu dari tiga tugas live coding. Laporan phone-screen publik lainnya menambahkan varian di mana sejumlah air dituangkan pada posisi tertentu yang dipilih. Halaman masalah LeetCode berbahasa Inggris dan Mandarin mengklasifikasikannya sebagai sulit (hard) dan menandainya dengan array, two pointers, pemrograman dinamis (dynamic programming), stack, dan monotonic stack. Keahlian intinya adalah menurunkan dan membuktikan algoritma linier dari rumus lokal, sehingga kategorinya adalah coding terlepas dari bahasa implementasi atau rumpun pekerjaannya.

Apa yang Dievaluasi Pewawancara

Pertama, dapatkah Anda menyatakan jumlah yang benar di atas satu batang? Ketinggian air pada indeks i dibatasi oleh yang lebih pendek di antara batang tertinggi di sebelah kirinya dan batang tertinggi di sebelah kanannya, bukan oleh dua batang yang bertetangga langsung. Jika leftMax[i] dan rightMax[i] keduanya mencakup indeks i, jumlahnya adalah min(leftMax[i], rightMax[i]) - height[i].

Kedua, dapatkah Anda mengompresi array prefix dan suffix menjadi ruang konstan? Menyimpan setiap maksimum kiri dan kanan menghasilkan solusi waktu O(n) yang mudah. Two pointers memanfaatkan observasi yang lebih kuat bahwa batas terkecil yang telah diketahui sudah cukup untuk memfinalisasi satu sisi, satu kolom pada satu waktu.

Ketiga, apakah Anda benar-benar memahami aturan pergerakannya? Mengulang kalimat "geser pointer yang lebih pendek" bukanlah sebuah pembuktian. Jawaban yang kuat menyatakan loop invariant dan menangani kedua kasus: batang saat ini bisa menaikkan batas di sisinya atau tetap berada di bawahnya. Argumen tersebut harus menunjukkan mengapa wilayah yang belum dipindai tidak dapat mengubah jumlah air yang baru saja difinalisasi.

Terakhir, dapatkah Anda membandingkan pendekatan alternatif secara akurat? Array prefix dan suffix adalah yang paling mudah dijelaskan. Monotonic stack menyelesaikan cekungan secara horizontal dan dapat ditransfer secara alami ke masalah stack terkait. Two pointers menggunakan ruang paling sedikit. Ketiganya bisa benar, tetapi memiliki batas ruang, gaya pembuktian, dan ekstensi yang berbeda.

Pertanyaan Klarifikasi Sebelum Menjawab

• Apakah setiap batang memiliki lebar 1? Ya. Jika lebarnya bervariasi, kalikan kedalaman air di setiap kolom dengan lebarnya.
• Apakah tinggi batang dijamin non-negatif? Ya. Tinggi negatif tidak memiliki makna fisik yang terdefinisi di sini dan tidak boleh secara diam-diam menjadi lubang yang lebih dalam.
• Bisakah array-nya kosong? Batasan standar menyatakan tidak. Implementasi ini secara alami mengembalikan 0 untuk array kosong, tetapi kontrak API sebaiknya tetap menyatakannya secara eksplisit.
• Apakah kita mengembalikan jumlah total atau jumlah di setiap indeks? Masalah utama hanya mengembalikan totalnya. Output per-indeks tentu memerlukan ruang O(n).
• Apakah ruang bantu konstan diwajibkan? Ya. Jika tidak, array prefix dan suffix adalah solusi linier yang lebih mudah dikomunikasikan.
• Bisakah tipe numerik mengalami overflow? Hitung batas atas dari batasan yang sebenarnya. Batasan yang lebih besar atau tipe integer yang sempit memerlukan akumulator yang lebih lebar.
• Apakah input berupa profil satu dimensi atau grid dua dimensi? Input berupa satu dimensi. Menampung air dalam grid memerlukan ekspansi batas dari luar ke dalam.
• Bolehkah implementasi memutasi input? Tidak perlu; kode sampel hanya membaca height.

Kerangka Jawaban 30 Detik

"Air di atas satu batang adalah nilai minimum dari batang tertinggi di kedua sisinya dikurangi tinggi batang tersebut. Array prefix dan suffix menghitung semua nilai maksimum tersebut dalam waktu linier tetapi menggunakan ruang O(n). Saya dapat mengompresi state tersebut ke dalam pointer kiri dan kanan ditambah leftMax dan rightMax, yang merupakan batang tertinggi yang sudah dipindai dari masing-masing sisi. Ketika leftMax <= rightMax, batas kanan yang diketahui sudah setidaknya setinggi leftMax. Jika batang kiri saat ini tidak menaikkan leftMax, jumlah airnya sudah pasti sebesar leftMax - height[left]; jika menaikkan batas, jumlah airnya adalah nol. Saya kemudian memajukan pointer kiri. Sisi lainnya bersifat simetris. Setiap indeks difinalisasi tepat satu kali, sehingga waktu komputasinya adalah O(n) dan ruang bantunya adalah O(1)."

Pembahasan Mendalam Langkah demi Langkah

Langkah 1: Tentukan jawaban untuk satu kolom.

Misalkan:

L[i] = max(height[0..i])
R[i] = max(height[i..n-1])
water[i] = min(L[i], R[i]) - height[i]

Baik L[i] maupun R[i] mencakup height[i], sehingga tidak ada yang bisa lebih rendah dari batang saat ini dan rumus tersebut tidak memerlukan pemotongan (clamp) ekstra ke nol. Totalnya adalah jumlah dari semua water[i]. Rumus ini juga menunjukkan mengapa memeriksa batang yang bersebelahan saja akan gagal: batas yang lebih tinggi di kejauhan dapat menentukan permukaan untuk seluruh cekungan.

Langkah 2: Tetapkan baseline yang benar.

Solusi prefix membangun L dari kiri ke kanan dan R dari kanan ke kiri, lalu menerapkan rumus tersebut. Two pointers tidak mendefinisikan ulang jumlah air. Pendekatan ini menggunakan batas-batas yang diketahui dan cukup untuk memfinalisasi sebuah kolom sebelum menyimpan setiap nilai dari L dan R.

Langkah 3: Nyatakan loop invariant.

Pada awal setiap iterasi:

1. Setiap indeks yang secara ketat berada di sebelah kiri left telah difinalisasi sesuai dengan rumus per kolom.
2. Setiap indeks yang secara ketat berada di sebelah kanan right telah difinalisasi dengan benar.
3. leftMax adalah nilai maksimum dari rentang yang telah dipindai height[0..left-1], dengan nilai maksimum kosong berupa 0.
4. rightMax adalah nilai maksimum dari height[right+1..n-1], juga menggunakan 0 untuk rentang kosong.
5. water adalah jumlah air untuk semua indeks yang telah difinalisasi.

Interval yang belum diproses selalu berupa [left, right]. Setiap iterasi harus membuktikan bahwa setidaknya satu ujung dapat difinalisasi secara permanen sebelum mempersempit interval ini.

Langkah 4: Buktikan mengapa sisi dengan batas yang lebih kecil boleh bergerak.

Misalkan leftMax <= rightMax dan perhatikan height[left]:

• Jika batang saat ini lebih tinggi dari leftMax, batang tersebut menjadi batas kiri tertinggi yang baru. Batang tersebut adalah

batas kirinya sendiri, sehingga air yang tertampung adalah 0.

• Jika batang saat ini tidak lebih tinggi dari leftMax, maksimum sebenarnya di sebelah kanannya setidaknya sebesar

rightMax yang telah diamati, dan rightMax >= leftMax. Oleh karena itu, batas yang lebih kecil terkunci pada leftMax, menjadikan jumlah airnya tepat sebesar leftMax - height[left].

Kedua kasus tidak memerlukan bentuk pasti dari bagian tengah yang belum dipindai, sehingga kolom kiri dapat difinalisasi. Jika leftMax > rightMax, pembuktiannya simetris untuk kolom kanan. Ini adalah perbandingan batas maksimum yang diketahui, bukan tebakan berdasarkan batang yang bertetangga.

Langkah 5: Implementasikan algoritma two-pointer.

def trap(height: list[int]) -> int:
    left = 0
    right = len(height) - 1
    left_max = 0
    right_max = 0
    water = 0

    while left <= right:
        if left_max <= right_max:
            left_max = max(left_max, height[left])
            water += left_max - height[left]
            left += 1
        else:
            right_max = max(right_max, height[right])
            water += right_max - height[right]
            right -= 1

    return water

Kondisinya adalah left <= right, sehingga kolom terakhir difinalisasi saat kedua pointer bertemu. Memperbarui batas sebelum menambahkan selisihnya membuat maksimum baru berkontribusi nol dan memastikan setiap penambahan selalu non-negatif. Untuk array kosong, right dimulai dari -1, loop tidak berjalan, dan fungsi mengembalikan 0.

Langkah 6: Telusuri [4, 2, 0, 3, 2, 5].

index  height  side   boundary after update  added water  total
0      4       left   leftMax=4              0            0
5      5       right  rightMax=5             0            0
1      2       left   leftMax=4              2            2
2      0       left   leftMax=4              4            6
3      3       left   leftMax=4              1            7
4      2       left   leftMax=4              2            9

Batang dengan tinggi 5 menyediakan batas kanan yang diketahui cukup tinggi untuk setiap kolom kiri yang tersisa, sehingga algoritma terus memfinalisasi sisi kiri. Setiap kolom muncul tepat satu kali, tanpa ada cekungan yang dihitung dua kali.

Langkah 7: Buktikan terminasi, kebenaran, dan kompleksitas.

Awalnya, kedua rentang yang diproses kosong, sehingga invariant terpenuhi. Langkah 4 membuktikan bahwa kolom yang ditambahkan di setiap iterasi menerima tepat sejumlah air per kolomnya. Memperbarui leftMax atau rightMax mempertahankan definisinya untuk iterasi berikutnya. Setiap iterasi akan menaikkan left atau menurunkan right; setelah sejumlah langkah berhingga, left > right. Pada titik tersebut, setiap indeks telah difinalisasi dengan benar, sehingga jumlah totalnya akurat.

Setiap indeks dikunjungi sekali, menghasilkan waktu O(n). Algoritma ini tidak mengalokasikan memori seukuran input selain hasil skalar tanpa output; dua pointer, dua batas, dan satu akumulator menggunakan ruang bantu O(1).

Langkah 8: Verifikasi terhadap oracle rumus dan kasus-kasus adversarial.

Pengujian tetap harus mencakup satu batang, dua batang, semua bernilai nol, input yang strictly increasing dan decreasing, semua tinggi sama, beberapa cekungan terpisah, cekungan berdasar datar, contoh standar, dan [3, 0, 3]. Kasus terakhir mengungkap implementasi yang salah menggunakan left < right dan melewatkan indeks pertemuan.

Untuk array non-negatif acak berukuran pendek, buat L dan R, gunakan rumus per kolom sebagai oracle, dan bandingkan dengan hasil two-pointer. Periksa juga bahwa hasilnya non-negatif, membalikkan array mempertahankan totalnya, dan menambahkan batang setinggi nol di salah satu ujung luar tidak mengubah total aslinya. Pengujian diferensial menemukan kesalahan implementasi; pembuktian invariant tetap menjadi argumen kebenaran logika.

Contoh Jawaban yang Kuat

"Pertama, saya mereduksi masalah ini menjadi rumus per-indeks. Kedalaman air pada i adalah min(max(height[0..i]), max(height[i..n-1])) - height[i]. Dua array prefix mengimplementasikan rumus tersebut dalam waktu O(n) dan ruang O(n). Untuk memenuhi batasan ruang bantu konstan, saya menggunakan two pointers.

Di dalam loop, leftMax dan rightMax adalah batang tertinggi yang telah dipindai di luar kedua pointer. Jika leftMax <= rightMax, saya memfinalisasi pointer kiri. Jika batang saat ini menaikkan leftMax, jumlah airnya nol. Jika tidak, nilai rightMax yang diketahui sudah setidaknya setinggi batas kiri, sehingga bagian tengah yang belum diketahui tidak dapat menurunkan batas yang lebih kecil di bawah leftMax; jumlahnya pasti sebesar leftMax - height[left]. Saya kemudian menggeser pointer kiri ke dalam. Sisi kanan bersifat simetris.

Setiap iterasi menangani satu kolom secara permanen, sehingga semua kolom selesai saat terminasi. Waktunya adalah O(n), dan pointer, batas, serta akumulator menggunakan ruang bantu O(1). Saya akan menguji input pendek, array monoton dan berunsur sama, beberapa cekungan, serta [3, 0, 3], lalu membandingkan kasus-kasus acak pendek secara diferensial dengan rumus array prefix."

Kesalahan Umum

• Mengurangi dari nilai maksimum yang lebih besar → Air akan tumpah melewati batas yang lebih pendek → Selalu gunakan nilai maksimum yang lebih kecil.
• Hanya memeriksa batang yang bersebelahan → Batas yang jauh diabaikan → Mulailah dari rumus per kolom kiri/kanan yang lengkap.
• Menambahkan sebelum memperbarui batas saat ini → Maksimum baru dapat menghasilkan jumlah negatif → Perbarui terlebih dahulu, baru tambahkan selisih non-negatif.
• Menggunakan left < right → Bagian tengah dari [3, 0, 3] bisa tertinggal tanpa diproses → Sertakan posisi pertemuan dalam loop.
• Memindahkan sisi dengan batas lebih besar tanpa bukti → Sisi berlawanan yang belum diketahui mungkin masih menentukan permukaan yang lebih rendah → Finalisasi hanya sisi yang didukung oleh batas berlawanan yang sudah diketahui.
• Menerapkan rumus Container With Most Water → width × boundary height menghitung ganda batang dan kolom → Jumlahkan kedalaman air di atas setiap batang.
• Menghentikan analisis hanya pada pekerjaan konstan per iterasi → Ini tidak menjelaskan mengapa batang di masa mendatang tidak dapat mengubah jawaban → Nyatakan invariant batas dan pembuktian dua kasus.
• Mengklaim bahwa monotonic stack juga menggunakan ruang O(1) → Input yang monoton dapat mempertahankan n indeks → Laporkan ruang kasus terburuk O(n).
• Hanya menguji contoh yang diilustrasikan → Batas pertemuan, monoton, dan tinggi sama tetap tidak teruji → Tambahkan kasus pengujian tetap dan oracle array prefix.

Pertanyaan Lanjutan dan Tanggapannya

Pertanyaan Lanjutan 1: Mengapa tidak membandingkan height[left] dan height[right] secara langsung?

Formulasi benar lainnya membandingkan tinggi titik ujung saat ini, tetapi memerlukan invariant dan urutan pembaruan yang cocok. Implementasi ini membandingkan leftMax dan rightMax karena nilai-nilai tersebut memetakan langsung ke rumus batas per kolom. Jangan mencampur kondisi dari satu formulasi dengan pembuktian formulasi lainnya; pilih salah satu dan jaga agar kode, penjelasan, serta pembuktian tetap konsisten.

Pertanyaan Lanjutan 2: Bagaimana jika fungsinya harus mengembalikan air di atas setiap batang?

Tulis setiap penambahan yang telah difinalisasi ke dalam array dengan panjang n, lalu jumlahkan atau akumulasikan totalnya pada saat yang sama. Waktu eksekusi tetap O(n), sedangkan output itu sendiri membutuhkan ruang O(n). Jika pemanggil mengonsumsi hasil sebagai stream, perhatikan bahwa two pointers tidak memfinalisasi indeks dalam urutan kiri-ke-kanan; sertakan indeksnya atau susun ulang output yang telah selesai.

Pertanyaan Lanjutan 3: Bagaimana jika tinggi batang hanya tiba sebagai stream dari kiri ke kanan?

Jawaban pasti bergantung pada batas kanan di masa mendatang, sehingga setiap kolom tidak dapat langsung difinalisasi dengan memori tetap. Monotonic stack dapat menahan cekungan terbuka dan menyelesaikannya saat batas kanan yang cukup tinggi tiba, tetapi memori kasus terburuknya tetap O(n). Batasan memori yang ketat memerlukan perkiraan (aproksimasi), penyimpanan eksternal, atau pass kedua; hal ini tidak dapat mempertahankan janji ruang konstan yang eksak seperti semula.

Pertanyaan Lanjutan 4: Bagaimana jika batang memiliki lebar yang berbeda?

Jika batang i secara independen mencakup width[i], logika tinggi batas tetap sama dan volumenya adalah waterDepth[i] * width[i]. Jika input memberikan koordinat tidak beraturan dan celah, tentukan terlebih dahulu tinggi di setiap interval horizontal. Jarak antara pusat batang yang bertetangga tidak serta-merta menjadi lebar dari keseluruhan batang.

Pertanyaan Lanjutan 5: Bagaimana cara menampung air pada peta ketinggian dua dimensi?

Sel grid dibatasi oleh seluruh batas luar, sehingga dua pointer satu arah tidak mencukupi. Algoritma yang umum memasukkan semua sel batas ke dalam min-heap dan secara berulang berekspansi ke dalam dari batas saat ini yang terendah. Tetangga belum dikunjungi yang lebih rendah berkontribusi terhadap selisih ketinggian, dan nilai yang lebih tinggi antara batas dan tetangga menjadi batas efektif untuk ekspansi berikutnya. Dengan set visited, grid m × n membutuhkan waktu O(mn log(mn)) dan ruang O(mn).

Pertanyaan Lanjutan 6: Kapan solusi monotonic-stack lebih disukai?

Stack lebih alami digunakan saat pertanyaan lanjutan menanyakan setiap cekungan yang ditutup oleh batas kiri dan kanan, untuk penjelasan lebar horizontal, atau untuk transisi ke masalah monotonic-stack bergaya histogram. Pendekatan ini menyimpan indeks dalam urutan tinggi yang menurun. Batang yang lebih tinggi mem-pop dasar cekungan; puncak stack yang baru dan batang saat ini membentuk batas-batasnya, dan algoritma menambahkan effective width × new water-layer depth. Total waktu tetap O(n), dengan ruang bantu kasus terburuk O(n).