Pattern: Sliding Window

Il pattern Sliding Window prevede l'uso di due puntatori che delimitano una "finestra" mobile all'interno di un array o di una stringa. Muovendo la finestra possiamo mantenere informazioni aggiornate sul contenuto senza dover rielaborare l'intera sequenza ad ogni passo.

🚀 Quando usarlo

Usa lo Sliding Window quando:

• Vuoi trovare la somma o la media massima di un sottoarray di lunghezza fissa
• Cerchi la sottostringa più lunga che soddisfa una certa condizione
• Hai bisogno di contare occorrenze mentre avanzi con la finestra
• Vuoi ridurre soluzioni bruteforce O(n^2) a O(n)

✏️ Esempio classico: Massima somma in una finestra di k elementi

Esempio ispirato a Leetcode 209. Minimum Size Subarray Sum

def maxSumSubarray(arr, k):
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, len(arr)):
        window_sum += arr[i] - arr[i - k]
        max_sum = max(max_sum, window_sum)
    return max_sum

✅ Complessità:

• Tempo: O(n)
• Spazio: O(1)

🧩 Problemi comuni

Nome	Difficoltà	Pattern	Link
Longest Substring Without Repeating Characters	Medium	Variabile	Leetcode #3
Maximum Average Subarray I	Easy	Fissa	Leetcode #643
Minimum Size Subarray Sum	Medium	Variabile	Leetcode #209
Permutation in String	Medium	Variabile	Leetcode #567
Sliding Window Maximum	Hard	Fissa	Leetcode #239

💡 Consigli utili

• Aggiorna la finestra aggiungendo l'elemento a destra e rimuovendo quello a sinistra
• Gestisci con attenzione i casi in cui la dimensione della finestra cambia
• Ricorda che spesso è utile un dizionario o contatore per tenere traccia dei valori nella finestra

📚 Continua con

👉 Two Pointers →