Leetcode 42 Trapping Rain Water

Soru

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Örnek 1

Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Örnek 2

Input: height = [4,2,0,3,2,5]
Output: 9

Çözüm

• Verilen bir yükseklik haritası üzerinde bir yağmur sonrası kaç birim su birikebileceğini hesaplamanızı isteyen bir problem. Bu problem, belirli bir yapı üzerinde suyun nasıl toplanabileceğini modellemek için kullanılır ve bu yapı, bir dizi olarak verilen çeşitli yüksekliklerle temsil edilir.
• Bu problem, birden fazla yaklaşımla çözülebilir, ancak en yaygın yaklaşımlardan biri iki işaretçi tekniğidir. Alternatif olarak, dinamik programlama veya yığın (stack) kullanılarak da çözülebilir. İki işaretçi tekniğinde, iki işaretçi dizinin başlangıcı ve sonunda başlar ve ortada buluşana kadar hareket eder. Her bir işaretçi, o noktaya kadar gördüğü maksimum yüksekliği takip eder ve su toplama kapasitesi, her adımda bu maksimum değerler arasındaki farka dayanarak hesaplanır.
• Çalışma Mekanizması:
• İşaretçilerin İnitialize Edilmesi: left ve right işaretçileri dizinin başı ve sonunda başlar. left_max ve right_max ise o noktalardaki yüksekliklerle başlatılır.
• Su Toplama Kontrolü: İşaretçiler birbirine doğru hareket ederken, left_max ve right_max güncellenir. Eğer left_max veya right_max mevcut yükseklikten daha büyükse, fark kadar su birikintisi hesaplanır ve toplam suya eklenir.
• İşaretçilerin Hareketi: left veya right işaretçisi, karşı tarafın maksimum yüksekliğinden daha küçük olan tarafın işaretçisi bir adım hareket eder.
• Sonuç: İşaretçiler birbiriyle kesişene kadar bu işlem tekrarlanır ve hesaplanan toplam su miktarı döndürülür.

Code

class Solution:
    def trap(self, height):
        if not height:
            return 0
            
        left, right = 0, len(height) - 1
        left_max, right_max = height[left], height[right]
        water_trapped = 0
        
        while left < right:
            if height[left] < height[right]:
                if height[left] >= left_max:
                    left_max = height[left]
                else:
                    water_trapped += left_max - height[left]
                left += 1
            else:
                if height[right] >= right_max:
                    right_max = height[right]
                else:
                    water_trapped += right_max - height[right]
                right -= 1
                
        return water_trapped

        

Complexity

• Time complexity (Zaman Karmaşıklığı) : O(n), burada n dizinin uzunluğudur. Dizi tam olarak bir kez taranır.
• Space complexity (Alan Karmaşıklığı) : O(1), çünkü ekstra bir alan kullanılmaz ve yalnızca iki işaretçi ve birkaç yerel değişkenle çözüm sağlanır.