X'inhu t-teknika tal-sliding-window?

Question

Accepted Answer

It-teknika **sliding-window** tippreserva firxa kontinwa (window) fuq array jew string u taħrikha minflok ma terħoq mill-ġdid, u tsolvi ħafna problemi ta' subarray/substring f' **O(n)**.

## L-idea

Ikkompli l-window billi ċċirkla l-ġenb tal-lemin; uqbud it-tama tiegħu billi ċċirkla l-ġenb tax-xellug meta jkun hemm violazzjoni ta' constraint. Uża mill-ġdid il-komputazzjoni ta' qabel minflok ma tiskanna mill-ġdid.

## Eżempju: massimu ta' somma ta' kwalunkwe window ta' daqs k

```python
def max_window_sum(arr, k):
    window = sum(arr[:k])       # sum of first window
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]  # add new, drop old
        best = max(best, window)
    return best

max_window_sum([2, 1, 5, 1, 3, 2], 3)  # -> 9 (5+1+3)
```

## Kumplessità

- **Ħin:** O(n) — kull element jidħol u joħroġ mill-window darba waħda.
- **Spazju:** O(1) għal windows fissa, O(k) meta tkun qed tarak il-kontenut.

## Meta tuża / pitfalls

Uża għal problemi "longest/shortest/max subarray bi proprjetà X". Għal windows **varjabbli**, advance il-pointer tax-xellug biex tirrestawra l-constraint. Ħarsa lill-erruri off-by-one meta tżid/tneħħi elementi tal-boundary.

## Għaliex dan importanti

Sliding window jt-tella l-xogħol redundanti, u jibdel il-komputazzjoni O(n·k) f'pass waħda.

Hija l-pattern ta' go-to għal problemi ta' substring u subarray li jidhru b'mod kostanti f'intervisti.

L-insight — uża mill-ġdid ir-riżultat ta' qabel minflok ma terħoq mill-ġdid — jiġeneralizza għal streaming u data real-time.