CP #35: Global and Local Inversions Problemi

 Problem surada.

Cozum

Cok enteresan bir problem ile karsi karsiyayiz. Elimizde 2 inversion tipi var: global ve local. 

Local inversion: yan yana olup da, kendisinden sonra gelenden buyuk olan bir eleman var ise bu local inversion oluyor. 

Global inversion: yanyana olmasina gerek olmadan, kendisinden sonra gelen elemanlar icinde, kendisinden buyuk bir eleman var ise, bu global inversion oluyor. 

Ben cok dusunmeden direk hesaplamaya giristim. Siz yapmayin diye burada tekrar yapalim ama sonra dusunme asamasina geri donecegiz. 

O zaman oncelikle local inversionlari hesaplayalim:

def isIdealPermutation(self, nums: List[int]) -> bool: 

    # local inversion sayisi kolay,

    # her bir pair'i kontrol ediyoruz

    loc = 0 

    for i in range(len(nums)-1):

        if nums[i+1] < nums[i]:

            loc += 1

    glob = 0

    # global icin ise 2 loop gerekli cunku her bir eleman icin

    # kendisinden sonra gelen ve kendisinden kucuk kac eleman

    # oldugunu bulmamiz gerek

    for i in range(len(nums)):

        for j in range(i+1, len(nums)):

            if nums[j] < nums[i]:

                glob +=1 

    

    # esit mi degil mi?

    return loc == glob

Aslinda dogru sonuc veriyor ama ikinci kisim O(n2) oldugu icin leetcode'da timeout oluyor. Bunun uzerine diger insanlarin cozumlerine baktim ve dusunme surecimin ciddi manada yanlis oldugunu gordum. 

Bir kere her local inversion aslinda global bir inversion. Cunku global inversion'da index sinirlamasi yok. Ornek olarak, yanyana durmasi gereken iki elemanin siralamasi yanlis olsa, yani 1 local inversion olsa (ornek: 0, 2, 1) bu durumda global inversion ve local inversion esit olacaktir. 

Peki hangi durumda global inversion ile local inversion esit olmaz? Yanyana olmayan iki eleman yer degistirirse esit olmayacaktir. Ornegin 2, 0, 1 icin 1 local inversion var iken (2 ve 0) buna mukabil 2 tane global inversion var (2 ve 0, 2 ve 1). 

Aslinda bu durumda yapmamiz gereken mevcut elemanin, olmasi gereken pozisyondan ne kadar shift ettigini bulmak. Eger bu shift 1 ise, demek ki inversion local. Bu durumda global vs local esitligi bozulmaz. Ama shift 1'den buyuk ise, bu durumda local olmayan bir global shift olmus demektir ve esitlik bozulur. 

Problemin basinda bu kadar seramoni ile bize bildirdigi bir gercek var. Verilen input arrayi aslinda 0'dan n-1'e kadar olan sayilarin permutasyonu. Yani bize verilen sayilar 0'dan n-1'e kadar olan sayilar. O zaman her bir eleman olmasi gereken konumdan ne kadar sapmis bunu direk o elemanin indisi ile arasindaki farka bakarak bulabiliriz. Ornek:

input : 0,  2,  1

index: 0,  1,  2

fark   : 0,  1,  1

Goruldugu gibi sadece local inversion var. (Fark == 1) Bu durumda local inversion == global inversion. True dondurmek gerekir.

input: 2,  1,  0

index: 0,  1,  2

fark:    2,  0,  2

Burada ise  local olmayan gloval inversion var. (Fark == 2) Burada esitlik bozulur ve False dondurmek gerekir. 

Implementasyon soyle olacak:

def isIdealPermutation(self, nums: List[int]) -> bool: 

    for i in range(len(nums)):

        if abs(nums[i] - i) > 1:

            return False

    return True

Analiz

Evet, kufur gibi bir problem. Ve dusunce tembeli olan ben, Umarim sizin icin faydali olmustur. Analizlik cok bir durum yok, one-pass bir loop icin O(n) time compl. ve ekstra hafiza harcamadigimiz icin de O(1) constant space bir algoritma elde ettik. 

Stay hungry, stay foolish, stay healthy :)