સ્લાઈડિંગ-વિન્ડો તકનીક શું છે?

Question

Accepted Answer

**સ્લાઈડિંગ-વિન્ડો** તકનીક એક કન્ટીજુઅસ રેન્જ (વિન્ડો) ને એરે અથવા સ્ટ્રિંગ પર જાળવી રાખે છે અને તેને સ્લાઈડ કરે છે બદલે કે શરૂ થી ફરીથી કમ્પ્યુટ કરવાથી, ઘણી subarray/substring સમસ્યાઓ ને **O(n)** માં હલ કરે છે.

## આ વિચાર

રાઇટ એજ ને આગળ ખસેડીને વિન્ડો વધારો; જ્યારે કોઈ constraint ની ક્ષતિ થાય ત્યારે લેફ્ટ એજ ને આગળ ખસેડીને તેને સંકુચિત કરો. ફરીથી સ્કેન કરવાથી બદલે પાછલી computation ને ફરીથી ઉપયોગ કરો.

## ઉદાહરણ: સાઈজ 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)
```

## જટિલતા

- **સમય:** O(n) — દરેક એલીમેન્ટ વિન્ડોમાં એક વખત પ્રવેશ કરે છે અને એક વખત બહાર નીકળે છે.
- **જગ્યા:** નિશ્ચિત વિન્ડો માટે O(1), જ્યારે contents ને ટ્રેક કરીને O(k).

## ક્યારે ઉપયોગ કરવો / ખતરા

"longest/shortest/max subarray with property X" સમસ્યાઓ માટે ઉપયોગ કરો. **વેરીએબલ** વિન્ડો માટે, constraint ને પુનઃસ્થાપિત કરવા માટે લેફ્ટ પોઈન્ટર ને આગળ ખસેડો. boundary એલીમેન્ટ્સ ને add/remove કરીને off-by-one ભૂલો પર નજર રાખો.

## તે શા માટે મહત્વપૂર્ણ છે

સ્લાઈડિંગ વિન્ડો redundant work ને દૂર કરે છે, O(n·k) recomputation ને એક પાસમાં પરિણત કરે છે.

તે substring અને subarray સમસ્યાઓ માટે go-to pattern છે જે interviews માં સતત દેખાય છે.

آ insight — પાછલા પરિણામ ને ફરીથી ઉપયોગ કરો બદલે કે recompute કરવાથી — streaming અને real-time ડેટા માટે સામાન્યીકૃત થાય છે.