Jump Game

En doğrudan fikir, bunu canlandırmaktır. 0 indeksinde dur ve sıçrayışının ulaşmana izin verdiği her iniş noktasını teker teker dene. Her iniş noktasından aynı şeyi tekrar yap. Herhangi bir dal son indekse ulaşırsa yanıt true olur. Her dal çıkmaza girerse yanıt false olur.

İlk örnekte 0 indeksinde 2 bulunur; bu yüzden 1 ve 2 indekslerini denersin. 1 indeksinde 0 bulunur, yani burası bir çıkmazdır; bu yüzden geri dönüp 2 indeksini denersin. 2 indeksinde 3 bulunur ve 5 indeksine, yani son indekse ulaşır; arama true sonucuyla sona erer.

Arama doğrudur çünkü her rotaya bakar. Sorun da budur: Daha önce incelediği bir indeksi asla hatırlamaz, bu yüzden o indekse ulaşan her rota için aynı indeksi yeniden inceler. Yanıt false olduğunda her rotayı elemesi gerekir. [4, 3, 2, 1, 0, 5] dizisinde, 0'dan önceki her indeks 0'a ulaşabilir; bu da 0'a giden 8 farklı rota oluşturur. Bu tür 30 indeks olduğunda 500 milyondan fazla rota vardır ve en büyük testlerde 10.000 eleman bulunur. Böyle uzun bir rota, bazı dillerde çağrı yığınını da taşırır: Python varsayılan olarak 1.000 iç içe çağrıda durur.

Yukarıdaki arama, “j indeksi sona ulaşabilir mi?” sorusunu tekrar tekrar soruyor. j için yanıt hiç değişmez; bu yüzden bir kez hesaplayıp saklayın. Bir indeksten son indekse ulaşabiliyorsanız, bu indekse iyi deyin. Son indeks iyidir. i dışındaki herhangi bir indeks, i+1 ile i+nums[i] arasında ulaşabileceği en az bir indeks iyiyse iyidir.

Her indeks yalnızca sağındaki indekslere bağlıdır; bu nedenle good tablosunu sağdan sola doldurun. İlk örnekte 5. indeks iyidir. 4. indeksin değeri 0 olduğundan iyi değildir. 3. indeks yalnızca 4. indekse ulaşır: iyi değildir. 2. indeks 3., 4. ve 5. indekslere ulaşır; 5. indeks iyi olduğundan 2. indeks de iyidir. 1. indeksin değeri 0: iyi değildir. 0. indeks 1. ve 2. indekslere ulaşır; 2. indeks iyi olduğundan yanıt true olur.

Artık her indeks için karar yalnızca bir kez veriliyor, ancak bu kararı verirken hâlâ n hücreye kadar tarama yapılabilir. [9998, 9997, …, 1, 0, 7] dizisinde her indeks 0'a ulaşabilir, ancak onun ötesine geçemez; bu nedenle her biri kendi aralığının tamamını tarar ve iyi bir indeks bulamaz. 10.000 eleman için bu yaklaşık 5 × 10^7 kontrol demektir ve en büyük testler de bunun gibi oluşturulmuştur. İş miktarı uzunluğun karesiyle birlikte büyür, bu yüzden bu testlerde süre sınırını aşar.

Güzergâhlara değil, hangi indekslere ulaşabildiğine bak. i indeksinden i+1 ile i+nums[i] arasındaki herhangi bir indekse, arada boşluk olmadan ulaşabilirsin. Dolayısıyla i indeksine ulaşılabiliyorsa, i+nums[i] değerine kadar olan her indekse de ulaşılabilir. Yalnızca 0 indeksinden başlayıp bu aralıkları sürekli genişlet. Her yeni aralık, elindeki bloğun içinde başladığından, ulaşılabilir indeksler her zaman kesintisiz tek bir blok oluşturur: [0, farthest].

Bu yüzden tek bir sayı yeterlidir. i değerini soldan sağa ilerlet. i ≤ farthest olduğu sürece i indeksine ulaşılabilir; bu nedenle farthest değerini max(farthest, i+nums[i]) değerine genişlet. i herhangi bir noktada farthest değerini geçerse, ulaşılabilir hiçbir indeks i indeksine sıçrayamaz. Blok bu boşluğu aşarak genişleyemez; dolayısıyla bloğun sağındaki hiçbir indekse, son indeks de dahil, ulaşılamaz. İlerleme boşluk olmadan sona ulaşırsa son indekse ulaşılabilir.

İkinci örnekte, farthest önce 0, 0 indeksinden sonra 1, 1 indeksinden sonra da 4 olur. 2, 3 ve 4 indekslerinde 0 bulunur ve değer 4 olarak kalır. 5 indeksi 4'ü geçtiğinden cevap false olur. İlk örnekte, 2 indeksi farthest değerini 5'e çıkarır ve hiçbir indeks bu değeri geçmez; dolayısıyla cevap true olur.

Yalnızca en uzak erişim mesafesini tutmak neden güvenlidir? Hiçbir sıçrama için kesin karar vermezsin. Blok, herhangi bir güzergâhın ulaşabileceği tüm indeksleri içerir ve daha kısa mesafeli her iniş noktası da bu bloğun içinde kalır. Sağ uç dışındaki her şeyi göz ardı etmek hiçbir bilgi kaybına yol açmaz.