Sliding-window technique क्या है?

Question

Accepted Answer

**Sliding-window** technique किसी array या string पर एक सतत range (window) बनाए रखती है और हर बार नए सिरे से गणना करने के बजाय उसे खिसकाती है, जिससे कई subarray/substring समस्याएँ **O(n)** में हल हो जाती हैं।

## मूल विचार

right edge को आगे बढ़ाकर window को बड़ा करें; जब कोई constraint टूटे, तो left edge को आगे बढ़ाकर window को छोटा करें। दोबारा scan करने के बजाय पिछली गणना का पुनः उपयोग करें।

## उदाहरण: size k की किसी भी window का अधिकतम sum

```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)
```

## Complexity

- **Time:** O(n) — प्रत्येक element एक बार window में प्रवेश करता है और एक बार बाहर निकलता है।
- **Space:** fixed windows के लिए O(1), और contents track करने पर O(k)।

## कब उपयोग करें / सावधानियाँ

"property X वाला सबसे लंबा/सबसे छोटा/अधिकतम subarray" जैसी समस्याओं के लिए उपयोग करें। **variable** windows के लिए, constraint को बहाल करने के लिए left pointer को आगे बढ़ाएँ। boundary elements जोड़ते/हटाते समय off-by-one errors से सावधान रहें।

## यह क्यों महत्वपूर्ण है

Sliding window अनावश्यक काम को समाप्त कर देता है, और O(n·k) पुनर्गणना को एक ही pass में बदल देता है।

यह substring और subarray समस्याओं के लिए सबसे पसंदीदा pattern है, जो interviews में लगातार आती रहती हैं।

यह अंतर्दृष्टि — पुनर्गणना के बजाय पिछले परिणाम का पुनः उपयोग करना — streaming और real-time data पर भी लागू होती है।