sliding-window تکنیک کیا ہے؟

Question

Accepted Answer

**sliding-window** تکنیک ایک array یا string پر ایک متصل رینج (window) کو برقرار رکھتی ہے اور اسے شروع سے دوبارہ calculate کرنے کی بجائے slide کرتی ہے، بہت سے subarray/substring مسائل کو **O(n)** میں حل کرتی ہے۔

## اہم خیال

دائیں edge کو move کرکے window کو expand کریں؛ بائیں edge کو move کرکے اسے shrink کریں جب کوئی constraint متصادم ہو۔ دوبارہ scanning کی بجائے پچھلے computation کو دوبارہ استعمال کریں۔

## مثال: سائز k کی کسی بھی window کا زیادہ سے زیادہ رقم

```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) — ہر element ایک بار window میں داخل ہوتا ہے اور ایک بار نکلتا ہے۔
- **Space:** fixed windows کے لیے O(1)، جب contents کو track کریں تو O(k)۔

## کب استعمال کریں / خطرات

"longest/shortest/max subarray property X کے ساتھ" مسائل کے لیے استعمال کریں۔ **variable** windows کے لیے، constraint کو بحال کرنے کے لیے left pointer کو آگے بڑھائیں۔ boundary elements کو add/remove کرتے وقت off-by-one errors سے سावधان رہیں۔

## اہمیت

Sliding window بے کار کام کو ختم کرتا ہے، O(n·k) recomputation کو ایک pass میں تبدیل کرتا ہے۔

یہ substring اور subarray مسائل کے لیے go-to pattern ہے جو interviews میں مسلسل ظاہر ہوتے ہیں۔

یہ بصیرت — پچھلے نتیجے کو دوبارہ استعمال کریں بجائے دوبارہ calculate کرنے کے — streaming اور real-time ڈیٹا میں عام ہے۔