Solusi Leetcode - Trapping Rain Water

Menghitung berapa banyak air hujan yang bisa terperangkap di antara bar kelihatannya kayak soal geometri yang rumit di awal. Air di posisi mana pun dibatasi oleh yang lebih pendek dari dua bar tertinggi di kedua sisinya. Observasi ini membawa saya ke solusi two pointer yang berjalan dalam O(n) time, bukan pendekatan O(n²) yang saya pakai di awal.

Memahami Soalnya

Diberikan sebuah elevation map dalam bentuk array berisi ketinggian, hitung berapa banyak air hujan yang bisa terperangkap. Air terperangkap di sebuah posisi kalau ada bar yang lebih tinggi di kedua sisinya. Yang lebih kecil dari tinggi maksimum di kedua sisi menentukan level airnya. Kurangi dengan tinggi di posisi i untuk menghitung kedalaman airnya, dengan kedalaman minimum nol.

Pendekatan Pertama Saya

Solusi awal saya simpel tapi nggak efisien. Untuk setiap posisi, saya mencari tinggi maksimum di kiri dan kanan, lalu menghitung air yang terperangkap.

function trapNaive(heights) {
  let total = 0;

  for (let i = 0; i < heights.length; i++) {
    // Find max on left
    let leftMax = 0;
    for (let j = 0; j < i; j++) {
      leftMax = Math.max(leftMax, heights[j]);
    }

    // Find max on right
    let rightMax = 0;
    for (let j = i + 1; j < heights.length; j++) {
      rightMax = Math.max(rightMax, heights[j]);
    }

    // Water trapped at this position
    const water = Math.min(leftMax, rightMax) - heights[i];
    if (water > 0) {
      total += water;
    }
  }

  return total;
}

Pendekatan ini butuh O(n²) time karena dia memindai kedua sisi lagi untuk setiap posisi.

Insight Two Pointers

Solusi yang udah dioptimasi pakai dua pointer yang mulai dari kedua ujung dan melacak tinggi maksimum yang sejauh ini udah terlihat. Kita selalu memproses sisi dengan maksimum yang lebih kecil karena sisi itulah yang membatasi level air.

Algoritmanya bekerja kayak gini:

• Mulai dengan pointer di kedua ujung
• Lacak tinggi maksimum yang terlihat di tiap sisi sambil bergerak
• Proses dari sisi dengan maksimum yang lebih kecil (sisi yang membatasi)
• Bergerak ke dalam, sambil meng-update nilai maksimum

Setiap pointer bergerak ke arah tengah, dan algoritmanya memproses setiap posisi sekali.

Implementasi two pointer

function trap(heights) {
  let left = 0;
  let right = heights.length - 1;
  let storedWater = 0;
  let leftMax = 0; // Max height seen from left
  let rightMax = 0; // Max height seen from right

  while (left <= right) {
    // Process from the side with smaller max (the limiting side)
    if (leftMax <= rightMax) {
      // Process left side
      if (heights[left] < leftMax) {
        // Can trap water here
        storedWater += leftMax - heights[left];
      } else {
        // Update leftMax
        leftMax = heights[left];
      }
      left++;
    } else {
      // Process right side
      if (heights[right] < rightMax) {
        // Can trap water here
        storedWater += rightMax - heights[right];
      } else {
        // Update rightMax
        rightMax = heights[right];
      }
      right--;
    }
  }

  return storedWater;
}

Kenapa sisi yang membatasi itu aman

Algoritma ini bekerja karena kita selalu memproses sisi dengan maksimum yang lebih kecil:

• Untuk bar yang lebih rendah dari maksimum terkecil yang udah diketahui, min(leftMax, rightMax) menentukan level air di posisi itu
• Dengan memproses sisi yang membatasi, kita tahu level air nggak bisa melebihi maksimum sisi itu
• Kita nggak perlu tahu nilai-nilai berikutnya di sisi lain karena kita udah memproses faktor pembatasnya
• Sambil bergerak ke dalam, kita meng-update nilai maksimum, jadi informasi yang kita punya selalu akurat

Contoh Langkah demi Langkah

Untuk [0,1,0,2,1,0,1,3,2,1,2,1], pointer-nya bergerak seperti ini:

• Awal: left=0, right=11, leftMax=0, rightMax=0
• leftMax <= rightMax, proses kiri: height[0]=0, leftMax=0, nggak ada air (tinggi sama dengan max), leftMax tetap 0, left=1
• leftMax <= rightMax, proses kiri: height[1]=1, leftMax=1, nggak ada air, leftMax=1, left=2
• leftMax > rightMax, proses kanan: height[11]=1, rightMax=1, nggak ada air, right=10
• leftMax <= rightMax, proses kiri: height[2]=0, leftMax=1, water += 1-0 = 1, left=3
• Lanjutkan proses...

Maksimum terkecil yang udah diketahui itu cukup untuk menghitung air di posisi yang dipilih. Sisi lainnya udah punya batas yang setidaknya setinggi itu.

Kenapa Pendekatan Ini Lebih Baik

Time Complexity: O(n)

• Satu kali pass melewati array
• Setiap elemen diproses tepat satu kali
• Nggak perlu nested loop

Space Complexity: O(1)

• Cuma pakai beberapa variabel untuk pointer dan nilai maksimum
• Nggak perlu struktur data tambahan

Efisiensi

• Turun dari O(n²) ke O(n)
• Jauh lebih cepat untuk input yang besar

Kesalahan yang Sering Terjadi

Waktu mengimplementasikan ini, perhatikan hal-hal berikut:

1. Memproses sisi yang salah: Selalu proses dari sisi dengan maksimum yang lebih kecil
2. Nggak meng-update nilai maksimum dengan benar: Pastikan leftMax/rightMax di-update waktu ketemu bar yang lebih tinggi
3. Edge case: Array kosong atau array dengan kurang dari 3 elemen nggak bisa menampung air

Ringkasan soal air hujan

• Two pointers dari kedua ujung bisa menyelesaikan banyak soal array dengan efisien
• Lacak nilai maksimum sambil jalan, jangan dihitung ulang
• Proses sisi yang membatasi duluan karena sisi itu yang menentukan level air
• Ini menurunkan time complexity dari O(n²) ke O(n) dengan O(1) space

Melacak nilai maksimum sambil bergerak ke dalam menghasilkan O(n) time dan O(1) space.