CP #33 : Partition Array Into Disjoint Intervals Problemi

 Problem surada.

Cozum

Naive implementasyon ile baslar isek, verilen arrayi sol taraf 1 elemanli olacak sekilde ayirmaya baslayabiliriz. Her adimda, sol arrayi bir eleman daha fazla genisletmeye calisiriz. Buradaki kriter su, sol arraydaki en buyuk eleman dahi, sag taraftaki elemanlarint tamamindan daha kucuk olacak. Bu kriteri sagladigimiz anda sol taraf eleman sayisini dondurecegiz. 

def partitionDisjoint(self, A: List[int]) -> int:

    # verilen left ve right arraylari icin bunun valid bir partition olup olmadigini 

    # kontrol eden fonksiyonumuz

    # max hesaplayip, sagdaki tum elemanlarla karsilastirdigimizdan

    # toplamda O(n) bir maliyete sahip

    def is_valid_partition(left, right):

        max_left = max(left)  # O(n)

        for n in right:

            if n > max_left:

                return False

        return True

    # sol taraf tek elemanli olacak sekilde baslayabiliriz

    for i in range(1, len(A)):

        left = A[:i]    # array kopyalama yaptigimizdan O(n)

        right = A[i:]  # bu da O(n)

        

        if is_valid_partition(left, right):

            return i

Analiz

Leetcode'da testlerden geciyor tamam, ama diger python gonderilerinin sadece %5'inden daha hizli. Bakacak olursak, for ile yaptigimiz dongude 1'den verilen arrayin sonuna kadar gitme ihtimalimiz var, O(n). Dongunun icerisinde de toplamda O(n) kompleksiteye sahibiz. Yani toplamda O(n2) gib bir cozumumuz var. 

Bunu nasil iyilestirebiliriz? 

1. is_valid_partition fonksiyonu icerisinde max_left'i bulduktan sonra bunu right array'deki tum elemenalarla kasilastirip, hepsinden kucuk oldugunudan emin oluyoruz. Hepsi ile karsilastirmak yerine, sagdaki en kucuk elemanla soldaki en buyuk elemani karsilastirsak yine ayni sonucu elde etmis oluruz aslinda. Yani yapmamiz gereken her adinda, max_left ve min_right gibi iki degeri karsilastirmak. 

2. her adimda tekrar tekrar max_left hesapliyoruz. Bunu tek bir seferde yapabiliriz. Hatta simdi bir de min_right degeri gerekiyor. Bu iki deger de verilen bir i indexinden once gelen degerlerin maximumu ve bu indexten sonra gelen degerlerin minumumunu ifade ediyor. Oyleyse, bu hesaplamalari onceden yapabiliriz. Yani one pass ile tum i degerleri icin max_left ve baska bir one pass ile de tum i degerleri icin min_right hesaplanabilir. Daha sonra bunlari partitionunun valid olup olmamasi kontrolunde kullanirsak, oradaki karsilastirmayi O(1)'e indirmis oluruz. 

def partitionDisjoint(self, A: List[int]) -> int:

    # tum i indexleri icin kendinden once gelen max

    # degeri bir arrayda tutalim

    max_lefts = [None] * len(A)

    cur_max_left = A[0]

    for i in range(len(A)):

        cur_max_left = max(cur_max_left, A[i])

        max_lefts[i] = cur_max_left

    # ayni sekilde her bir i indexi icin, kendisinin saginda kalan 

    # min elemani tutan bir array olusturalim

    # bunu yapmak icin arrayi sondan basa dogru traverse ediyoruz

    min_rights = [None] * len(A)

    cur_min_right = A[-1]

    for i in range(len(A)-1, -1, -1):

        cur_min_right = min(cur_min_right, A[i])

        min_rights[i] = cur_min_right

    # simdi artik partitionlamaya baslayabiliriz

    for i in range(1, len(A)):

        if max_lefts[i-1] <= min_rights[i]:

            return i

Tekrar bakacak olursak, max_lefts ve min_rights hesaplamasi icin verilen arrayi birer kere donduk. Toplamda O(n). Ve dogru partitionun bulunmasi icin de tekrar verilen arrayi bir kere donduk. Sonucta, toplamda cozumumuz O(n) kompleksiteye sahip. Zaten leetcode'da 8260 ms'den 200 ms'ye indi. 

Hafiza kullaniminda ise iki ekstra array tuttuk. Bu durumda 2*n ekstra yere ihtiyacimiz olacak demektir ki bu da O(n) space complexity'e takabul ediyor demektir. 

Bir diger problemde gorusmek uzere.

Stay hungry, stay foolish, stay healthy :)