Interviewer पूछेगा:
10 लाख numbers का array है. लगातार 1000 का सबसे बड़ा sum चाहिए. कितनी additions लगेंगी?
बाहर गया घटाओ. अंदर आया जोड़ो. Let’s make it click.
Match के runs हैं [4, 9, 2, 12, 7, 1, 10]. Best 3 consecutive overs चाहिए. पहले 4 + 9 + 2 = 15. अब अगले तीन: 9 + 2 + 12. भाई, 9 और 2 दोबारा क्यों जोड़ रहे हो? दोनों पहले से sum में हैं!
बाहर गया घटाओ. अंदर आया जोड़ो.
पहला window sum 15. Move right: बाहर 4 गया, अंदर 12 आया. नया sum = 15 − 4 + 12 = 23. अगला = 23 − 9 + 7 = 21. फिर 21 − 2 + 1 = 20. Last 20 − 12 + 10 = 18. Best 23, यानी overs 2–4.
Window size हमेशा k है. इस invariant की वजह से entering index right और exiting index right-k होगा. Answer सिर्फ current sum नहीं; best so far अलग track करना.
10 लाख × 1000 का हिसाब
n = 10,00,000 और k = 1000. Windows n-k+1 = 9,99,001. हर window को zero से sum करो तो करीब 100 करोड़ element-additions. Strictly k-1 additions प्रति window गिनो तो 9,98,001,999 additions. दोनों का growth O(n × k).
Sliding window में पहली window के 999 additions, फिर हर shift पर 1 subtraction + 1 addition. Exact: 999 + 2 × 9,99,000 = 19,98,999 arithmetic operations. करीब 20 लाख. Time O(n), extra space O(1).
Negative values और off-by-one traps
Best को 0 से initialize मत करना अगर values negative हो सकती हैं. [-5, -2, -4], k=2 में best -6 है, 0 नहीं. Best first window sum से शुरू करो.
k = 1, k = n, empty input और invalid k को सोचो. Sample implementation invalid k पर clear exception देता है. Interview problem constraints valid k guarantee करें तो भी invariant explain करना useful है.
Average आसान; maximum के लिए deque
LC 643 में k fixed है, इसलिए largest average वही window देती है जिसका sum सबसे बड़ा है. Answer best_sum / k. हर window पर divide करने की जरूरत नहीं.
LC 239 में हर window का largest element चाहिए. Outgoing number maximum हो सकता है; सिर्फ subtract/add से नया maximum नहीं मिलेगा. Monotonic deque रखो: indices decreasing values के order में, expired indices front से हटाओ. हर index एक बार push/pop, total O(n), space O(k).
“Consecutive k elements के sums में adjacent windows k−1 elements share करती हैं. First window O(k) में बनाऊँगा, फिर outgoing element subtract और incoming add करूँगा. n−k shifts constant work हैं. Total O(n) time, O(1) space; best first sum से initialize करूँगा ताकि negative input भी सही रहे.”
Read it once. फिर अपने words में बोल के देखो.Pattern पहचानो.
| Problem में ये दिखे | तब ये use करो | यहाँ नहीं |
|---|---|---|
| Consecutive k, max sum / average | Fixed-size sum window | Noncontiguous subsequences |
| Max element in every window | Monotonic deque | Subtract/add alone cannot recover a maximum |
| Longest / shortest valid interval | Variable-size window | A fixed k that the problem never gives |
अब code लिखते हैं.
Maximum Average Subarray I · LC 643
Cricket example: max sum 23, max average 23/3. O(n) time, O(1) space.
def find_max_average(nums, k):
if not 1 <= k <= len(nums):
raise ValueError("k must be between 1 and len(nums)")
window_sum = sum(nums[:k])
best = window_sum
for right in range(k, len(nums)):
window_sum += nums[right] - nums[right - k]
best = max(best, window_sum)
return best / k
assert abs(find_max_average([4, 9, 2, 12, 7, 1, 10], 3) - 23 / 3) < 1e-9Practice करो. Confidence आएगा.
Your progress stays on this device. Solve first, tick later. तू खुद से cheat मत करना.
कल interview है? ये साथ ले जाओ.
Day 5 का full guide — concepts, patterns, code और practice, एक PDF में.
अभी भी doubt है?
Prefix sum से भी कर सकते हैं?+
हाँ. Prefix sums बनाओ और हर window का sum pref[r+1]-pref[l]. O(n) preprocessing + O(n) queries, पर prefix array O(n) extra space लेता है. Single fixed-size pass में window O(1) extra space देती है.
सब negative हैं तो?+
Algorithm फिर भी सही है. Best first window से initialize होना चाहिए, zero से नहीं.
दो पड़ोसी windows में क्या बदला? बस वही update करो. Next: HashMap से repeated searching हटाओ.