016 — Online Stock Span

Problem link ও উৎস

• Original source: Classic monotonic-stack exercise (online / streaming)
• Platform: LeetCode — https://leetcode.com/problems/online-stock-span/
• Topic: stack (monotonic, online)
• Difficulty: Medium
• Pattern: monotonic stack — online
• Basic idea inherited from: Problem 9 (monotonic stack), কিন্তু value গুলো একটা একটা করে streaming-এ আসছে

প্রশ্ন ও উদাহরণ

সহজ করে প্রশ্ন

তোমাকে দিনের পর দিন একটা একটা করে stock-এর দাম দেওয়া হবে (আগে থেকে পুরো list পাওয়া যায় না — streaming)। প্রতিটা নতুন দামের জন্য তার span বলতে হবে: আজ সহ পেছনের দিকে পরপর কত দিন দাম আজকের দামের চেয়ে বেশি ছিল না (মানে ≤ আজকের দাম)।

উদাহরণ

দাম : 100  80  60  70  60  75  85
span:   1   1   1   2   1   4   6
- 75-এর span 4: আজ(75) + 60 + 70 + 60 -> পরপর 4 দিন ≤ 75
- 85-এর span 6: আজ + 75 + 60 + 70 + 60 + 80 -> 6 দিন ≤ 85

Input ও output

উদাহরণ

ধারাবাহিক next() call (একটাই StockSpanner instance):
prices : [100, 80, 60, 70, 60, 75, 85]
spans  : [  1,  1,  1,  2,  1,  4,  6]

Edge case 1 (কঠোর বাড়তি): [31, 41, 48, 59, 79] -> [1, 2, 3, 4, 5]
Edge case 2 (কঠোর কমতি)  : [10, 9, 8, 7]        -> [1, 1, 1, 1]
Edge case 3 (একটাই দাম)  : [50]                 -> [50-এর span 1]

চেনা উদাহরণে বোঝা

ভাবো তুমি দিনে দিনে রসিদ জমাচ্ছ একটা গাদায়। আজকের দাম একটা নতুন রসিদ। পেছনে তাকিয়ে দেখো — যত দিনের দাম আজকের সমান বা কম, তত দিনের রসিদ একসাথে তুলে নিয়ে আজকের রসিদের সাথে ক্লিপ করে দাও, আর তাদের গোনা সংখ্যাটা মনে রেখে দাও। পরে আরও বড় দাম এলে, সে শুধু তোমার ক্লিপ-করা পুরো বান্ডিলটা এক টানে তুলে নেবে — ভেতরের আলাদা রসিদ আবার গুনতে হবে না।

ভিত্তির ধারণা

আগের কোন ধারণাটি লাগবে

এটা Problem 9 (monotonic stack)-এর online/streaming রূপ। সেখানে পুরো array আগে থেকে ছিল; এখানে value গুলো এক এক করে আসে আর তখনই উত্তর দিতে হয়। দিকটাও উল্টো — next greater না, বরং previous greater পর্যন্ত পেছনের distance। মূল machinery একই: একটা decreasing monotonic stack, নতুন value এসে নিজের চেয়ে ছোট/সমানদের "গিলে ফেলে" তাদের span যোগ করে নেয়।

ভেতরের যুক্তি

লুকানো logic: আজকের span বাড়তে বাড়তে থামে ঠিক সেই দিনে যেদিন দাম আজকের চেয়ে strictly বেশি ছিল (previous greater element)। তার আগের সব দিন আজকের চেয়ে ছোট বা সমান।

চালাকিটা হলো — আগেই হিসাব-করা span গুলো জমিয়ে রাখা। নতুন দাম p এলে, stack-এর top যদি ≤ p হয়, তবে ওই দিনের span (যা তার নিজের পেছনের ছোট দিনগুলোকে আগেই গুনে রেখেছে) পুরোটাই আজকের span-এ যোগ হয়ে যায়। তাই আগের দিনগুলো আবার গোনার দরকার নেই — span গুলো compressed history হিসেবে কাজ করে।

কী দিয়ে তথ্য রাখব

একটা monotonic stack যেখানে (price, span) জোড়া রাখি (Python-এ list of tuple)। price গুলো নিচ-থেকে-উপর strictly decreasing থাকে। span জমা থাকায় গিলে-ফেলা দিনগুলোর হিসাব এক ধাপেই যোগ হয়। এটা একটা class (StockSpanner) হিসেবে রাখি, কারণ state (stack) call-এর পর call ধরে রাখতে হয়।

এটি কেন উপযুক্ত

"আজকের আগে পরপর কত দিন ≤ আজ" = "previous strictly-greater পর্যন্ত distance" — monotonic stack-এর কাজ। streaming বলে আমরা পুরো history রাখতে পারি না/চাই না; কিন্তু decreasing stack-এ শুধু "এখনো প্রাসঙ্গিক" দিনগুলো (ভবিষ্যতে কারো span-এ বাধা হতে পারে যারা) থাকে, প্রত্যেকে নিজের পেছনের ছোট দিনদের span নিয়ে। প্রতিটা দিন বড়জোর একবার push আর একবার pop হয় → amortized O(1) প্রতি call।

ধাপে ধাপে সমাধান

প্রথম সরল উপায়

সরল চিন্তা: প্রতিটা দাম একটা list-এ জমাও; নতুন দাম এলে list-এর শেষ থেকে পেছনের দিকে hাঁটো যতক্ষণ দাম ≤ আজকের, গুনতে থাকো; প্রথম strictly-বড় দাম পেলে (বা list শেষ হলে) থামো।

উদাহরণ

prices.append(p)
span=1; j=len-2; while j>=0 and prices[j]<=p: span++; j--
return span

কোথায় বেশি কাজ হচ্ছে

প্রতিটা call-এ সবচেয়ে খারাপ ক্ষেত্রে পুরো ইতিহাস পেছনে hাঁটতে হয়। কঠোর-কমতে-থাকা দাম এলে (10, 9, 8, ... তারপর হঠাৎ 100) ওই বড় দিন গোটা history scan করে → m দিনে মোট O(m^2)। monotonic stack-এ span জমা থাকায় পুরনো দিনগুলো এক ধাপে যোগ হয় — মোট O(m), অর্থাৎ amortized O(1) প্রতি call।

যে বিষয়টি খেয়াল করতে হবে

মূল observation: একটা ছোট দিন (যার দাম আজকের ≤) ভবিষ্যতে আর কখনো কারো span থামাতে পারবে না — কারণ আজকের দিনই তার চেয়ে বড় আর নতুন। তাই তাকে stack থেকে ফেলে দেওয়া নিরাপদ, কিন্তু তার আগে তার span-টা আজকের span-এ যোগ করে নিতে হয়, যাতে তার পেছনের গোনা হারিয়ে না যায়।

আরও কম কাজে সমাধান

stack-এ (price, span) রাখো, price decreasing। নতুন দাম price এলে span = 1 দিয়ে শুরু করো; যতক্ষণ stack খালি নয় আর top-এর price ≤ price, ততক্ষণ top pop করে তার span-টা span-এ যোগ করো (ওই দিন আর তার গিলে-ফেলা দিনরা সবাই আজকের ≤)। তারপর (price, span) push করে span ফেরত দাও।

ভাবনার পরিবর্তন

মোচড়: প্রতিটা পুরনো দিনকে আলাদাভাবে আবার গোনার বদলে ভাবো "আগের দিন তার span-এ নিজের পেছনের সব ছোট দিন আগেই গুনে রেখেছে"। তাই top গিলে ফেলার সময় শুধু তার জমানো span-টা যোগ করলেই গোটা পেছনের অংশ এক ধাপে চলে আসে — span হলো compressed history।

ছবিতে বোঝা

দাম পরপর 100, 80, 60, 70, 60, 75, 85 এলে stack-এ (price, span) (top ডানে):

উদাহরণ

price  action                                          stack(price,span)        span
100    কেউ নেই -> span=1, push                          [(100,1)]                1
80     top 100<=80? না -> span=1, push                  [(100,1),(80,1)]         1
60     top 80<=60? না -> span=1, push                   [(100,1),(80,1),(60,1)]  1
70     top 60<=70 -> span+=1=2, pop; 80<=70? না, push   [(100,1),(80,1),(70,2)]  2
60     top 70<=60? না -> span=1, push                   [(100,1),(80,1),(70,2),(60,1)]      1
75     60<=75 +1=2 pop; 70<=75 +2=4 pop; 80<=75? না     [(100,1),(80,1),(75,4)]  4
85     75<=85 +4=5 pop; 80<=85 +1=6 pop; 100<=85? না    [(100,1),(85,6)]         6

ছোট input-এ ধাপে ধাপে

call ক্রম next(70) after stack [(100,1),(80,1),(60,1)]:

1. span = 1
2. top (60,1), 60 <= 70 → pop, span += 1 → 2
3. top (80,1), 80 <= 70? না → থামো
4. push (70, 2) → stack [(100,1),(80,1),(70,2)]
5. return 2

পরের call next(60):

1. span = 1
2. top (70,2), 70 <= 60? না → থামো
3. push (60, 1); return 1

কোড ও ব্যাখ্যা

Python

Python

class StockSpanner:
    def __init__(self):
        self.stack = []                          # (price, span) জোড়া, price decreasing

    def next(self, price):
        span = 1                                  # আজকের দিনটা নিজে গোনা
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]           # গিলে-ফেলা দিনের span যোগ
        self.stack.append((price, span))
        return span

# ---- tests ----
spanner = StockSpanner()
prices = [100, 80, 60, 70, 60, 75, 85]
spans = [spanner.next(p) for p in prices]
assert spans == [1, 1, 1, 2, 1, 4, 6]

s2 = StockSpanner()
assert [s2.next(p) for p in [31, 41, 48, 59, 79]] == [1, 2, 3, 4, 5]   # কঠোর বাড়তি

s3 = StockSpanner()
assert [s3.next(p) for p in [10, 9, 8, 7]] == [1, 1, 1, 1]             # কঠোর কমতি

s4 = StockSpanner()
assert s4.next(50) == 1                                                 # একটাই দাম
print("সব test pass!")

কোডের প্রতিটি অংশ

• self.stack = [] — call-এর পর call ধরে রাখা state; (price, span) জোড়া, price decreasing।
• span = 1 — আজকের দিনটা সবসময় নিজের span-এ গোনে।
• while self.stack and self.stack[-1][0] <= price: — top-এর দাম আজকের ≤ হলে সে আজকের span-এ মিশে যাবে।
• span += self.stack.pop()[1] — pop করা দিনের জমানো span (তার পেছনের ছোট দিনসহ) পুরোটা যোগ।
• self.stack.append((price, span)) — আজকের দিন তার মোট span নিয়ে stack-এ; ভবিষ্যতে কেউ একে গিললে এই span-ই কাজে দেবে।
• return span — আজকের span।

Output মিলিয়ে দেখা

StockSpanner instance-এ [100,80,60,70,60,75,85] দিলে section 7-এর trace মতো span হয় [1,1,1,2,1,4,6]; বিশেষ করে 85 এসে (75,4) আর (80,1) গিলে span = 1+4+1 = 6। কঠোর-কমতে-থাকা [10,9,8,7]-এ কেউ কাউকে গিলতে পারে না, সব span 1। সব assert pass করে শেষে print: সব test pass!।

খরচ ও সাধারণ ভুল

সময়

Amortized O(1) প্রতি next() call — প্রতিটা দাম জীবনে বড়জোর একবার push আর একবার pop হয়; m call-এ মোট O(m)।

অতিরিক্ত জায়গা

O(m) — সবচেয়ে খারাপ ক্ষেত্রে (কঠোর-কমতে-থাকা দাম, যেমন 100, 99, 98, ...) কোনো pop হয় না, সব দিন stack-এ জমে।

যে ভুলগুলো এড়াতে হবে

• < বনাম <= — span-এ আজকের সমান দামের দিনও গোনা হয় ("বেশি ছিল না" = ≤), তাই <= লাগে; < দিলে সমান দামের দিন বাদ পড়বে।
• pop করার সময় span যোগ না করা — শুধু পপ করলে গিলে-ফেলা দিনের পেছনের গোনা হারিয়ে যায়, span কম আসে।
• প্রতি call-এ নতুন stack বানানো — state ধরে রাখতে হয়; stack-টা instance-level (__init__-এ) হতে হবে।

শেখা ও পরের অনুশীলন

ভিত্তির সঙ্গে সম্পর্ক

ভিত্তি: Problem 9-এর monotonic stack, এখানে online/streaming আর previous-greater দিকে। chapter-এর ../patterns.md-এর Pattern 4 (Monotonic Stack); নতুন অংশ — span জমিয়ে রেখে compressed history হিসেবে ব্যবহার আর state ধরে রাখা।

পরের অনুশীলন

• Daily Temperatures (offline next greater) — https://leetcode.com/problems/daily-temperatures/ (এই tracker-এর #9)
• Sum of Subarray Minimums (monotonic stack + contribution) — https://leetcode.com/problems/sum-of-subarray-minimums/ (#17)
• Largest Rectangle in Histogram — https://leetcode.com/problems/largest-rectangle-in-histogram/ (#20)

কৌশলটি মনে রাখুন

Online monotonic stack with stored counts: "streaming", "প্রতিটা নতুন value-তে পেছনের span/count" দেখলে decreasing stack-এ (value, count) রাখো; নতুন value এসে ছোট/সমানদের গিলে তাদের count যোগ করে নেয় — count জমা থাকায় amortized O(1)।

নিজেকে যাচাই করুন

ভবিষ্যতের আমাকে: span = previous-greater পর্যন্ত distance, কিন্তু streaming-এ। stack-এ (price, span) রাখো; নতুন দাম ≤-দের pop করে তাদের span যোগ করো (compressed history)। <= মনে রেখো, state ধরে রাখো। "online", "span", "streaming next/previous greater" দেখলে এই pattern।

---

মনে রাখার নিয়ম (legal): সব নিজের ভাষায় লেখা; problem statement copy করা হয়নি; official link শুধু attribution-এর জন্য; "asked by Google/Amazon" দাবি নেই — এটা একটা common interview pattern।