LeetCode #1: Two Sum Problemi ve Klasik Hash Map Çözümü – Detaylı Bir Analiz
LeetCode’un ilk problemi olan “Two Sum”, algoritmik düşünmenin temel taşlarından biridir. Bu makalede, Mahdi Shamlou’nun da üzerinde durduğu gibi, problemin en verimli çözümü olan klasik hash map yaklaşımını detaylıca ele alacağız. Amacımız, çözümün mantığını, performansını ve önemini kapsamlı bir şekilde açıklamaktır.
LeetCode ve Algoritma Problemlerine Giriş
LeetCode Nedir ve Neden Önemlidir?
LeetCode, yazılım geliştiricilerin algoritmik problem çözme yeteneklerini geliştirmeleri, veri yapıları bilgilerini pekiştirmeleri ve teknik mülakatlara hazırlanmaları için tasarlanmış çevrimiçi bir platformdur. Binlerce farklı zorluk seviyesinde problem barındırır ve kullanıcıların farklı programlama dillerinde çözümlerini test etmelerine olanak tanır. LeetCode’da pratik yapmak, hem teorik bilgiyi pekiştirir hem de gerçek dünya mühendislik problemlerine yaklaşım yeteneğini artırır.
Algoritmik Düşünmenin Temelleri
Algoritmik düşünme, bir problemi adım adım çözme, verimli yöntemler geliştirme ve bu yöntemlerin karmaşıklığını analiz etme becerisidir. Bu, sadece kod yazmaktan öte, problemi farklı açılardan ele almayı, olası çözümleri değerlendirmeyi ve en uygun olanı seçmeyi içerir. Two Sum gibi temel problemler, bu düşünme biçimini geliştirmek için mükemmel başlangıç noktalarıdır.
İlk Adım: Two Sum Problemi
Two Sum, LeetCode’un en bilinen ve en sık karşılaşılan problemlerinden biridir. Genellikle mülakatlarda adayların temel algoritmik yeteneklerini ölçmek için kullanılır. Problem, basit bir tanıma sahip olsa da, farklı çözüm yaklaşımlarının performans üzerindeki etkisini net bir şekilde gösterir.
Two Sum Problemini Detaylı İnceleme
Problem Tanımı ve Kısıtlamalar
Two Sum problemi şu şekildedir: Size bir tam sayı dizisi (nums) ve bir hedef tam sayı (target) verilir. Dizideki hangi iki sayının toplamının hedefe eşit olduğunu bulmanız ve bu iki sayının dizideki indekslerini döndürmeniz istenir. Her girişin tam olarak bir çözümü olduğu varsayılır ve aynı elemanı iki kez kullanamazsınız.
numsdizisi 2 ile 104 eleman arasında olabilir.-109 <= nums[i] <= 109-109 <= target <= 109- Yalnızca bir geçerli çözüm vardır.
Örnek Senaryolar ve Beklenen Çıktılar
Problemi daha iyi anlamak için birkaç örnek inceleyelim:
# Örnek 1:
nums = [2, 7, 11, 15]
target = 9
# Beklenen Çıktı: [0, 1]
# Çünkü nums[0] + nums[1] == 2 + 7 == 9.
# Örnek 2:
nums = [3, 2, 4]
target = 6
# Beklenen Çıktı: [1, 2]
# Çünkü nums[1] + nums[2] == 2 + 4 == 6.
# Örnek 3:
nums = [3, 3]
target = 6
# Beklenen Çıktı: [0, 1]
# Çünkü nums[0] + nums[1] == 3 + 3 == 6.
Neden Bu Problem Temel Bir Köşe Taşıdır?
Two Sum, temel arama algoritmaları, veri yapıları (özellikle hash map'ler) ve zaman/alan karmaşıklığı analizi gibi kavramları tanıtmak için idealdir. Birçok karmaşık problemin temelinde yatan prensipleri barındırır ve farklı çözüm yaklaşımlarının performans üzerindeki dramatik etkisini açıkça gösterir.
Naif Yaklaşım: Brute Force ve Performans Dezavantajları
Brute Force Çözümünün Mantığı
Bir problemi çözmek için akla gelen ilk ve en basit yöntem genellikle "brute force" (kaba kuvvet) yaklaşımıdır. Two Sum için brute force, dizideki her sayıyı alıp, kalan tüm sayılarla toplayarak hedef toplamı bulmaya çalışmaktır. Bu, iç içe iki döngü kullanılarak gerçekleştirilir.
Zaman Karmaşıklığı Analizi (O(n^2))
Brute force çözümünde, dış döngü dizideki her eleman için bir kez çalışırken (n kez), iç döngü de her dış döngü iterasyonunda kalan elemanlar için (yaklaşık n kez) çalışır. Bu durumda toplam işlem sayısı yaklaşık n * n = n2 olur. Büyük O notasyonu ile bu, O(n2) olarak ifade edilir. Bu, dizi boyutu (n) arttıkça çözüm süresinin katlanarak artacağı anlamına gelir. Örneğin, 10.000 elemanlı bir dizi için yaklaşık 100 milyon işlem gerekebilir, bu da modern sistemlerde bile kabul edilemez derecede yavaş olabilir.
Alan Karmaşıklığı
Brute force yaklaşımında, ek bir veri yapısı kullanmadığımız için alan karmaşıklığı O(1) veya O(n) (eğer sonuç dizisi döndürme maliyetini sayarsak) düzeyindedir. Ancak, bu düşük alan maliyeti, yüksek zaman maliyeti nedeniyle genellikle tercih edilmez.
Hash Map (Karma Tablo) Veri Yapısının Gücü
Hash Map Nedir ve Nasıl Çalışır?
Hash map (karma tablo veya sözlük), anahtar-değer çiftlerini depolayan, verimli arama, ekleme ve silme işlemleri sunan bir veri yapısıdır. Bir anahtar verildiğinde, bu anahtarı bir "hash fonksiyonu" kullanarak bir dizin değerine dönüştürür ve değeri o dizinde saklar. Bu sayede, bir değeri anahtarı aracılığıyla neredeyse sabit zamanda (ortalama O(1)) bulmak mümkün olur.
Temel Operasyonlar: Ekleme, Arama, Silme
Hash map'lerin en büyük avantajı, temel operasyonlarının ortalama olarak O(1) zaman karmaşıklığına sahip olmasıdır:
- Ekleme (Insertion): Yeni bir anahtar-değer çiftini tabloya eklemek.
- Arama (Lookup): Bir anahtara karşılık gelen değeri bulmak.
- Silme (Deletion): Bir anahtar-değer çiftini tablodan kaldırmak.
Bu hız, özellikle büyük veri kümelerinde arama işlemlerinin kritik olduğu durumlarda hash map'leri vazgeçilmez kılar.
Two Sum İçin Hash Map'in Avantajları
Two Sum probleminde, bir sayıyı bulduktan sonra hedefi tamamlayacak diğer sayıyı hızlıca bulmamız gerekir. Hash map'ler, bu "tamamlayıcı" sayıyı dizinin geri kalanında tekrar aramak yerine, O(1) sürede mevcut olup olmadığını kontrol etme yeteneği sunar. Bu, iç içe döngü ihtiyacını ortadan kaldırarak zaman karmaşıklığını önemli ölçüde iyileştirir.
Klasik Hash Map Çözümünün Adım Adım Uygulanması
Algoritma Mantığı ve Akış Diyagramı
Hash map çözümü, dizide tek bir geçiş yaparak çalışır. Her elemanı işlerken, hedefi tamamlayacak "tamamlayıcı" sayının daha önce görülüp görülmediğini kontrol ederiz. Eğer görülmüşse, çözüm bulunmuştur. Görülmemişse, mevcut sayıyı ve indeksini hash map'e ekleriz.
Adım 1: Hash Map'i Başlatma
Boş bir hash map (Python'da sözlük, Java'da HashMap) oluşturulur. Bu map, anahtar olarak sayıları ve değer olarak da o sayının dizideki indeksini saklayacaktır.
Adım 2: Dizide Tek Geçiş
Verilen nums dizisi üzerinde baştan sona tek bir döngü başlatılır. Her iterasyonda, mevcut sayıya (num) ve onun indeksine (i) erişilir.
Adım 3: Tamamlayıcı Sayıyı Arama
Mevcut num için, hedefi tamamlayacak olan sayıyı (complement = target - num) hesaplarız. Daha sonra bu complement sayısının hash map'te zaten mevcut olup olmadığını kontrol ederiz.
Adım 4: Eşleşme Bulunduğunda
Eğer complement hash map'te bulunuyorsa, bu demektir ki daha önce bu sayıyı görmüş ve indeksini kaydetmişiz. Bu durumda, complement'in hash map'teki indeksi ile mevcut num'un indeksi (i) aranan cevaptır. Bu iki indeksi içeren bir liste döndürülür ve algoritma sona erer.
Adım 5: Eşleşme Bulunamazsa
Eğer complement hash map'te bulunamıyorsa, bu, mevcut num'un henüz bir eşleşme bulamadığı anlamına gelir. Bu durumda, num'u ve onun indeksini (i) hash map'e ekleriz. Böylece, dizinin ilerleyen elemanları için num bir complement olarak işlev görebilir.
Kod Örneği ve Detaylı Açıklamalar
Python ile Çözüm Kodu
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
# 1. Boş bir hash map (sözlük) oluştur
num_map = {} # {sayı: indeks}
# 2. Dizide tek geçiş yap
for i, num in enumerate(nums):
# 3. Tamamlayıcı sayıyı hesapla
complement = target - num
# 4. Tamamlayıcı sayı map'te var mı kontrol et
if complement in num_map:
# Varsa, çözüm bulundu.
# Tamamlayıcının indeksi ve mevcut sayının indeksi döndürülür.
return [num_map[complement], i]
# 5. Tamamlayıcı sayı bulunamazsa, mevcut sayıyı map'e ekle
num_map[num] = i
# Eğer döngü biter ve çözüm bulunamazsa (problem tanımına göre bu durum olmaz)
return []
Kodun Satır Satır Analizi
num_map = {}: Boş bir Python sözlüğü (hash map) başlatılır. Anahtarlar sayılar, değerler ise o sayıların dizideki indeksleri olacaktır.for i, num in enumerate(nums)::enumeratefonksiyonu, dizideki her elemanı hem indeksi (i) hem de değeri (num) ile birlikte döngüye sokar.complement = target - num: Mevcutnumiçin hedefi tamamlayacak sayıyı hesaplarız.if complement in num_map:: Hesaplanancomplementsayısının daha önce hash map'e eklenip eklenmediğini kontrol ederiz. Bu kontrol ortalama O(1) sürede gerçekleşir.return [num_map[complement], i]: Eğercomplementmap'te bulunursa, çözüm bulunmuştur.num_map[complement]bizecomplement'in indeksini verirken,ide mevcutnum'un indeksidir. Bu iki indeks döndürülür.num_map[num] = i: Eğercomplementbulunamazsa, mevcutnum'u ve onun indeksini hash map'e ekleriz. Bu, gelecekteki elemanlar içinnum'un bircomplementolarak bulunabilmesini sağlar.
Edge Case'ler ve Dikkat Edilmesi Gerekenler
Problem tanımına göre her zaman tam olarak bir çözüm olduğu varsayıldığı için, kodun döngüden çıkmadan bir çözüm bulması garanti edilir. Bu nedenle, döngüden sonra boş bir liste döndürme durumu pratikte gerçekleşmez, ancak iyi bir uygulama olarak eklenebilir. Aynı elemanı iki kez kullanamama kısıtlaması, hash map'e ekleme stratejimizle otomatik olarak ele alınır, çünkü mevcut elemanı ancak tamamlayıcısı bulunamazsa ekleriz. Bu, aynı elemanın kendisiyle eşleşmesini engeller.
Performans Analizi ve Optimizasyon
Zaman Karmaşıklığı (O(n))
Hash map çözümünde, dizide sadece tek bir geçiş yaparız. Her eleman için bir çıkarma işlemi (O(1)), hash map'te bir arama işlemi (ortalama O(1)) ve potansiyel olarak bir ekleme işlemi (ortalama O(1)) gerçekleştiririz. Bu nedenle, toplam zaman karmaşıklığı dizinin boyutuyla doğru orantılıdır, yani O(n) olur. Bu, brute force çözümünün O(n2) karmaşıklığına göre çok daha verimlidir.
Alan Karmaşıklığı (O(n))
Bu çözümde, en kötü durumda dizideki tüm elemanları hash map'e eklememiz gerekebilir (çözüm son elemanla bulunursa). Bu durumda hash map'in boyutu dizinin boyutuyla (n) orantılı olacaktır. Dolayısıyla, alan karmaşıklığı O(n) olarak kabul edilir. Bu, brute force çözümüne göre daha fazla bellek kullanımı anlamına gelir, ancak zaman performansındaki kazanç genellikle bu maliyeti haklı çıkarır.
Brute Force ile Karşılaştırma
Aşağıdaki tablo, iki çözüm yaklaşımının performansını özetlemektedir:
| Yaklaşım | Zaman Karmaşıklığı | Alan Karmaşıklığı |
|---|---|---|
| Brute Force | O(n2) | O(1) |
| Hash Map | O(n) | O(n) |
Görüldüğü üzere, hash map çözümü zaman karmaşıklığı açısından çok daha üstündür, özellikle büyük veri setlerinde bu fark hayati önem taşır.
Sonuç ve İleri Adımlar
Two Sum Çözümünün Önemi
Two Sum problemi, basit bir başlangıç noktası olmasına rağmen, algoritmik düşünme, veri yapıları seçimi ve performans analizi gibi temel yazılım mühendisliği kavramlarını pekiştirmek için mükemmel bir araçtır. Hash map çözümünün anlaşılması, daha karmaşık LeetCode problemlerini çözmek için sağlam bir temel oluşturur.
Öğrenilen Dersler
Bu problemden çıkarılacak en önemli ders, doğru veri yapısı seçiminin bir algoritmanın performansı üzerindeki dramatik etkisidir. Hash map'ler, hızlı arama gerektiren birçok senaryoda vazgeçilmez bir araçtır ve bu çözüm, onların gücünü açıkça ortaya koymaktadır.
Gelecek Problemlere Hazırlık
Two Sum'ı hash map ile çözmek, LeetCode yolculuğunuzda attığınız ilk önemli adımdır. Bu deneyim, dinamik programlama, grafik algoritmaları ve diğer gelişmiş veri yapıları gibi daha karmaşık konulara geçiş yaparken size rehberlik edecektir. Her zaman problemi anlamaya, farklı yaklaşımları düşünmeye ve performans analizini yapmaya odaklanın.
Sıkça Sorulan Sorular (SSS)
Two Sum için başka çözüm yolları var mı?
Evet, diziyi önce sıralayıp sonra iki işaretçi (two-pointer) tekniğiyle de çözülebilir. Ancak bu durumda, orijinal indeksleri korumak için ek adımlar gerekebilir ve sıralama işlemi O(n log n) zaman karmaşıklığına sahiptir. Hash map çözümü genellikle en optimal ve pratik yöntem olarak kabul edilir.
Hash Map yerine başka hangi veri yapıları kullanılabilir?
Eğer sayılar belirli bir aralıkta ve pozitif ise, bir boolean dizisi veya frekans dizisi (array) de kullanılabilir. Ancak bu, sayıların aralığı çok geniş olduğunda veya negatif sayılar içerdiğinde pratik değildir. Genel durumlar için hash map en esnek ve verimli çözümdür.
Boş dizi veya tek elemanlı dizi gibi özel durumlar nasıl ele alınır?
Problem kısıtlamalarına göre nums dizisi en az iki eleman içerecektir. Bu nedenle, boş veya tek elemanlı dizi gibi durumları özel olarak ele almaya gerek kalmaz. Ancak genel bir çözüm yazarken bu tür "edge case"leri düşünmek iyi bir alışkanlıktır.
Hash Map çözümünün dezavantajları nelerdir?
En büyük dezavantajı, ek bellek kullanımıdır (O(n) alan karmaşıklığı). Çok kısıtlı bellek ortamlarında bu bir sorun olabilir. Ayrıca, hash çarpışmaları (collision) nedeniyle en kötü durumda arama ve ekleme işlemleri O(n) olabilir, ancak bu durum modern hash map uygulamalarında nadiren görülür ve ortalama performans O(1)'dir.
Bu problemde neden iki geçiş yerine tek geçiş tercih edilir?
Tek geçişli çözüm, diziyi sadece bir kez tarayarak hem mevcut sayıyı işler hem de tamamlayıcısını arar. Bu, iki ayrı geçiş yapmaktan (bir geçişle tüm sayıları map'e ekleyip, ikinci geçişle tamamlayıcıları aramak) daha verimlidir çünkü her elemanı sadece bir kez ziyaret eder. İki geçiş de O(n) zaman karmaşıklığına sahip olsa da, tek geçiş pratik uygulamada daha az sabit faktörle daha hızlıdır.