Two pointers və sliding window
Two pointers — iç-içə iki döngəni bir keçidə çevirən texnikadır. O(n²) → O(n). İki forması var.
Əks uclardan (opposite ends) — bir pointer əvvəldə, biri sonda, bir-birinə doğru hərəkət edirlər. Sıralanmış massivdə işləyir və gücü ondadır ki, hər addımda bütöv bir sıra variantı silinir.
Misal: sıralanmış massivdə cəmi target olan cüt tapmaq. a[lo] + a[hi] cəmini hesablayırsan:
- cəm hədəfdən kiçikdirsə — böyütmək lazımdır, deməli
lo++(çünkia[hi]onsuz da ən böyükdür;hi-ni azaltmaq cəmi daha da kiçildərdi) - cəm hədəfdən böyükdürsə — kiçiltmək lazımdır, deməli
hi--
Hər addımda bir pointer hərəkət edir, deməli cəmi n addım: O(n) vaxt, O(1) yaddaş. Diqqət: bu, brute force-un O(n²)-indən yaxşıdır, amma massiv sıralanmayıbsa sortun O(n log n) xərcini də hesaba almaq lazımdır — o halda hash map (O(n) vaxt, O(n) yaddaş) üstün ola bilər.
Eyni istiqamətdə (same direction) — hər iki pointer soldan sağa gedir, amma fərqli sürətlə. Klassik istifadə: massivi yerində filtrləmək. read pointeri bütün elementləri gəzir, write pointeri isə yalnız saxlanılacaqları yazır — nəticədə əlavə massiv olmadan O(1) yaddaşla filtr alınır. Sliding window da elə bu formanın xüsusi halıdır.
Sliding window — ardıcıl alt-massiv (və ya alt-sətir) haqqında suallara cavab verən pattern-dir. İki növü var.
Sabit ölçülü pəncərə — ölçü k verilib. Hiylə: hər dəfə pəncərəni sıfırdan hesablama. Bir addım sağa sürüşəndə yeni elementi əlavə et, köhnəni çıxar — bu, O(k) işi O(1)-ə endirir:
sum += a[right] - a[right - k]
Nəticə: O(n × k) əvəzinə O(n).
Dəyişən ölçülü pəncərə — ölçü verilmir, şərt verilir ("təkrarsız", "cəmi ən çox S", "ən çoxu 2 fərqli hərf"). Şablon həmişə eynidir və onu əzbər bilmək lazımdır:
right-i bir addım sağa apar və elementi pəncərəyə əlavə et- pəncərə şərti pozursa,
left-i sağa sürüşdürüb elementləri çıxar —whileilə,ifilə deyil - pəncərə yenidən düzgün olanda cavabı yenilə
Buna "pozulubsa daralt" (shrink while invalid) şablonu deyilir.
Niyə `O(n)`? İç-içə while görünsə də, hər element pəncərəyə bir dəfə girir və bir dəfə çıxır. left heç vaxt geri qayıtmır. Deməli daxili döngənin ümumi işi n-dən çox ola bilməz. Bu arqumenti interview-da ucadan söyləmək vacibdir — çox namizəd öz həllinin mürəkkəbliyini səhvən O(n²) adlandırır və özünü zəif göstərir.
| Məsələdəki siqnal | Variant | Açar detal |
|---|---|---|
| "Sıralanmış massivdə cəmi X olan cüt/üçlük" | Əks uclardan two pointers | Cəm kiçikdirsə `lo++`, böyükdürsə `hi--`; `O(n)`, `O(1)` yaddaş |
| "Palindromdurmu", "massivi tərsinə çevir" | Əks uclardan two pointers | Ortada görüşənə qədər müqayisə/dəyişmə |
| "Təkrarları sil", "sıfırları sona köçür" (yerində) | Eyni istiqamətdə (read/write) | `write` yalnız saxlanılan elementlərdə irəliləyir |
| "K ardıcıl elementin maksimum cəmi/ortalaması" | Sabit ölçülü pəncərə | `sum += a[right] - a[right - k]` |
| "Təkrarsız ən uzun alt-sətir" | Dəyişən pəncərə | `Set`/`Map` ilə pəncərənin içindəkiləri izlə; təkrar görsən daralt |
| "Cəmi ən azı S olan ən qısa alt-massiv" | Dəyişən pəncərə | Şərt ödənən kimi daralt və minimum uzunluğu yenilə |
| Alt-massiv **ardıcıl deyil** (istənilən elementlər) | Sliding window UYĞUN DEYİL | Hash map, sort, DP və ya backtracking düşün |
Interview məsləhəti: sliding window-un ən böyük tələsi — pattern-i ardıcıl olmayan məsələyə tətbiq etməkdir. Pəncərə yalnız contiguous (ardıcıl) alt-massiv/alt-sətir üçün işləyir. "İstənilən elementlərdən ibarət ən böyük cəm" məsələsində pəncərə səhv cavab verir. Ona görə kodu yazmazdan əvvəl bir cümlə de: "Burada alt-massiv ardıcıl olmalıdır — təsdiq edirsiniz? Onda sliding window uyğundur." İkinci məsləhət: mürəkkəbliyi izah edərkən "hər element pəncərəyə bir dəfə girir, bir dəfə çıxır, ona görə iç-içə while-a baxmayaraq O(n)" cümləsini mütləq söylə.