En çok su tutan kap

Problem

Yan yana dizilmiş dikey çubukların yükseklikleri bir dizi olarak veriliyor; çubuklar arası mesafe 1 birim. Herhangi iki çubuğu kabın iki duvarı olarak seçiyorsun; aradaki diğer çubuklar yok sayılıyor (suyu engellemiyor). Kabın tutabileceği su miktarı, iki duvar arasındaki mesafe ile kısa olan duvarın yüksekliğinin çarpımı. En fazla su tutan duvar çiftinin alanını döndür.

Girdi:  [2, 7, 3, 1, 6, 4, 8, 2]
Çıktı:  35         (index 1 ve 6: mesafe 5, min(7, 8) = 7)

Girdi:  [4, 4, 4, 4]
Çıktı:  12         (en dıştaki iki çubuk: 3 × 4)

Netleştirme soruları

• Aradaki çubuklar suyu bölüyor mu? (Hayır; bu, Trapping Rain Water'dan farkı.)
• Yükseklik 0 olabilir mi? Dizi 2'den kısa olabilir mi? (Cevap 0.)
• Çarpım int'e sığar mı? (10⁵ × 10⁴ = 10⁹, sığar; daha büyük girdide long.)
• Sadece alan mı, duvarların index'leri de mi isteniyor?

İpuçları

Yaklaşım

Brute force: Tüm (i, j) çiftlerinin alanını hesapla, maksimumu al. O(n²) zaman; n = 10⁵ için 5×10⁹ işlem, zaman aşımı.

Optimal, iki uçtan içeri iki işaretçi: left = 0, right = n-1 ile başla. Her adımda alanı hesapla ve kısa olan duvarı içeri al.

Neden doğru? Bunu bir eleme argümanıyla kanıtlarız: h[left] < h[right] olsun. left'i duvar olarak kullanan ve right'tan daha içerideki bir j ile kurulan her kapın alanı (j - left) × min(h[left], h[j]) ≤ (j - left) × h[left] < (right - left) × h[left] olur. Yani left'in mevcut eşleşmesinden daha iyisi yoktur ve left güvenle elenebilir. Her adımda bir çubuk elenir, n-1 adımda tarama biter ve hiçbir aday kaçırılmaz.

Yükseklikler eşitse hangisini hareket ettirdiğin önemli değil: ikisi de mevcut genişlikten daha iyi bir kap kuramaz (diğer duvar en az o yükseklikte olsa bile genişlik azalır, yükseklik artmaz).

Sık görülen yanlış sezgi: "uzun duvarı içeri alırsam belki daha uzun bir duvar bulurum". Bulsan bile yükseklik kısa duvarla sınırlı kaldığı için alan artmaz.

Java çözümü

public final class ContainerWithMostWater {

    public int maxArea(int[] heights) {
        int left = 0, right = heights.length - 1;
        int best = 0;
        while (left < right) {
            int width = right - left;
            int area = width * Math.min(heights[left], heights[right]);
            best = Math.max(best, area);
            // Kısa olan duvar alanı sınırlıyor; onu tutup genişliği daraltmak asla daha iyi sonuç vermez
            if (heights[left] < heights[right]) {
                left++;
            } else {
                right--;
            }
        }
        return best;
    }
}

Karmaşıklık

• Zaman: O(n). Her iterasyonda işaretçilerden biri bir adım içeri gelir; toplam n-1 iterasyon.
• Bellek: O(1).

Kenar durumlar ve testler

main içinde derlenip çalıştırıldı; 3.000 rastgele girdide (0-19 uzunluk, yükseklikler 0-9) O(n²) brute force ile karşılaştırıldı.

Mülakatçı için

Kodu altı satır olan bu sorunun değeri doğruluk argümanında. Pek çok aday iki işaretçi çözümünü ezberden bilir; ama "neden kısa duvarı hareket ettiriyorsun, bu bir çözümü kaçırmaz mı?" sorusuna net bir eleme argümanıyla cevap veremez. Bu argümanı istemek, ezber ile anlayış arasındaki farkı ortaya çıkarır.

İpucu zamanlaması: Aday brute force'tan sonra 5 dakika ilerleyemezse "en geniş kaptan başlarsan, genişlik daralırken alanın artması için ne değişmeli?" diye sor. Çözümü bulduktan sonra mutlaka "neden doğru?" diye sor; "sezgisel olarak" cevabını kabul etme, kısa duvarın tüm kalan eşleşmelerinin neden daha kötü olduğunu iste.

Takip soruları:

1. Duvarların index'lerini de döndür; birden fazla optimum varsa en dar olanı? (Beklenen: eşit alanda genişliği karşılaştıran ek koşul.)
2. Aradaki çubuklar suyu engelleseydi ne değişirdi? (Beklenen: bu artık Trapping Rain Water; her sütunun sol/sağ maksimumu gerekir.)
3. Bu açgözlü stratejiyi bir arkadaşın "kısa duvarı değil, uzun duvarı içeri al" diye değiştirdi; hangi girdide yanlış sonuç verir? (Beklenen: küçük bir karşı örnek üretebilmek. [5, 5, 1]: doğru cevap 5 (ilk iki çubuk); "uzunu hareket ettir" stratejisi ilk adımda soldaki 5'i eler ve 2 bulur.)

Benzer problemler

• Trapping Rain Water (LeetCode 42): aynı iki işaretçi iskeleti, farklı değişmez (bu sette: trapping-rain-water).
• Two Sum II (LeetCode 167): sıralı dizide iki uçtan eleme.
• 3Sum (LeetCode 15) (bu sette: 3sum).
• Largest Rectangle in Histogram (LeetCode 84): "kısa çubuk sınırlar" fikrinin stack'li versiyonu.