LeetCode 2975: Tarladan Çitleri Kaldırarak Maksimum Kare Alanı Bulma Rehberi

LeetCode 2975: Tarladan Çitleri Kaldırarak Maksimum Kare Alanı Bulma Rehberi

Merhaba kodlama meraklıları! Bugün, LeetCode’un 2975 numaralı problemi olan “Tarladan Çitleri Kaldırarak Maksimum Kare Alanı” problemini adım adım inceleyeceğiz. Bu problem, başlangıç seviyesindeki programcılar için hem geometrik düşünme hem de etkili veri yapıları kullanma becerilerini geliştirmek adına harika bir fırsat sunuyor. Karmaşık görünen bu problemi basit adımlara bölerek, nasıl çözüme ulaşacağımızı C++, Python ve JavaScript dillerinde kod örnekleriyle birlikte keşfedeceğiz.

Problemi Anlamak: Tarlalar, Çitler ve Kareler

Bu problemde, belirli sayıda satır (n) ve sütun (m) içeren bir tarlamız var. Bu tarlanın içinde yatay ve dikey çitler bulunuyor. Bize verilen hFences dizisi yatay çitlerin konumlarını, vFences dizisi ise dikey çitlerin konumlarını belirtiyor. Amacımız, bu çitlerden istediğimiz kadarını kaldırarak, elde edebileceğimiz en büyük kare şeklindeki alanın büyüklüğünü bulmak. Unutmayın, kare bir alanın kenar uzunlukları birbirine eşit olmalıdır.

Tarlanın Yapısı ve Çitlerin Konumu

Problem tanımına göre, tarlamızın n+1 yatay çizgisi ve m+1 dikey çizgisi vardır. Yatay çizgiler y = 0, 1, ..., n+1 konumlarında, dikey çizgiler ise x = 0, 1, ..., m+1 konumlarında bulunur. hFences dizisindeki her r_i değeri, y = r_i konumunda bir yatay çit olduğunu, vFences dizisindeki her c_j değeri ise x = c_j konumunda bir dikey çit olduğunu gösterir. Bu çizgiler, tarlayı bir ızgara yapısına böler.

Hedefimiz: Maksimum Kare Alanı

Bir kare alan oluşturmak için, iki yatay çizgi ve iki dikey çizgi seçmemiz gerekir. Bu çizgiler arasındaki mesafeler eşit olmalıdır. Örneğin, y1 ve y2 yatay çizgileri ile x1 ve x2 dikey çizgilerini seçtiysek, |y2 - y1| ve |x2 - x1| değerleri birbirine eşit olmalı ve bu değer kare alanımızın bir kenar uzunluğunu temsil etmelidir. Bizim görevimiz, tüm olası kombinasyonlar arasından en büyük kenar uzunluğuna sahip kareyi bulmak ve alanını döndürmektir.

Çözüme Giden İlk Adımlar: Sınırları ve Çitleri Düzenleme

Problemi çözmeye başlamadan önce, elimizdeki veriyi doğru bir şekilde hazırlamamız gerekiyor. Bu, problemin kilit noktalarından biridir.

Gizli Çitler: Sınırları Dahil Etmek

Problem tanımında belirtildiği gibi, tarlanın kendisi y = 0 ve y = n+1 konumlarında yatay sınırlara, x = 0 ve x = m+1 konumlarında dikey sınırlara sahiptir. Bu sınırlar, tıpkı diğer çitler gibi davranır ve kare alan oluşturmak için kullanılabilir. Dolayısıyla, hFences dizisine 0 ve n+1 değerlerini, vFences dizisine ise 0 ve m+1 değerlerini eklememiz şarttır. Bu “gizli” çitler, olası tüm kenar uzunluklarını hesaplarken göz önünde bulundurulmalıdır.

Çit Konumlarını Düzenleme: Sıralama ve Tekilleştirme

Sınırları ekledikten sonra, hem yatay hem de dikey çit konumlarını içeren dizilerimiz olacaktır. Bu dizileri işlemeye başlamadan önce iki önemli adım atmalıyız:

1. Sıralama: Çit konumlarını küçükten büyüğe doğru sıralamak, aralarındaki mesafeleri daha kolay ve sistematik bir şekilde hesaplamamızı sağlar.
2. Tekilleştirme: Aynı konumda birden fazla çit olması durumu, problemde bir farklılık yaratmaz. Bu yüzden, her çit konumunun sadece bir kez listede yer almasını sağlamak için dizileri tekilleştirmeliyiz.

Bu adımlar, hem doğru sonuçlar elde etmemizi hem de gereksiz hesaplamalardan kaçınarak performansımızı artırmamızı sağlar.

Olası Mesafeleri Bulma: Yatay ve Dikey Genişlikler

Çit konumlarını düzenledikten sonra, bir sonraki adım, bu çitler arasında oluşabilecek tüm olası yatay ve dikey mesafeleri (yani karelerin potansiyel kenar uzunluklarını) bulmaktır.

Yatay Mesafelerin Hesaplanması

Düzenlenmiş hFences dizisini ele alalım. Bu dizideki her iki çit konumu (f1 ve f2) arasında bir mesafe (f2 - f1) hesaplayabiliriz. Bu mesafeler, yatay bir kenar uzunluğu olmaya adaydır. Tüm olası yatay mesafeleri bir küme (set) veri yapısında saklamak, daha sonra dikey mesafelerle karşılaştırmamızı kolaylaştıracaktır.

Dikey Mesafelerin Hesaplanması

Aynı mantıkla, düzenlenmiş vFences dizisindeki her iki çit konumu (f1 ve f2) arasındaki mesafeyi (f2 - f1) hesaplarız. Bu mesafeler de dikey bir kenar uzunluğu olmaya adaydır. Bu dikey mesafeleri de ayrı bir küme veri yapısında saklarız.

Veri Yapısı Seçimi: Setler (Kümeler)

Neden küme (set) kullanıyoruz? Çünkü kümeler, elemanları otomatik olarak tekilleştirir ve eleman arama işlemlerini çok hızlı bir şekilde gerçekleştirir. Bu, özellikle ortak mesafeleri bulma aşamasında bize büyük avantaj sağlar.

Ortak Mesafeleri Belirleme ve Maksimum Kare Alanı

Artık elimizde tüm olası yatay ve dikey kenar uzunluklarını içeren iki ayrı küme var. Bir kare oluşturmak için hem yatay hem de dikey kenar uzunluğunun aynı olması gerekir. Bu yüzden, iki kümenin kesişimini bulmalıyız.

Ortak Mesafelerin Kesişimi

Yatay mesafeler kümesi (h_distances) ve dikey mesafeler kümesi (v_distances) arasındaki kesişimi bulduğumuzda, elimizde hem yatayda hem de dikeyde oluşturulabilecek tüm olası kare kenar uzunlukları kalır. Bu ortak mesafelerden en büyüğünü bulmak, bizim için kritik öneme sahiptir.

Maksimum Ortak Mesafeyi Bulma

Kesişim kümesindeki tüm elemanlar arasından en büyük değeri seçmeliyiz. Bu değer, oluşturabileceğimiz en büyük karenin bir kenar uzunluğunu temsil eder. Eğer kesişim kümesi boşsa (yani hiçbir ortak mesafe yoksa), bu durumda kare alan oluşturmak mümkün değildir ve problem gereği 0 döndürülmelidir.

Alan Hesaplaması ve Modulo İşlemi

En büyük ortak kenar uzunluğunu (side) bulduktan sonra, maksimum kare alanı side * side olarak hesaplanır. Ancak, problem genellikle büyük sayılarla çalışırken sonuçların belirli bir modüloya göre döndürülmesini ister. Bu problemde de 10^9 + 7 modülosu kullanmamız isteniyor. Bu, sonucun belirli bir aralıkta kalmasını sağlar ve taşma problemlerini önler.

Algoritma ve Kod Örnekleri

Şimdiye kadar bahsettiğimiz adımları bir algoritma olarak özetleyelim ve ardından C++, Python ve JavaScript dillerinde örnek uygulamalarını görelim.

1. hFences ve vFences dizilerine tarlanın sınırlarını (0 ve n+1/m+1) ekleyin.
2. Her iki diziyi sıralayın ve tekilleştirin.
3. Her iki dizideki tüm çit çiftleri arasındaki mesafeleri hesaplayarak ayrı ayrı kümelere (h_distances, v_distances) ekleyin.
4. h_distances ve v_distances kümelerinin kesişimini bulun.
5. Kesişim kümesindeki en büyük değeri (max_side) bulun. Eğer küme boşsa, 0 döndürün.
6. Sonucu (max_side * max_side) % (10^9 + 7) olarak hesaplayıp döndürün.

C++ Çözümü

#include 
#include 
#include 

class Solution {
public:
    int maximizeSquareArea(int n, int m, std::vector& hFences, std::vector& vFences) {
        long long MOD = 1e9 + 7;

        // 1. Sınırları ekle
        hFences.push_back(0);
        hFences.push_back(n + 1);
        vFences.push_back(0);
        vFences.push_back(m + 1);

        // 2. Sırala ve tekilleştir
        std::sort(hFences.begin(), hFences.end());
        hFences.erase(std::unique(hFences.begin(), hFences.end()), hFences.end());

        std::sort(vFences.begin(), vFences.end());
        vFences.erase(std::unique(vFences.begin(), vFences.end()), vFences.end());

        // 3. Olası yatay ve dikey mesafeleri hesapla
        std::set h_distances;
        for (size_t i = 0; i < hFences.size(); ++i) {
            for (size_t j = i + 1; j < hFences.size(); ++j) {
                h_distances.insert(hFences[j] - hFences[i]);
            }
        }

        std::set v_distances;
        for (size_t i = 0; i < vFences.size(); ++i) {
            for (size_t j = i + 1; j < vFences.size(); ++j) {
                v_distances.insert(vFences[j] - vFences[i]);
            }
        }

        // 4. Ortak mesafeleri bul ve en büyüğünü seç
        long long max_side = 0;
        for (int dist : h_distances) {
            if (v_distances.count(dist)) { // dist hem yatay hem dikeyde var mı?
                max_side = std::max(max_side, (long long)dist);
            }
        }

        // 5. Sonucu hesapla
        if (max_side == 0) {
            return -1; // Hiçbir kare oluşturulamazsa -1 döndürülüyor (LeetCode problemine göre)
        }
        return (max_side * max_side) % MOD;
    }
};

C++ çözümünde, std::vector ve std::set gibi STL kapsayıcıları kullanıyoruz. std::sort ve std::unique fonksiyonları dizileri düzenlemek için idealdir. Modulo işlemi için long long kullanmak, olası taşmaları engeller.

Python Çözümü

class Solution:
    def maximizeSquareArea(self, n: int, m: int, hFences: list[int], vFences: list[int]) -> int:
        MOD = 10**9 + 7

        # 1. Sınırları ekle
        hFences.append(0)
        hFences.append(n + 1)
        vFences.append(0)
        vFences.append(m + 1)

        # 2. Sırala ve tekilleştir
        hFences = sorted(list(set(hFences)))
        vFences = sorted(list(set(vFences)))

        # 3. Olası yatay ve dikey mesafeleri hesapla
        h_distances = set()
        for i in range(len(hFences)):
            for j in range(i + 1, len(hFences)):
                h_distances.add(hFences[j] - hFences[i])

        v_distances = set()
        for i in range(len(vFences)):
            for j in range(i + 1, len(vFences)):
                v_distances.add(vFences[j] - vFences[i])

        # 4. Ortak mesafeleri bul ve en büyüğünü seç
        max_side = 0
        for dist in h_distances:
            if dist in v_distances:
                max_side = max(max_side, dist)
        
        # 5. Sonucu hesapla
        if max_side == 0:
            return -1 # Hiçbir kare oluşturulamazsa -1 döndürülüyor (LeetCode problemine göre)
        
        return (max_side * max_side) % MOD

Python'da set() veri yapısı tekilleştirme ve hızlı arama için doğal bir seçimdir. sorted(list(set(...))) ifadesi hem tekilleştirme hem de sıralama işlemini pratik bir şekilde yapar.

JavaScript Çözümü

/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} hFences
 * @param {number[]} vFences
 * @return {number}
 */
var maximizeSquareArea = function(n, m, hFences, vFences) {
    const MOD = 10**9 + 7;

    // 1. Sınırları ekle
    hFences.push(0, n + 1);
    vFences.push(0, m + 1);

    // 2. Sırala ve tekilleştir
    hFences = [...new Set(hFences)].sort((a, b) => a - b);
    vFences = [...new Set(vFences)].sort((a, b) => a - b);

    // 3. Olası yatay ve dikey mesafeleri hesapla
    const hDistances = new Set();
    for (let i = 0; i < hFences.length; i++) {
        for (let j = i + 1; j < hFences.length; j++) {
            hDistances.add(hFences[j] - hFences[i]);
        }
    }

    const vDistances = new Set();
    for (let i = 0; i < vFences.length; i++) {
        for (let j = i + 1; j < vFences.length; j++) {
            vDistances.add(vFences[j] - vFences[i]);
        }
    }

    // 4. Ortak mesafeleri bul ve en büyüğünü seç
    let maxSide = 0;
    for (const dist of hDistances) {
        if (vDistances.has(dist)) {
            maxSide = Math.max(maxSide, dist);
        }
    }

    // 5. Sonucu hesapla
    if (maxSide === 0) {
        return -1; // Hiçbir kare oluşturulamazsa -1 döndürülüyor (LeetCode problemine göre)
    }

    // JavaScript'te büyük sayılar için BigInt kullanmak gerekebilir,
    // ancak 10^9 + 7 modülü sayesinde sonuç normal number aralığında kalır.
    return (maxSide * maxSide) % MOD;
};

JavaScript'te Set objesi ve spread operatörü (...) ile tekilleştirme ve sıralama işlemleri kolayca yapılabilir. Math.max fonksiyonu en büyük değeri bulmak için kullanılır.

Karmaşıklık Analizi

Herhangi bir algoritmayı değerlendirirken, zaman ve uzay karmaşıklığına bakmak önemlidir.

Zaman Karmaşıklığı

• Sınırları Ekleme: O(1)
• Sıralama ve Tekilleştirme: Eğer N_h ve N_v sırasıyla yatay ve dikey çitlerin son sayıları ise, sıralama O(N_h log N_h + N_v log N_v) zaman alır. Tekilleştirme bu karmaşıklığı değiştirmez. N_h en fazla n + 2 ve N_v en fazla m + 2 olabilir.
• Mesafeleri Hesaplama: Her iki dizi için de iç içe döngüler kullandığımızdan, bu O(N_h^2 + N_v^2) zaman alır. Her bir mesafe kümesine ekleme işlemi ortalama O(1)'dir.
• Ortak Mesafeleri Bulma: h_distances kümesi üzerindeki her eleman için v_distances kümesinde arama yaparız. Bu, O(N_h * log(N_v)) veya ortalama O(N_h) zaman alır (küme aramasının ortalama O(1) olduğu varsayılırsa).

Genel olarak, baskın faktör mesafeleri hesaplama adımıdır: O(N_h^2 + N_v^2).

Uzay Karmaşıklığı

• Çit Dizileri: O(N_h + N_v)
• Mesafe Kümeleri: En kötü durumda, h_distances kümesi O(N_h^2) ve v_distances kümesi O(N_v^2) eleman içerebilir.

Genel olarak, baskın faktör mesafe kümeleridir: O(N_h^2 + N_v^2).

Bu problemde n ve m değerleri 100'e kadar çıkabildiğinden, N_h ve N_v de yaklaşık 100 civarında olur. Dolayısıyla 100^2 = 10000 işlemi kabul edilebilir bir karmaşıklıktadır.

Sonuç

LeetCode 2975 problemi, basit bir geometrik problemi etkili veri yapıları ve algoritmik düşünceyle nasıl çözebileceğimizi gösteren güzel bir örnektir. Sınır koşullarını doğru bir şekilde ele almak, veriyi düzenlemek (sıralama ve tekilleştirme) ve uygun veri yapılarını (kümeler) kullanmak, bu tür problemlerin çözümünde anahtardır. Maksimum kare alanı bulma yaklaşımı, diğer benzer "maksimum dikdörtgen/kare" problemlerine de uyarlanabilir. Umarım bu rehber, problemi anlamanıza ve kendi çözümlerinizi geliştirmenize yardımcı olmuştur!

Sıkça Sorulan Sorular (SSS)

Neden 0 ve n+1/m+1 sınırlarını ekliyoruz?

Tarlanın kendisi, dış kenarlarında da hayali çitlere sahiptir. Bu sınırlar, iç çitler gibi bir kare alanın kenarı olarak kullanılabilir. Örneğin, y=0 ve y=5 arasında bir yatay kenar oluşturmak isteyebilirsiniz, ancak hFences dizisinde 0 veya 5 olmasa bile bu kenarlar mevcuttur. Bu sınırları dahil etmek, tüm olası kenar uzunluklarını göz önünde bulundurmamızı sağlar.

Neden set (küme) kullanıyoruz? Listelerle olmaz mıydı?

Listelerle de çözülebilirdi ancak setler, iki temel avantaj sunar:

1. Tekilleştirme: Setler, aynı elemanı birden fazla kez içermez. Bu, çit konumlarını veya mesafeleri otomatik olarak tekilleştirmemizi sağlar.
2. Hızlı Arama: Bir elemanın sette olup olmadığını kontrol etmek (.has() veya .count()) ortalama O(1) zaman alır. Listelerde bu işlem O(N) zaman alırdı, bu da özellikle ortak mesafeleri bulma adımında performansı önemli ölçüde etkilerdi.

Modulo işlemi (10^9 + 7) neden gerekli?

Modulo işlemi, özellikle büyük sayılarla yapılan hesaplamalarda sonucun belirli bir aralıkta kalmasını sağlamak için kullanılır. Problemde n ve m değerleri 100'e kadar çıkabilir. Bu durumda max_side 100'den büyük olabilir (örneğin n+1). max_side * max_side işlemi çok büyük bir sayıya dönüşebilir ve standart integer tiplerinin kapasitesini aşarak taşma (overflow) hatalarına yol açabilir. Modulo işlemi, sonucun her zaman 0 ile 10^9 + 6 arasında kalmasını garanti eder.

Bu problem türü başka nerede karşıma çıkabilir?

Bu tür problemler, genellikle geometrik algoritmalar, ızgara tabanlı problemler ve kombinatorik optimizasyon problemlerinde karşımıza çıkar. Örneğin, "maksimum dikdörtgen alan", "en yakın nokta çifti" gibi problemler benzer mantık ve veri yapıları kullanılarak çözülebilir. Temel mantık, tüm olası alt problemleri veya alt yapıları sistematik olarak incelemek ve en iyi çözümü bulmaktır.