En uzun ardışık sayı dizisi

Problem

Sırasız bir tamsayı dizisi veriliyor. Dizideki değerlerden, birer birer artan ardışık tamsayılar oluşturan en uzun kümeyi bul ve uzunluğunu döndür. Elemanların dizide yan yana olması gerekmiyor; önemli olan değerlerin x, x+1, x+2, ... şeklinde kesintisiz bir zincir kurması. Tekrar eden değerler zinciri uzatmaz. Beklenen çözüm O(n) zamanda çalışmalı.

Girdi:  [10, 4, 20, 1, 3, 2, 11]
Çıktı:  4          (1, 2, 3, 4)

Girdi:  [1, 2, 2, 3]
Çıktı:  3          (tekrar eden 2 bir kez sayılır)

Netleştirme soruları

• Boş dizi gelebilir mi? (Cevap 0.)
• Tekrar eden değerler var mı, nasıl sayılmalı?
• Değer aralığı ne? Negatifler ve Integer.MIN_VALUE/MAX_VALUE gelebilir mi? (x + 1 taşabilir.)
• O(n) şartı kesin mi, yoksa O(n log n) kabul mü? (Sıralamalı çözüm çok daha kısa.)
• Sadece uzunluk mu, dizinin kendisi de mi isteniyor?

İpuçları

Yaklaşım

Brute force: Her x için x+1, x+2, ... dizide var mı diye lineer arama yap. O(n) arama × O(n) zincir uzunluğu × n başlangıç = O(n³).

Sıralama: Diziyi sırala, tekrarları atlayarak ardışık artışları say. O(n log n) zaman; mülakatta bunu söylemek iyi bir başlangıç noktasıdır ama soru O(n) istiyor.

Optimal, HashSet ve "zincir başı" kuralı: Tüm değerleri HashSet'e koy; artık "x var mı?" ortalama O(1). Her değerden yukarı doğru sayarsan [1, 2, ..., n] gibi bir girdide 1'den n, 2'den n-1 adım... toplam O(n²) olur. Çözüm: sadece zincirin başı olan değerlerden say. Bir değer ancak x - 1 kümede yoksa zincir başıdır. Böylece her zincir yalnızca bir kez, başından sonuna kadar yürünür.

Neden O(n): while döngüsünün toplam adım sayısı, tüm zincir uzunluklarının toplamıdır ve zincirler ayrık olduğu için bu toplam en fazla farklı değer sayısıdır. Dış döngü de n kez döner. Toplam O(n).

Bir incelik: dış döngüyü orijinal dizi yerine set üzerinde döndürmek gerekir. [1, 1, 1, ..., 1, 2, 3, ..., k] gibi tekrarlı bir girdide dizi üzerinde dönersen aynı zincir başı (1) defalarca yürünür ve süre O(n × k)'ya çıkar.

Java çözümü

import java.util.HashSet;
import java.util.Set;

public final class LongestConsecutiveSequence {

    public int longestConsecutive(int[] nums) {
        Set<Integer> values = new HashSet<>();
        for (int num : nums) {
            values.add(num);
        }
        int longest = 0;
        for (int start : values) {                                 // tekrarları atlamak için set üzerinde dön
            if (start != Integer.MIN_VALUE && values.contains(start - 1)) {
                continue;                                          // dizinin başı değil; başı sayacak
            }
            int current = start;
            while (current != Integer.MAX_VALUE && values.contains(current + 1)) {
                current++;                                         // MAX + 1 taşıp MIN olmasın
            }
            longest = Math.max(longest, current - start + 1);
        }
        return longest;
    }
}

start - 1 ve current + 1 ifadeleri int sınırında taşar: Integer.MAX_VALUE + 1 sessizce Integer.MIN_VALUE olur ve kümede MIN_VALUE varsa zincir "dolanarak" yanlış uzar. LeetCode sınırlarında (±10⁹) bu olmaz ama testte bu durum bilerek denendi ve iki koruma eklendi.

Karmaşıklık

• Zaman: O(n) ortalama. Set'e ekleme n kez O(1); dış döngü farklı değer sayısı kadar; iç while döngüsü toplamda en fazla farklı değer sayısı kadar.
• Bellek: O(n), set için.
• Pratik not: HashSet<Integer> boxing ve hash maliyetiyle n ≤ 10⁵ için sıralama çözümünden yavaş olabilir. Asimptotik ile gerçek performansın farklı olabileceğini söylemek olgun bir cevaptır.

Kenar durumlar ve testler

main içindeki testlerle derlenip çalıştırıldı; ayrıca 2.000 rastgele girdide (tekrarlı, negatifli) sıralama tabanlı referans çözümle karşılaştırıldı.

Mülakatçı için

Bu sorunun ayırt edici anı, adayın set'li ama her elemandan sayan O(n²) çözümü yazıp onu O(n) sanmasıdır. Çoğu aday set fikrine hızlı ulaşır; zincir başı kuralını görmeyenler ya da gördüğü halde O(n) olduğunu açıklayamayanlar burada ayrışır. Amortize analiz yapabilmek (iç döngü toplamda n adım) güçlü bir sinyaldir.

İpucu zamanlaması: Aday sıralamalı çözümü önerirse kabul et ve "O(n) yapabilir misin?" diye sor. Set'li O(n²) çözümü yazarsa [1..n] girdisi için kaç adım attığını sor; kendi bulsun. Zincir başı kuralını bulduktan sonra "neden O(n)?" sorusunun cevabını mutlaka iste.

Takip soruları:

1. Sayılar bir stream olarak geliyor ve her yeni sayıdan sonra güncel en uzun zinciri raporlaman gerekiyor. (Beklenen: Union-Find ile x ve x±1'i birleştirme, bileşen boyutlarını tutma; ya da HashMap<sınır, uzunluk> ile zincir uçlarını güncelleme.)
2. Zincirin kendisini de döndürmen gerekirse? (Beklenen: en iyi başlangıç değerini ve uzunluğu tut, sonra üret.)
3. n = 10⁵ için hangisi gerçekte daha hızlı olur, sıralama mı set mi? Neden? (Beklenen: primitive dizide Arrays.sort cache dostu ve boxing yok; ölçmeden karar verilmez.)

Benzer problemler

• Binary Tree Longest Consecutive Sequence (LeetCode 298).
• Number of Islands (LeetCode 200) ve Union-Find problemleri: aynı "bileşen" fikri.
• Two Sum (LeetCode 1): HashSet/HashMap ile O(1) üyelik (bu sette: two-sum).
• Data Stream as Disjoint Intervals (LeetCode 352): stream versiyonuna yakın.