Window Variabel dengan Two Pointer

Beberapa masalah tidak menetapkan panjang jendela. Sebaliknya, jendela membesar dan mengecil agar suatu kondisi tetap terpenuhi, misalnya jumlah tetap di bawah batas tertentu.

Pertahankan dua indeks, kiri dan kanan, sebagai penanda tepi jendela. Penunjuk kanan memperluas jendela, sementara penunjuk kiri mengikutinya untuk mengecilkan jendela jika diperlukan.

Telusuri setiap elemen ke arah kanan dan sertakan elemen tersebut dalam jendela. Perbarui keadaan berjalan, misalnya dengan menambahkan nilai baru ke jumlah.

Selama jendela melanggar aturan, geser kiri ke arah kanan dan hapus elemen tersebut. Dengan begitu, kondisi dipulihkan tanpa perlu kembali ke belakang.

Setelah perulangan bagian dalam berakhir, jendela dari kiri hingga kanan menjadi valid. Panjangnya adalah kanan dikurangi kiri ditambah satu, sehingga siap digunakan.

Perbarui jawaban dengan jendela valid ini, yang sering kali merupakan jendela terpanjang yang ditemukan. Lakukan ini pada setiap iterasi agar tidak ada yang terlewat.

Setiap penunjuk hanya bergerak maju, tidak pernah mundur. Penunjuk kiri dan kanan secara keseluruhan maju paling banyak n langkah, sehingga seluruh penelusuran adalah O(n).

Ini bekerja ketika memperluas jendela hanya membuat kondisi menjadi lebih sulit untuk dipenuhi. Perilaku monoton inilah yang memungkinkan penunjuk kiri tidak pernah kembali.

Untuk mencari jendela valid terpendek, kecilkan jendela selama aturan masih terpenuhi dan catat hasilnya sebelum kondisi tidak lagi terpenuhi. Mekanisme penunjuknya tetap sama.

Jika pengecilan dapat mengosongkan jendela, cegah kondisi kiri melewati kanan. Pastikan juga bahwa jawaban benar-benar ditemukan sebelum mengembalikannya.

Gunakan jendela variabel ketika masalah meminta rentang berurutan terpanjang atau terpendek yang memenuhi suatu kondisi pada elemennya.

Perluas kanan untuk menyertakan elemen, kecilkan kiri saat aturan dilanggar, dan catat setiap jendela valid. Penunjuk yang hanya bergerak maju membuat kompleksitasnya O(n). ✅