LeetCode 41 Takıntım: İlk Eksik Pozitif Bulmacanın Derinlemesine İncelenmesi

LeetCode'un "Eksik Olmayan En Küçük Pozitif Sayı" problemi (41 numaralı), son kodlama takıntım haline geldi. Aldatıcı derecede basit bir bulmaca olan bu problem, düşüncelerimi ele geçirdi ve mümkün olan en verimli TypeScript çözümünü oluşturmak için inceliklerini keşfetmeye yöneltti. Bu yazı sadece kodlama mülakatlarında başarılı olmakla ilgili değil (her ne kadar bu hoş bir avantaj olsa da). Problem çözmenin saf zevki, optimizasyon heyecanı ve verimli kodun zarif güzelliği hakkında. Ve biraz matematik delisi olduğum için, çözümün matematiksel temellerine bile ineceğiz.

Problem: Kurt Postunda Kuzu Postu

Problem, sıralanmamış bir tamsayı dizisi sunuyor. Göreviniz: Eksik olan en küçük pozitif tamsayıyı bulun. Düzgün görünüyor mu? Tekrar düşünün. $O(n)$ zaman ve $O(1)$ alan karmaşıklığı kısıtlamaları, bu görünüşte basit görevi zorlu bir algoritmik bulmacaya dönüştürüyor.

Başlangıçtaki Çabalar: Brüt Kuvvet Tuzağı

İlk denemelerime sıralama ( $O(n)$ zaman kısıtlamasını ihlal eden) ve karma kümeleri ( $O(1)$ alan sınırını aşan) dahil ettim. Açıkçası, daha sofistike bir yaklaşım gerekiyordu.

Eureka Anı: Yerinde Dönüşüm

Ana fikir, giriş dizisinin kendisini bir karma tablo olarak kullanabileceğimi fark etmekti. Elemanları yeniden düzenleyerek, sayı $x$'i $x - 1$ indeksine yerleştirebilirdim ($1 \le x \le n$, burada $n$ dizi uzunluğudur). Bu yerinde dönüşüm, verimli bir çözüme giden yolu açıyor.

Kod Evrimi: Bir TypeScript Destanı

İşte, ayrıntılı açıklamalar ve matematiksel bilgilerle kodumun evriminin kroniği:

Sürüm 1: Basit Yaklaşım (Fazla Sayıda Değiştirmeyle)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length

  // Her sayıyı, [1, n] aralığında ise doğru konumuna yerleştirin
  for (let i = 0; i < n; i++) {
    while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] !== nums[i]) {
      const correctIndex = nums[i] - 1
      ;[nums[i], nums[correctIndex]] = [nums[correctIndex], nums[i]] // Değiştirme
    }
  }

  // Eksik olan ilk pozitif sayıyı bulun
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  // Tüm sayılar doğru konumlarında ise, eksik sayı n + 1'dir
  return n + 1
}

Bu sürüm, işlevsel olmasına rağmen, gereksiz değiştirmelerden muzdariptir. En kötü durum senaryosundaki değiştirme sayısı $O(n^2)$'ye yaklaşırken, ortalama durum $O(n)$'ye daha yakındır.

Açıklama:

1. Diziyi yeniden düzenleyin: Her nums[i] sayısı, [1, n] aralığında ise ve henüz doğru konumda değilse, "doğru" indeksine (nums[i] - 1) yerleştirilir.

2. Eksik pozitif sayıyı belirleyin: Yeniden düzenlemeden sonra, nums[i] !== i + 1 olan ilk i indeksi, i + 1'in eksik pozitif tamsayı olduğunu gösterir.

3. Gerekirse n + 1'i döndürün: 1'den n'ye kadar tüm sayılar doğru konumlarda ise, eksik sayı n + 1'dir.

Ana Noktalar:

• Yerinde yeniden düzenleme: Ekstra alan kullanmaktan kaçınmak için dizinin kendisini değiştiriyoruz.
• Verimlilik: Hem yeniden düzenleme hem de son tarama $O(n)$ zaman alır ve optimum performansı sağlar.

Sürüm 2: Performans Artışı (Gereksiz Değiştirmeleri Ortadan Kaldırma)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  // Sayıları mümkünse doğru konumlarına yeniden düzenleyin
  while (idx < n) {
    const correctIdx = nums[idx] - 1
    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      // Geçici değişken kullanmadan değiştirme
      ;[nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]
    } else {
      idx++
    }
  }

  // Eksik olan ilk pozitif sayıyı belirleyin
  for (let i = 0; i < n; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return n + 1
}

Açıklama:

1. Verimli Yeniden Düzenleme:

   • while döngüsü, sayı geçerli [1, n] aralığında ise ve henüz doğru konumda değilse, elemanları doğrudan doğru konumlarına (nums[idx] - 1) değiştirir.
   • if koşulu, geçersiz veya zaten doğru olan sayıların gereksiz değiştirmeler olmadan atlanmasını sağlar.

2. Doğrudan İndeks Kontrolü:

   • Yeniden düzenleme aşamasında, nums[idx]'in aralığı ve değeri kontrol edilerek geçersiz değiştirmeler ve gereksiz işlemler önlenir.

3. Bellek Etkin Değiştirme:

   • Yapı çözümlemenin kullanımı ([nums[idx], nums[correctIdx]] = [nums[correctIdx], nums[idx]]), geçici bir değişkene duyulan ihtiyacı ortadan kaldırır ve bellek kullanımını en aza indirir.

4. Minimum Döngüler:

   • Algoritma yalnızca iki doğrusal geçiş kullanır:
     • Dizinin yerinde yeniden düzenlenmesi için bir tane.
     • Eksik olan ilk pozitifi bulmak için bir tane.

Karmaşıklık Analizi:

• Zaman Karmaşıklığı:
  • while döngüsü ve for döngüsü her ikisi de $O(n)$ zaman alır, toplam zaman karmaşıklığını $O(n)$ yapar.
• Alan Karmaşıklığı:
  • Algoritma, yardımcı veri yapıları kullanmadan yerinde çalışır, bu nedenle alan karmaşıklığı $O(1)$'dir.

Neden Bu Kod Optimumdur:

• Performans: Akıcı while döngüsü, minimum gereksiz işlemi sağlar ve hızı en üst düzeye çıkarır.
• Bellek Verimliliği: Yerinde değiştirmenin ve ekstra değişkenlerden kaçınmanın kullanımı, mümkün olan en düşük bellek ayak izini sağlar.

Sürüm 3: Bellek İçin Optimize Edilmiş (Minimum Alan Kullanımı)

function firstMissingPositive(nums: number[]): number {
  const n = nums.length
  let idx = 0

  while (idx < n) {
    const correctIdx = nums[idx] - 1

    if (correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx]) {
      nums[idx] = nums[correctIdx]
      nums[correctIdx] = correctIdx + 1
    } else {
      idx++
    }
  }

  for (let idx = 0; idx < n; idx++) {
    if (nums[idx] !== idx + 1) {
      return idx + 1
    }
  }

  return nums.length + 1
}

Ana Bellek Optimizasyonları:

1. Minimum Geçici Değişkenlerle Yerinde Güncellemeler:

   • Değiştirme için bir temp değişkeni kullanmak yerine, bu kod diziyi nums[idx] = nums[correctIdx]; nums[correctIdx] = correctIdx + 1 ile doğrudan değiştirir.
   • Bu, geçici bir değişkene duyulan ihtiyacı ortadan kaldırır ve bellek yükünü sabit bir miktar azaltır.

2. Döngüde Daha Az Geçici Değer:

   • Kod, correctIdx'i doğrudan döngüde hesaplar ve çekirdek mantığın dışında ek ara değişkenlerin depolanmasına gerek kalmaz.
   • Daha az değişken ataması, yineleme başına biraz daha düşük bellek kullanımı anlamına gelir.

3. Yeniden Düzenleme İçin Tek Geçiş:

   • while döngüsünde iç içe koşullar kullanan ilk koddaki aksine, bu uygulama değiştirmeleri daha akıcı bir şekilde tamamlar veya indeksi ilerletir; çalışma zamanı yığın derinliğini ve bellek kullanımını azaltır.
   • Döngü yapısı (while tek bir artış veya yeniden düzenleme ile), daha az yardımcı değere ihtiyaç duyarak daha doğrudandır.

4. Gereksiz Kontroller Yok:

   • correctIdx >= 0 && correctIdx < n && nums[idx] !== nums[correctIdx] kontrolleri özlüdür ve geçici olarak yığın veya CPU önbelleği belleği kullanabilecek gereksiz işlemleri önler.
   • Bu, sonuca katkıda bulunmayacak işlemler için ek kaynak tahsis edilmesine gerek kalmamasını sağlar.

Bunun Bellekte Neden Fark Yaratması:

• Azaltılmış Geçici Depolama: Bir temp değişkenine güvenmeyerek ve ara hesaplamaları en aza indirgeyerek, bellek ayak izi küçülür.
• Akıcı Çalıştırma: Daha az adım ve daha basit mantık, işlem başına daha düşük bellek kullanımıyla sonuçlanır.
• Geliştirilmiş Önbellek Kullanımı: Algoritmanın doğrusal, tahmin edilebilir erişim modeli, CPU önbellek performansını iyileştirir ve dolaylı olarak bellek yükünü azaltır.

Bu çözümün yerinde doğrudan güncellemelere, minimum değişken kullanımına ve verimli bellek erişim modellerine odaklanması, bellek verimliliği açısından en iyisini yapar. Tasarruflar sabit ($O(1)$) olsa da, özellikle büyük veri kümeleri için LeetCode gibi rekabetçi platformlarda kaydolmak için yeterince önemlidir.

Sürüm 4: Optimize Edilmiş Başyapıt (Yerinde Değiştirme, Geçici Yok)

function firstMissingPositive(nums: number[]): number {
  for (let i = 0; i < nums.length; i++) {
    while (nums[i] !== i + 1) {
      if (nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]) {
        break
      }

      const temp = nums[i]
      nums[i] = nums[temp - 1]
      nums[temp - 1] = temp
    }
  }

  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== i + 1) {
      return i + 1
    }
  }

  return nums.length + 1
}

Bu son sürüm, geçici bir değişken olmadan zarif yerinde değiştirme yoluyla hem optimum performansı hem de minimum bellek kullanımını elde eder. Zaman karmaşıklığı artık kesin olarak $O(n)$'dir ve alan karmaşıklığı $O(1)$'dir ve tüm gereksinimleri karşılar. Matematiksel olarak, elemanları "doğru" konumlarına yerleştirmek için dizi içinde bir tür döngüsel permütasyon gerçekleştiriyoruz.

Bir kontrol ekleyerek (nums[i] === nums[nums[i] - 1]), gereksiz değiştirmeleri önlüyoruz. Bu, performansı önemli ölçüde iyileştirir ve zaman karmaşıklığını istenen $O(n)$'ye yaklaştırır.

Uygulamada Ana Farklılıklar:

1. Gereksiz Değiştirmelerden Kaçınma:

   • Sağlanan kod, değiştirmeyi gerçekleştirmeden önce nums[i] === nums[nums[i] - 1] olup olmadığını açıkça kontrol eder. Sayı zaten doğru konumdaysa veya çoğaltmalar varsa gereksiz değiştirmeler önlenir.
   • İlk uygulamada, bu kontrol atlanır ve gereksiz olsa bile gereksiz değiştirmelere yol açabilir. Her ek değiştirme, özellikle büyük diziler için ek yük ekler.

2. Doğrudan İndeks Karşılaştırması:

   • Sağlanan kod, bir sayının doğru bir şekilde yerleştirilene veya geçersiz bir koşul karşılanana kadar tekrar tekrar doğru konumuna değiştirilmesini sağlamak için while (nums[i] !== i + 1) kullanır. Bu, gereksiz döngü yinelemelerini ortadan kaldırır.
   • İlk kod, sayıyı döngü koşulu içindeki amaçlanan indeksine açıkça karşılaştırmaz. Sayıların minimum hareket gerektirmesi durumunda daha fazla işlem gerçekleştirebilir.

3. Optimize Edilmiş Koşullu Kontroller:

   • Koşullar tek bir if bloğunda birleştirilerek (örneğin, nums[i] <= 0 || nums[i] > nums.length || nums[i] === nums[nums[i] - 1]), gereksiz kontrollerden veya hesaplamalardan kaynaklanan ek yükten kaçınılır.

LeetCode'da Bunun Önemi:

• Çalışma Zamanı Tutarlılığı:

  • LeetCode'un çalışma zamanı ölçümleri, gereksiz değiştirmeler veya ekstra karşılaştırmalar gibi gereksiz işlemlere duyarlı olabilir.
  • Sağlanan kod bu işlemleri en aza indirir ve ortalama olarak daha hızlı çalışma zamanına yol açar.

• Önbellek Verimliliği:

  • Daha az değiştirme ve daha basit döngü mantığı, daha iyi CPU önbellek kullanımıyla sonuçlanır. Modern işlemciler, sağlanan kodun sergilediği tahmin edilebilir ve akıcı erişim modellerinden faydalanır.

Sonuçlar

İşte tablo formatında sunulan özet:

Bu tablo, uzlaşmaları ve son çözümün optimallığını vurgular.

Özet, en iyi performans ve bellek için denemenin gerçekten en optimize olduğunu göstermektedir:

• 1 ms çalışma zamanı: Performans açısından en hızlı sonucu eşleştiriyor.
• 58.9 MB bellek kullanımı: "En iyi bellek" klonundan biraz daha yüksek ancak diğer denemelerden daha düşük.

Analiz:

1. Çalışma Zamanı:

   • 1 ms çalışma zamanı, optimize edilmiş yaklaşımın gereksiz kontrolleri ve gereksiz değiştirmeleri ortadan kaldırdığını göstermektedir.
   • $O(n)$'nin tutarlı zaman karmaşıklığı, daha büyük veri kümeleri için ölçeklenebilirliği sağlar.

2. Bellek:

   • 58.9 MB, hızlı yürütmeye rağmen bellek ayak izinin düşük olduğunu göstermektedir. "En iyi bellek" (58.5 MB)'den bu hafif artış, yapı çözümlemelerindeki veya motor özgü optimizasyonlardaki farklılıklardan kaynaklanıyor olabilir.

3. Uzlaşmalar:

   • "En iyi bellek" çözümü, daha düşük bellek kullanımı için çalışma zamanından biraz ödün veriyor.
   • "En iyi performans" çözümü daha çok hıza odaklanıyor ancak biraz daha fazla bellek kullanıyor.

Sonuç:

Optimize edilmiş çözüm iyi bir denge sağlıyor:

• 1 ms çalışma zamanı, en iyi performans gösteren kod kadar hızlıdır.
• 58.9 MB bellek kullanımı, en iyi bellek sonucuna çok yakındır, ihmal edilebilir bir ek yük ile.

Hem performansın hem de belleğin kritik olduğu senaryolar için iyi bir seçimdir.

Matematiksel Temeller: Döngüsel Permütasyonlar ve Güvercin Yuvası İlkesi

Ana fikir, döngüsel permütasyonlar kavramı etrafında dönüyor. Her $x$ sayısının $x - 1$ indeksine yerleştirildiği bir döngü oluşturmayı hedefliyoruz. while döngüsü bu döngülerde etkili bir şekilde dolaşarak her elemanın belirlenmiş yerine ulaşmasını sağlar.

Güvercin Yuvası İlkesi burada ince bir rol oynar. $n$ olası konum (0 ila $n-1$ indeksleri) olduğundan ve $[1, n+1]$ aralığında eksik bir pozitif tamsayı arıyoruz, 1'den $n$'ye kadar tüm sayılar mevcutsa, eksik sayı $n + 1$ olmalıdır.

Takıntı Devam Ediyor...

LeetCode 41'e olan hayranlığım devam ediyor. Sürekli olarak daha fazla optimizasyon ve daha derin içgörüler arıyorum. Bu arayışa katılın! Düşüncelerinizi, kendi çözümlerinizi paylaşın ve matematiğin ve algoritmaların zarif kesişimini birlikte keşfedelim.