016 — Online Stock Span¶

Source¶

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-এ আসছে

1. Problem in simple words¶

তোমাকে দিনের পর দিন একটা একটা করে 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

2. Which basic idea does this inherit from?¶

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

3. What is the hidden math or logic?¶

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

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

4. Which data structure is needed?¶

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

5. Why this data structure fits¶

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

6. Real-life analogy¶

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

7. Visual explanation¶

দাম পরপর 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                   [...,(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

8. Example input and 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]

9. Brute force thinking¶

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

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

10. Why brute force is slow¶

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

11. Key observation¶

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

12. Optimized intuition¶

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

13. Thinking tweak¶

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

14. Step-by-step dry run¶

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

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

পরের call next(60):

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

15. Python solution¶

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!")

16. Line-by-line code explanation¶

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।

17. Output walkthrough¶

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!।

18. Time complexity¶

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

19. Space complexity¶

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

20. Common mistakes¶

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

21. Which basic problem this inherits from¶

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

22. Similar harder problems¶

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)

23. Pattern learned¶

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

24. Final summary¶

ভবিষ্যতের আমাকে: 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।