#স্লাইডিং উইন্ডো #মনোটোনিক ডিক #ডিকিউ #রেঞ্জ মিনিমাম কুয়েরি #ডাটা স্ট্রাকচার #অ্যালগরিদম #প্রবলেম সলভিং #কম্পিটিটিভ প্রোগ্রামিং #প্রিফিক্স সাম #টু পয়েন্টার #sliding window minimum #monotonic deque #spoj #leetcode
স্লাইডিং উইন্ডো মিনিমামঃ এই O(n) ট্রিকটা কেন ইন্টারভিউ আর প্রোডাকশন গুরুত্বপূর্ণ
2026-09-24 · 33 min read

আপনার সার্ভারের শেষ ৬০ সেকেন্ডের সবচেয়ে কম রেসপন্স টাইম কত? গত ২০ ক্যান্ডেলে কয়েনের সর্বনিম্ন দাম কী ছিল? সেন্সরের শেষ ১০০ রিডিংয়ের মিনিমাম? তিনটাই একই প্রশ্নঃ একটা sliding window ভেতরের সর্বনিম্ন সংখ্যা। আর বর্তমানে এসে এই প্রশ্নটা আগের চেয়ে বেশি ঘুরছে। কারণ ডেটা এখন "টেবিলে জমা" থাকে না, স্ট্রিম হয়ে বয়ে যায়। Kafka, Flink, ksqlDB, টাইম-সিরিজ ডাটাবেজ, এজ ডিভাইসের ছোট্ট RAM, সবখানে একই চাহিদাঃ ডেটা একবারই দেখব, দুইবার না। চলুন, সমস্যাটা গোড়া থেকে ধরি।
সমস্যাটা ঠিক কী
একটা অ্যারে arr-এ n টা সংখ্যা আছে। একটা উইন্ডো সাইজ m দেওয়া। m আকারের প্রতিটা পাশাপাশি সাবঅ্যারের সর্বনিম্ন সংখ্যা বের করতে হবে। উদাহরণঃ arr = [7, 2, 9, 4, 11, 3, 5], m = 3
| উইন্ডো | সর্বনিম্ন |
|---|---|
| 7, 2, 9 | 2 |
| 2, 9, 4 | 2 |
| 9, 4, 11 | 4 |
| 4, 11, 3 | 3 |
| 11, 3, 5 | 3 |
আউটপুট: [2, 2, 4, 3, 3]
m ফিক্সড না, ১ থেকে n যেকোনো কিছু হতে পারে।
ধাপ ১ঃ সৎ কিন্তু ধীর সমাধান
n ছোট হলে ভাবার কিছু নেই। প্রতিটা উইন্ডো ধরে min() চালিয়ে দিনঃ
def windowed_min_bruteforce(arr, m):
out = []
for start in range(len(arr) - m + 1):
out.append(min(arr[start:start + m]))
return out
জটিলতা O(n * m), সবচেয়ে খারাপ ক্ষেত্রে O(n²)। n = 10⁶ হলে এই কোড আপনার কফি ব্রেকের চেয়েও লম্বা হবে।
ধাপ ২ঃ সেগমেন্ট ট্রি; কাজ করে, কিন্তু ওভারকিল
সেগমেন্ট ট্রি বা স্পার্স টেবিল দিয়ে প্রতিটা কুয়েরি O(log n), মোট O(n log n)। খারাপ না। কিন্তু এখানে উইন্ডোগুলো এলোমেলো নয়। ওরা এক ধাপে এক ঘর করে ডানে সরে। এই "নিয়মটা" আমরা ব্যবহার করছি না, অর্থাৎ টাকা ফেলে দিচ্ছি। আর স্ট্রিমিং সিস্টেমে সেগমেন্ট ট্রি মানে পুরো ডেটা মেমোরিতে রাখা। স্ট্রিম তো শেষই হয় না, কী রাখবেন?
ধাপ ৩ঃ আসল ইনসাইট; "যে বড়, তার আর কোনো ভবিষ্যৎ নেই"
এখানেই আসল মজা। একটা ছোট্ট কিন্তু নির্মম পর্যবেক্ষণঃ
ধরুন
arr[i]আরarr[j]-এ দুটো সংখ্যা আছে, যেখানেi < jএবংarr[i] >= arr[j]। তাহলেarr[i]আর কোনোদিন কোনো উইন্ডোর মিনিমাম হতে পারবে না।
কেন? কারণ যে উইন্ডোতেই i থাকবে, তার ডানপাশে j-ও থাকবে (যেহেতু j পরে, আর উইন্ডো ডানদিকে সরে) অথবা i উইন্ডো থেকে বেরিয়েই যাবে। যতক্ষণ i টিকে আছে, j-ও আছে, আর j ছোট। তাহলে i-কে বাঁচিয়ে রেখে লাভ কী? মনোটোনিক ডিক হলো সেই সহকর্মী, যে শুধু কাজে লাগবে এমন জিনিসটাই মনে রাখে। বাকিটা এক সেকেন্ডে ডিলিট করে দেয়, কোনো আবেগ ছাড়াই। তাই আমরা একটা ডাবল-এন্ডেড কিউ (deque) রাখব, যেখানেঃ
- সামনে (front) থাকবে বর্তমান উইন্ডোর সর্বনিম্ন সংখ্যার ইনডেক্স
- সামনে থেকে পেছনে গেলে সংখ্যাগুলো বাড়তে থাকবে (monotonically increasing)
- আমরা ভ্যালু নয়, ইনডেক্স রাখব, নাহলে "কে উইন্ডোর বাইরে চলে গেছে" বোঝা যাবে না
প্রতিটা নতুন সংখ্যার জন্য মাত্র তিনটা কাজঃ
- পেছন থেকে ছাঁটাইঃ ডিকের শেষে যতগুলো সংখ্যা নতুন সংখ্যার চেয়ে বড় বা সমান, সবগুলো বের করে দিন (ওরা মৃত)
- পেছনে ঢোকানঃ নতুন ইনডেক্স append করুন
- সামনে থেকে ছাঁটাইঃ ডিকের সামনের ইনডেক্স যদি উইন্ডোর বাইরে চলে যায়, বের করে দিন
উইন্ডো পূর্ণ হলেই উত্তর = arr[deque.front()]।
ছোট্ট একটা ট্রেস
arr = [8, 30, 12, 9, 3], m = 3। ডিকে ইনডেক্স রাখছি, পাশে ভ্যালু দেখাচ্ছি:
| i | arr[i] | কাজ | ডিক (ভ্যালু) | উইন্ডো মিন |
|---|---|---|---|---|
| 0 | 8 | ঢোকাও | [8] | - |
| 1 | 30 | 8 ছোট, থাকুক; 30 ঢোকাও | [8, 30] | - |
| 2 | 12 | 30 ≥ 12 → বাদ | [8, 12] | 8 |
| 3 | 9 | 12 ≥ 9 → বাদ; ইনডেক্স 0 উইন্ডোর বাইরে → বাদ | [9] | 9 |
| 4 | 3 | 9 ≥ 3 → বাদ | [3] | 3 |
আউটপুট [8, 9, 3], হাতে মিলিয়ে দেখুন, ঠিক আছে।
কোড
পাইথন (প্রোডাকশন-সেফ, ইনডেক্স-ভিত্তিক):
from collections import deque
def windowed_min(arr, m):
dq = deque() # indices, values increasing from front to back
out = []
for i, val in enumerate(arr):
while dq and arr[dq[-1]] >= val:
dq.pop()
dq.append(i)
if dq[0] <= i - m:
dq.popleft()
if i >= m - 1:
out.append(arr[dq[0]])
return out
C++ (কম্পিটিটিভ প্রোগ্রামিংয়ের জন্য):
vector<int> windowedMin(const vector<int>& a, int m) {
deque<int> dq;
vector<int> out;
for (int i = 0; i < (int)a.size(); i++) {
while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
dq.push_back(i);
if (dq.front() <= i - m) dq.pop_front();
if (i >= m - 1) out.push_back(a[dq.front()]);
}
return out;
}
জটিলতা কেন O(n)?
দেখে মনে হয় ভেতরের while লুপটা খরচ বাড়াচ্ছে। বাড়াচ্ছে না, কারণ প্রতিটা ইনডেক্স জীবনে ঠিক একবার ঢোকে, আর সর্বোচ্চ একবার বের হয়। মোট অপারেশন 2n-এর বেশি না। এটাই amortized analysis-এর সৌন্দর্যঃ একটা ধাপ ব্যয়বহুল হতে পারে, কিন্তু গড়ে সবাই সস্তা।
- সময়: O(n)
- মেমোরি: O(m), পুরো অ্যারে নয়, শুধু উইন্ডো। এটাই স্ট্রিমিংয়ের জন্য সোনার খনি।
যে চার জায়গায় মানুষ হোঁচট খায়
>=না>? সমান মান পেলেও পেছন থেকে বাদ দিন (>=)। ডিক ছোট থাকে, উত্তর একই।>দিলেও উত্তর ঠিক, শুধু বেশি জায়গা খায়।- ভ্যালু রাখাঃ ভ্যালু রাখলে উইন্ডোর বাইরের জিনিস চিনতে পারবেন না। ইনডেক্স রাখুন।
- ক্রম উল্টে ফেলাঃ আগে পেছনের ছাঁটাই ও push, তারপর সামনের ছাঁটাই। এই ক্রমটা রাখলে এজ কেস নিজে থেকেই সামলে যায়।
m > n: আলাদা করে হ্যান্ডেল করুন, নাহলে খালি লিস্ট ফিরবে আর কলার অবাক হবে।
ম্যাক্সিমাম দরকার? তুলনার চিহ্ন উল্টে দিন (<=)। ব্যস।
বর্তমানে এই অ্যালগোরিদম কোথায় বসে আছে
pandas/Polars-এরrolling().min()ভেতরে এই ডিক-ট্রিকই, নাহলে বড় ডেটাফ্রেমে সেকেন্ড লাগত- অবজারভেবিলিটিঃ rolling min/max latency, SLO burn-rate ড্যাশবোর্ড
- ট্রেডিং বটঃ Donchian channel, ব্রেকআউট ডিটেকশন সবই rolling min/max
- এজ ও IoT: যেখানে RAM কিলোবাইটে মাপা হয়, ওখানে
O(m)মেমোরিই বাঁচার শর্ত - অটোস্কেলিংঃ শেষ k মিনিটের সর্বনিম্ন ফ্রি মেমোরি দেখে স্কেল-আপের সিদ্ধান্ত
- LLM-এর দুনিয়াতেওঃ sliding-window attention-এর "শুধু সাম্প্রতিক উইন্ডো রাখো" দর্শনটা একই পরিবারের চিন্তা। অ্যালগোরিদম আলাদা, কিন্তু মনোভাব এক
অর্থাৎ ভবিষ্যৎ যত বেশি real-time হচ্ছে, ততই "এক পাসে, কম মেমোরিতে" ধরনের অ্যালগোরিদমের দাম বাড়ছে। এটা পুরনো CP ট্রিক নয়, এটা ইনফ্রাস্ট্রাকচার।
দুটো চিন্তার সমস্যা ও সমাধান
সমস্যা ১ঃ মনোটোন রেঞ্জ কুয়েরি
প্রশ্নঃ n টা সংখ্যা এবং q টা রেঞ্জ [a₁,b₁], [a₂,b₂], …, [a_q,b_q] দেওয়া, যেখানে প্রতিটা i-এর জন্য aᵢ ≤ aᵢ₋₁ এবং bᵢ ≤ bᵢ₋₁। প্রতিটা রেঞ্জের সর্বনিম্ন সংখ্যা বের করতে হবে।
মূল চাবিঃ রেঞ্জগুলোর দুই প্রান্তই ক্রমশ বাঁয়ে সরছে। অর্থাৎ উল্টো দিক থেকে (i = q থেকে 1) প্রসেস করলে দুই প্রান্তই ক্রমশ ডানে সরে। আর তখন এটা হুবহু স্লাইডিং উইন্ডোর সমস্যা, শুধু উইন্ডোর দৈর্ঘ্য পরিবর্তনশীল। যেহেতু দুটো পয়েন্টারই কখনো পেছনে যায় না, একটাই ফরওয়ার্ড সুইপ যথেষ্ট।
from collections import deque
def monotone_range_minimums(arr, ranges):
# ranges[i] = (a, b), 0-indexed inclusive; a and b are non-increasing in i
dq = deque()
right = 0 # next index to push
answers = [0] * len(ranges)
for i in range(len(ranges) - 1, -1, -1):
a, b = ranges[i]
while right <= b: # grow the window rightwards
while dq and arr[dq[-1]] >= arr[right]:
dq.pop()
dq.append(right)
right += 1
while dq[0] < a: # shrink from the left
dq.popleft()
answers[i] = arr[dq[0]]
return answers
জটিলতাঃ O(n + q)। right পয়েন্টার সারা জীবনে সর্বোচ্চ n ঘর এগোয়, আর প্রতিটা ইনডেক্স একবার ঢোকে-একবার বেরোয়। সর্ট করার দরকারও নেই, সেগমেন্ট ট্রিরও দরকার নেই।
সাধারণ কেসে (রেঞ্জ এলোমেলো হলে) এই ট্রিক খাটে না। তখন অফলাইনে Mo's algorithm, নয়তো স্পার্স টেবিল (
O(n log n)প্রি-প্রসেস,O(1)কুয়েরি)। মনোটোনিসিটিই এখানে উপহার।
সমস্যা ২ঃ SPOJ PARSUMS - Nonnegative Partial Sums
প্রশ্নঃ a₀ … aₙ₋₁ দেওয়া। k ঘর সাইক্লিক শিফট মানে সিকোয়েন্সটা হয় aₖ, aₖ₊₁, …, aₙ₋₁, a₀, …, aₖ₋₁। কয়টা শিফটে সব প্রিফিক্স সাম ≥ 0 থাকে? (n ≤ 10⁶)। সমাধানের পথ (তিন লাইনে):
অ্যারেটা দুইবার জোড়া দিন (দৈর্ঘ্য
2n)। তাহলে যেকোনো সাইক্লিক শিফট একটা সাধারণ কনটিগুয়াস সেগমেন্ট হয়ে যায়প্রিফিক্স সাম
P[0] = 0,P[j] = a₀ + … + a_{j−1}শিফট
k-এর প্রিফিক্স সামগুলো হলোP[k+i] − P[k], যেখানেi = 1…n। সবগুলো≥ 0হওয়ার শর্ত মানেঃmin(P[k+1 … k+n]) ≥ P[k]
আর এটা ঠিক n সাইজের উইন্ডোতে P-এর সর্বনিম্ন মান। অর্থাৎ আমাদের সেই মনোটোনিক ডিক, হুবহু।
from collections import deque
def count_nonnegative_shifts(a):
n = len(a)
doubled = a + a
prefix = [0] * (2 * n + 1)
for i, val in enumerate(doubled):
prefix[i + 1] = prefix[i] + val
dq = deque() # indices into prefix, values increasing
count = 0
for j in range(1, 2 * n + 1):
while dq and prefix[dq[-1]] >= prefix[j]:
dq.pop()
dq.append(j)
k = j - n # window is prefix[k+1 .. k+n]
if k >= 0:
while dq[0] <= k:
dq.popleft()
if k < n and prefix[dq[0]] >= prefix[k]:
count += 1
return count
জটিলতাঃ সময় O(n), মেমোরি O(n)। n = 10⁶ আর ১০ টা টেস্ট কেসেও নিশ্চিন্ত। C++-এ long long ব্যবহার করুন। 10⁶ × 1000 প্রিফিক্স সাম int-এ ধরবে না, এখানেই বেশিরভাগ WA আসে।
প্র্যাকটিস লিস্ট
ধারণা পাকা করতে এই ক্রমে যানঃ
- LeetCode 239 – Sliding Window Maximum
- SPOJ ARRAYSUB
- SPOJ PARSUMS
- LeetCode 862 – Shortest Subarray with Sum at Least K
- LeetCode 1438
শেষ কথা
এই অ্যালগোরিদম থেকে মুখস্থ করার মতো কিছু নেই, শেখার মতো একটা জিনিস আছেঃ
সমস্যার কাঠামোতে যে নিয়ম লুকিয়ে আছে, সেটা খুঁজে বের করলে জেনেরিক ডাটা স্ট্রাকচারের দরকার পড়ে না।
উইন্ডো একদিকে সরে, এই একটা বাক্য থেকেই O(n log n) নেমে O(n) হলো, মেমোরি O(n) থেকে O(m)। একই চিন্তা দিয়েই ঘটে monotonic stack, two pointers, convex hull trick পুরো একটা পরিবার। ডিক আপনাকে একটা জীবনদর্শনও শেখায়ঃ যেটা আর কখনো কাজে লাগবে না, সেটা ধরে রাখা মেমোরি লিক। কোডে, এবং কোডের বাইরেও।