Wawancara Koding: Menghitung Jumlah Pulau dengan DFS Iteratif

Masalah dan Kapan Masalah Ini Berlaku

Diberikan grid m × n yang hanya berisi "1" untuk daratan dan "0" untuk air, kembalikan jumlah pulau. Dua sel daratan terhubung hanya jika keduanya berbagi sisi horizontal atau vertikal. Sebuah pulau adalah himpunan terhubung maksimal dari sel-sel daratan.

Batasannya adalah 1 <= m, n <= 300. Implementasi tetap mengantisipasi array kosong daripada mengubah kontrak pemanggil menjadi kegagalan runtime. Asumsikan grid dapat dimodifikasi. Jika pemanggil harus mempertahankan grid aslinya, gunakan matriks visited berukuran sama sebagai gantinya.

Ini adalah pertanyaan algoritma umum untuk sesi coding rekayasa perangkat lunak. Soal ini menguji apakah seorang kandidat dapat memodelkan matriks sebagai graf implisit, menelusuri komponen terhubung (connected components), dan menjaga implementasi tetap konsisten dengan analisis kompleksitas.

Apa yang Dinilai oleh Pewawancara

Jawaban yang kuat memperlakukan setiap sel daratan sebagai sebuah simpul (vertex) dan setiap keterhubungan daratan 4 arah sebagai sebuah sisi (edge). Hal itu menghasilkan aturan utama: setiap kali pemindaian mencapai daratan yang belum dikunjungi, ia telah menemukan komponen terhubung yang baru. Hitung satu kali, lalu telusuri dan tandai seluruh pulau agar tidak dapat dihitung lagi.

Detail implementasi sangat penting. Tandai tetangga saat di-push, bukan saat di-pop; jika tidak, beberapa sel yang berdekatan dapat me-push sel yang sama. DFS iteratif menghindari call stack bahasa yang dalam ketika sebagian besar grid berupa satu pulau tunggal. Jawaban yang tepat juga menyatakan bahwa penandaan in-place menghilangkan kebutuhan matriks visited, sementara stack eksplisit masih dapat memakan ruang O(mn) pada kasus terburuk.

Jawaban yang lemah hanya mengatakan "gunakan DFS" tanpa mendefinisikan konektivitas, mutasi input, invarian kebenaran, atau uji kasus adversarial.

Pertanyaan Klarifikasi di Awal

Apakah diagonal terhubung? Masalah ini menggunakan empat arah. Jika delapan arah dihitung, perluas daftar arah dan antisipasi beberapa jawaban akan berubah.
Bolehkah input dimodifikasi? Jika ya, ubah sel "1" yang dikunjungi menjadi "0". Jika tidak, gunakan visited, yang mempertahankan batas waktu sambil menambah penyimpanan O(mn).
Apakah grid berbentuk persegi panjang dan tidak kosong? Deskripsi menjamin keduanya; kode produksi tetap dapat mengembalikan 0 untuk input kosong. Jagged array akan memerlukan batasan berdasarkan setiap baris.
Apakah ini satu kali penghitungan statis atau penghitungan setelah setiap penambahan daratan? DFS atau BFS cocok untuk grid statis. Penambahan bertahap lebih cocok menggunakan disjoint set union.
Berapa batas ukuran dan call-stack? Grid 300×300 yang seluruhnya berupa daratan dapat memicu jalur dengan 90.000 pemanggilan rekursif, sehingga solusi ini menggunakan stack eksplisit.

Kerangka Jawaban 30 Detik

"Saya akan memodelkan sel daratan sebagai simpul dalam graf implisit, dengan keterhubungan empat arah sebagai sisi. Saya memindai grid baris demi baris. Setiap 1 yang tersisa memulai komponen terhubung yang belum diproses, jadi saya menambah hitungan pulau dan menjalankan DFS iteratif dari sel tersebut. Saya mengubah tetangga daratan menjadi 0 saat me-push-nya, yang mencegah push duplikat. Setiap sel di-push paling banyak satu kali, dan stack eksplisit menghindari rekursi yang dalam. Kompleksitas waktu adalah O(mn), dan stack adalah O(mn) pada kasus terburuk. Jika mutasi dilarang, saya akan menyimpan status yang sama dalam matriks visited."

Pembahasan Mendalam Langkah Demi Langkah

Langkah 1: Temukan pekerjaan berulang dalam pencarian naif

Memulai pencarian baru dari setiap sel daratan akan menelusuri pulau yang sama berkali-kali. Menemukan tetangga bukanlah bottleneck; bagian yang hilang adalah status yang bertahan di seluruh pencarian dan mencatat bahwa suatu sel sudah menjadi bagian dari komponen yang telah dihitung.

Pemindaian penuh ditambah tanda kunjungan permanen menghilangkan pengulangan tersebut. Mulai penelusuran hanya dari daratan yang belum dikunjungi.

Langkah 2: Tetapkan invarian penghitungan

Ketika pemindaian mencapai (r, c), setiap DFS sebelumnya telah menandai tepat satu pulau lengkap. Jika sel saat ini masih "1", tidak ada penelusuran sebelumnya yang mencapainya, sehingga sel ini harus memulai pulau baru dan hitungan bertambah satu.

DFS hanya mengikuti sisi daratan empat arah, sehingga tidak dapat menyeberangi air dan menggabungkan pulau-pulau yang berbeda. DFS juga mencapai setiap sel daratan yang terhubung ke titik awalnya, sehingga pulau ini tidak dapat memicu penghitungan lain di kemudian hari. Dua fakta tersebut membuktikan tidak adanya undercounting maupun double counting.

Langkah 3: Tandai saat melakukan push

Misalkan sebuah sel yang belum ditandai bersentuhan dengan dua sel yang sudah ada di dalam stack. Jika penandaan menunggu hingga waktu pop, kedua tetangga tersebut dapat me-push sel yang sama. Hasilnya sering kali tetap benar, tetapi stack memuat pekerjaan duplikat dan argumen kompleksitas yang ketat menjadi hilang.

Ubah tetangga yang ditemukan menjadi "0" sebelum me-push-nya. Sisi berikutnya yang memeriksa sel tersebut akan melihatnya sudah dikunjungi, menjamin bahwa setiap sel daratan masuk ke stack paling banyak satu kali.

Langkah 4: Implementasikan DFS iteratif

javascript

function numIslands(grid) {
  if (grid.length === 0 || grid[0].length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  let islands = 0;

  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (grid[row][col] !== "1") continue;

      islands += 1;
      grid[row][col] = "0";
      const stack = [[row, col]];

      while (stack.length > 0) {
        const [currentRow, currentCol] = stack.pop();

        for (const [rowOffset, colOffset] of directions) {
          const nextRow = currentRow + rowOffset;
          const nextCol = currentCol + colOffset;

          if (
            nextRow >= 0 && nextRow < rows &&
            nextCol >= 0 && nextCol < cols &&
            grid[nextRow][nextCol] === "1"
          ) {
            grid[nextRow][nextCol] = "0";
            stack.push([nextRow, nextCol]);
          }
        }
      }
    }
  }

  return islands;
}

Pemindaian memeriksa mn sel. Setiap sel daratan di-push paling banyak satu kali dan memeriksa empat tetangga, sehingga waktunya adalah O(mn). Stack eksplisit dapat menampung O(mn) koordinat pada grid yang seluruhnya daratan. Fungsi ini memutasi inputnya. Menyalin grid sebagai gantinya juga membutuhkan waktu dan ruang O(mn).

Langkah 5: Validasi batasan dan kasus adversarial

Minimal, uji: array kosong mengembalikan 0; satu sel air mengembalikan 0; satu sel daratan mengembalikan 1; semua air mengembalikan 0; semua daratan mengembalikan 1; dua sel yang hanya bersentuhan secara diagonal mengembalikan 2; contoh dengan tiga wilayah terpisah mengembalikan 3; dan grid 300×300 seluruhnya daratan tidak menyebabkan overflow pada call stack rekursif.

Uji juga kontrak mutasi. Jika asersi lain membutuhkan grid asli setelah pemanggilan, salin terlebih dahulu atau gunakan visited. Pilihan ini harus menjadi bagian dari kontrak antarmuka, bukan sebagai detail implementasi yang tersembunyi.

Langkah 6: Bandingkan alternatif

BFS dan DFS iteratif memiliki waktu dan ruang kasus terburuk yang sama di sini. Pilih BFS ketika lapisan jarak diperlukan; keduanya sama-sama sesuai jika satu-satunya tujuan adalah menghabiskan suatu komponen. DFS rekursif lebih ringkas hanya ketika input cukup kecil atau bahasa menjamin kedalaman stack yang cukup. Disjoint set union berguna ketika daratan ditambahkan secara bertahap dan penghitungan diminta setelah setiap penambahan; metode ini menambah pengindeksan dan pemeliharaan himpunan yang tidak perlu untuk penghitungan statis tunggal.

Contoh Jawaban Berkualitas Tinggi

"Masalah ini adalah penghitungan connected-component dalam graf tak berarah implisit. Setiap 1 adalah simpul, dan tetangga daratan horizontal atau vertikal berbagi sisi. Saya memindai seluruh grid. Jika suatu posisi masih 1, tidak ada pencarian sebelumnya yang mencapainya, jadi saya telah menemukan pulau baru dan menambah hitungan. Kemudian saya menjalankan DFS iteratif dan mengubah seluruh pulau itu menjadi 0.

Saya menandai tetangga saat me-push-nya agar dua sel yang berdekatan tidak dapat me-push posisi yang sama. Saya menggunakan stack eksplisit karena grid 300×300 yang seluruhnya daratan dapat menghasilkan jalur rekursif yang sangat dalam. Setiap sel diproses paling banyak satu kali dan memeriksa empat arah, menghasilkan waktu O(mn) dan ruang stack kasus terburuk O(mn). Versi ini memutasi input; jika antarmuka harus mempertahankan input asli, saya akan memindahkan penandaan ke matriks Boolean visited berukuran O(mn). Saya akan memverifikasi kasus ketidakterhubungan diagonal, semua air, semua daratan, dan batas input kosong."

Jawaban ini menghubungkan model, argumen penghitungan, risiko implementasi, efek samping, dan validasi tanpa bergantung pada hafalan istilah.

Kesalahan Umum

Menganggap diagonal terhubung → ini mengubah masalah dan dapat mengurangi hitungan pulau (undercount) → hanya sertakan atas, bawah, kiri, dan kanan dalam daftar arah.
Hanya menandai saat pop → beberapa tetangga dapat me-push sel yang sama → tandai tetangga yang valid segera sebelum me-push.
Mengklaim in-place berarti ruang O(1) → ini mengabaikan stack eksplisit pada kasus terburuk → laporkan ruang tambahan O(mn) pada kasus terburuk.
Menggunakan DFS rekursif tanpa mendiskusikan kedalaman stack → satu pulau besar dapat menghabiskan call stack bahasa pemrograman → gunakan iterasi atau tetapkan batas ukuran yang aman.
Memutasi data pemanggil secara diam-diam → kode berikutnya melihat grid yang sudah dibersihkan → dokumentasikan efek samping atau gunakan visited.
Mencari lagi dari setiap sel daratan → komponen yang sama ditelusuri berulang kali → mulai hanya dari daratan yang belum dikunjungi.
Hanya menguji persegi panjang biasa → contoh uji kasus kosong, semua air, semua daratan, dan diagonal menjadi tidak teruji → cakup kasus minimal, ekstrem, dan adversarial.

Pertanyaan Lanjutan dan Tanggapan

Pertanyaan Lanjutan 1: Bagaimana jika input tidak boleh dimodifikasi?

Alokasikan matriks Boolean m × n dan tandai lokasi sebagai telah dikunjungi saat me-push-nya. Invarian penghitungan dan waktu O(mn) tetap tidak berubah; penyimpanan tambahan secara eksplisit bernilai O(mn). Menyalin input memiliki biaya ruang asimtotik yang sama tetapi semantik yang berbeda.

Pertanyaan Lanjutan 2: Bagaimana jika diagonal juga terhubung?

Perluas daftar arah dari empat offset menjadi delapan; kerangka kerja penelusuran tidak berubah. Konfirmasikan aturannya terlebih dahulu dengan kasus seperti [[1, 0], [0, 1]]: jawaban empat arah adalah 2, sedangkan jawaban delapan arah adalah 1.

Pertanyaan Lanjutan 3: Bagaimana jika daratan ditambahkan satu sel demi satu sel dan penghitungan diminta setiap kali penambahan?

Mengulang DFS statis akan membuang-buang pemrosesan. Gunakan disjoint set union sebagai gantinya: sel daratan baru awalnya menambah hitungan, lalu di-union dengan setiap tetangga daratan yang ada. Setiap penggabungan yang berhasil dari dua himpunan berbeda akan mengurangi hitungan. Penambahan duplikat harus diabaikan agar tidak menambah hitungan dua kali.

Pertanyaan Lanjutan 4: Bagaimana jika rentang koordinat sangat besar tetapi daratannya jarang (sparse)?

Jangan mengalokasikan matriks penuh. Simpan hanya koordinat daratan dalam hash set, telusuri koordinat tersebut, dan periksa empat tetangganya. Dengan k sel daratan, waktu yang diharapkan adalah O(k), dan himpunan kunjungan ditambah stack adalah O(k). Kesimpulan ini memerlukan representasi daftar koordinat renggang (sparse); kesimpulan ini tidak berlaku dari input grid padat (dense).