Leetcode 73 Set Matrix Zeroes

Given an m x n integer matrix matrix, if an element is 0, set its entire row and column to 0’s, and return the matrix.

You must do it in place.

Input: matrix = [[1,1,1],[1,0,1],[1,1,1]]
Output: [[1,0,1],[0,0,0],[1,0,1]]

Input: matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
Output: [[0,0,0,0],[0,4,5,0],[0,3,1,0]]

• Soruda bir matrix veriliyor.Bu matrixin bazı değerleri sıfır.Bizden istenen sıfır değerlerinin olduğu tüm sütun ve satırları sıfır yapıp yeni bir matrix oluşturmak.
• Basit bir şekilde düşünürsek elimizdeki matrixin aynısından bir kopya matrix oluştururuz.Daha sonra ilk matrixi gezerek sıfır gördüğümüz zaman kopya matrixte ilgili sütunu ve satırı sıfır yaparız.Bu space complexity olarak o(m.n) maliyet oluşturur.
• Bu çözümü biraz daha geliştirirsek.Yedek olarak sadece bir satır ve bir sütun oluşturalım.Elimizdeki matrixte sıfır gördüğümüz zaman aynı hizadaki sütun ve satırdaki alanları sıfır yapalım.Tüm matrixte dolaşmayı tamamlayınca kopya sütun ve satırdaki sıfır olan alanları kontrol edelim ve orjinal matrixte bunlara karşılık gelen yerleri sıfır yapalım.Bu işleminde space complexity değeri o(m+n) olur.
• Bizden istenen space complexity değeri o(1) olması.Bunu nasıl sağlarız?
• Önceki örnekte kopya sütun ve satır oluşturduk.Peki bu kopyaları oluşturmak yerine orjinal matrixteki en soldaki sütun ve en üstteki satırı kullansaydık.Yani sol üstten dolaşmaya başladık.0 değilse geç.Sıfır ise en üstteki satır ve en soldaki sütunu sıfır yap.Bu şekilde tüm matrixi dolaşıp sıfır gördüğümüzde en üstteki satır ve en soldaki sütunu güncelleriz.Sonra da bu alanları kontrol ederek gerekli yerleri sıfır yaparız.
• Yalnız burada bir sıkıntı var.En üst satırın en solundaki alan ile en sol sütunun en üstündenki alan çakışmakta.Birbirlerini ezmekteler.Bunun için sadece 1 değerlik bir değişken atarız ve en sol sütunun en üstteki değerini burada saklarız.Bu da space complexity olarak o(1) olur.

    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.   
        """
        
        ROWS, COLS = len(matrix), len(matrix[0])
        rowZero = False
        
        #determine which rows/cols need to be zero
        
        for r in range(ROWS): #satır
            for c in range(COLS): #sütun
                if matrix[r][c] == 0:   # 0 değerini bulduk 
                    matrix[0][c] = 0    #en üst satırda aynı hizadaki değeri 0 yap
                    if r > 0:           #eğer en üstteki satır {matrix[0][0]} değil ise en soldaki  
                        matrix[r][0]=0  #sütundaki değeri 0 yap
                    else:             #eğer en üstteki değeri {matrix[0][0]} 0 yapmamız gerekiyorsa bir 
                        rowZero =True #değişkene ata çünkü az önce atadığımız değeri ezmek istemiyoruz.

        for r in range(1,ROWS): # şimdi en soldaki sütun ve en üstteki satı hariç
            for c in range(1,COLS):#kalan alanları kontrol edip sıfırlıyoruz.
                if matrix[0][c] == 0 or matrix[r][0] == 0:
                    matrix[r][c] = 0

        if matrix[0][0]==0:# en üst en soldaki değer sıfır ise demekki en üst satır sıfır olacak.
            for r in range(ROWS):
                matrix[r][0] = 0

        if rowZero: #yedek oluşturduğumuz değeri kontrol ediyoruz bu bizim sütunumuzun en üst değeri idi
            for c in range(COLS): #sıfır ise en soldaki sütun sıfır olacak
                matrix[0][c] = 0