017 — Sum of Subarray Minimums¶

Source¶

Original source: Classic monotonic-stack + contribution exercise
Platform: LeetCode — https://leetcode.com/problems/sum-of-subarray-minimums/
Topic: stack (monotonic) + contribution counting
Difficulty: Medium
Pattern: monotonic stack + contribution technique
Basic idea inherited from: math level 5-এর contribution technique (prefix-difference-contribution) — প্রতিটা element আলাদা করে জিজ্ঞেস করো "আমি কয়টা subarray-র min?", তারপর সব contribution যোগ করো

1. Problem in simple words¶

তোমাকে একটা সংখ্যার array arr দেওয়া আছে। তার প্রতিটা contiguous subarray ধরো, প্রতিটার ভেতরের সবচেয়ে ছোট সংখ্যাটা (minimum) বের করো, আর সেই সব minimum যোগ করো। উত্তর বড় হতে পারে, তাই 10**9 + 7 দিয়ে modulo নিয়ে ফেরত দাও।

arr = [3, 1, 2, 4]-এর জন্য সব subarray আর তাদের min দেখো:

[3]        -> 3
[3,1]      -> 1
[3,1,2]    -> 1
[3,1,2,4]  -> 1
[1]        -> 1
[1,2]      -> 1
[1,2,4]    -> 1
[2]        -> 2
[2,4]      -> 2
[4]        -> 4
যোগফল      = 3+1+1+1+1+1+1+2+2+4 = 17

2. Which basic idea does this inherit from?¶

এটা contribution technique-এর সরাসরি প্রয়োগ (math level 5, prefix-difference-contribution)। মূল মন্ত্র: পুরো যোগফলকে subarray-ধরে-ধরে না ভেবে, element-ধরে-ধরে ভাবো। প্রশ্নটা উল্টে জিজ্ঞেস করো — "প্রতিটা arr[i] কয়টা subarray-র minimum হয়?" সেই সংখ্যাটা count[i] হলে পুরো উত্তর হলো sum(arr[i] * count[i])।

আর count[i] বের করতে লাগে monotonic stack (Problem 9, 16-এর machinery): বাঁয়ে আর ডানে arr[i]-এর "শাসন এলাকা" (যেখানে সে min থাকে) কতদূর ছড়ায়, সেটা previous/next-smaller দিয়ে মাপা যায়।

3. What is the hidden math or logic?¶

লুকানো logic: একটা subarray-তে arr[i] ঠিক তখনই min, যখন subarray-টা পুরোপুরি arr[i]-এর "এলাকা"-র ভেতরে থাকে আর i-কে ছুঁয়ে থাকে। এই এলাকা বাঁ দিকে থামে সেই index-এ যেখানে প্রথম arr[i]-এর চেয়ে ছোট কেউ আছে, ডান দিকেও তাই।

ধরা যাক:

left = i থেকে শুরু করে বাঁ দিকে কয়টা শুরু-বিন্দু বাছা যায় যেখানে arr[i] এখনো min থাকে।
right = i থেকে ডান দিকে কয়টা শেষ-বিন্দু বাছা যায়।

তাহলে arr[i]-কে min রাখা subarray-র সংখ্যা = left * right (বাঁ পছন্দ আর ডান পছন্দ স্বাধীন, তাই গুণ)। contribution = arr[i] * left * right।

সমান সংখ্যার ফাঁদ: array-তে সমান সংখ্যা থাকলে দুটো element একই subarray-র "min" হিসেবে দুবার গোনা হয়ে যেতে পারে। এটা ঠেকাতে এক পাশে strictly ছোট খুঁজি (<), অন্য পাশে ছোট-বা-সমান (<=) — তাহলে প্রতিটা subarray ঠিক একজনের দখলেই পড়ে, double-count হয় না।

4. Which data structure is needed?¶

একটা monotonic stack (Python-এ list) যেখানে index রাখি — দুবার ব্যবহার করি: একবার বাঁ-থেকে-ডান scan-এ prev_less (previous strictly-smaller) বের করতে, আরেকবার ডান-থেকে-বাঁ scan-এ next_le (next smaller-or-equal) বের করতে। সাথে দুটো array এই দূরত্বগুলো ধরে রাখে।

5. Why this data structure fits¶

"প্রতিটা element-এর জন্য বাঁ/ডানে প্রথম ছোট প্রতিবেশী" — এটা monotonic stack-এর হুবহু কাজ (Pattern 4)। প্রতিটা index stack-এ একবার ঢোকে আর বড়জোর একবার বের হয়, তাই দুটো pass-ই O(n)। contribution technique এর সাথে মিলে পুরো O(n^2)-সংখ্যক subarray-কে গোনার বদলে আমরা প্রতিটা element-কে একবার করে ছুঁয়ে কাজ সারি।

6. Real-life analogy¶

ভাবো একদল মানুষ পাশাপাশি দাঁড়িয়ে, প্রত্যেকের একটা উচ্চতা আছে, আর "সবচেয়ে খাটো লোকই দলের নেতা" — এই নিয়ম। প্রতিটা লোককে জিজ্ঞেস করো: "তুমি বাঁ দিকে কতদূর আর ডান দিকে কতদূর পর্যন্ত নেতা থাকতে পারো, যতক্ষণ না তোমার চেয়ে খাটো কেউ এসে পড়ছে?" সেই বাঁ-পরিসর আর ডান-পরিসর গুণ করলেই পাও — এই লোকটা কয়টা সম্ভাব্য দলের নেতা। সবার "নেতাগিরির হিসাব" যোগ করলেই মোট উত্তর।

7. Visual explanation¶

arr = [3, 1, 2, 4]-এ প্রতিটা element-এর এলাকা (left = বাঁ পরিসর, right = ডান পরিসর):

idx  val  prev_less(<)  next_le(<=)  left=i-PL  right=NL-i  count=L*R  contri=val*count
0     3      -1            1            1           1          1          3
1     1      -1            4 (n)        2           3          6          6
2     2       1            4 (n)        1           2          2          4
3     4       2            4 (n)        1           1          1          4
                                                          মোট contribution = 3+6+4+4 = 17

PL = previous strictly-smaller-এর index (নেই হলে -1); NL = next smaller-or-equal-এর index (নেই হলে n=4)।

8. Example input and output¶

Input : [3, 1, 2, 4]        -> Output: 17
Input : [11, 81, 94, 43, 3] -> Output: 444
Input : [2, 2, 2]           -> Output: 12   (6 subarray, প্রতিটার min 2)

Edge case 1 (একটা element) : [7]          -> 7
Edge case 2 (কঠোর বাড়তি)  : [1, 2, 3]    -> 1*6 + 2*2 + 3*1... = 10
Edge case 3 (কঠোর কমতি)    : [3, 2, 1]    -> প্রতিটা suffix-এর শেষজনই min

9. Brute force thinking¶

সবচেয়ে সরল চিন্তা: প্রতিটা শুরু i-র জন্য ডান দিকে এগোতে এগোতে চলমান min রাখো, আর প্রতিটা শেষ j-তে সেই min যোগফলে যোগ করো।

total = 0
for i in range(n):
    m = inf
    for j in range(i, n):
        m = min(m, arr[j])
        total += m

10. Why brute force is slow¶

দুটো nested loop মানে O(n^2)-সংখ্যক subarray, প্রতিটার জন্য O(1) কাজ হলেও মোট O(n^2)। n বড় হলে (যেমন 30000) এটা প্রায় 9*10^8 step — সময়ে আটকে যাবে। আমরা চাই প্রতিটা element-কে একবার ছুঁয়ে O(n)-তে কাজ শেষ করতে, আর সেটাই contribution + monotonic stack দেয়।

11. Key observation¶

মূল observation: subarray গুনে min যোগ করার বদলে, প্রতিটা element কয়বার min হিসেবে গোনা হবে সেটা সরাসরি বের করা যায়। arr[i] min থাকে ঠিক ততক্ষণ যতক্ষণ subarray-টা বাঁয়ে previous-smaller আর ডানে next-smaller পার না করে। এই দুই সীমানা monotonic stack এক pass-এ দিয়ে দেয়।

12. Optimized intuition¶

দুটো pass চালাও। প্রথমে বাঁ-থেকে-ডান একটা stack রেখে প্রতিটা i-র prev_less[i] (বাঁয়ের শেষ strictly ছোট index) বের করো — stack-এ arr[stack[-1]] >= arr[i] যতক্ষণ, pop করো; যা টেকে তার top-ই previous-smaller। তারপর ডান-থেকে-বাঁ আরেকটা stack রেখে next_le[i] (ডানের পরের ছোট-বা-সমান index) বের করো — এবার arr[stack[-1]] > arr[i] যতক্ষণ pop। শেষে প্রতিটা i-র জন্য left = i - prev_less[i], right = next_le[i] - i, আর arr[i] * left * right যোগ করো।

13. Thinking tweak¶

মোচড়: "সব subarray ঘুরে min যোগ করব" — এই দিক থেকে ভেবো না। উল্টে ভাবো — "প্রতিটা সংখ্যা মোট যোগফলে কতটা contribute করে?" একটা সংখ্যা v যতগুলো subarray-র min, ততবার v যোগফলে ঢোকে। তাই কাজটা হয়ে যায় "প্রতিটা v কয়বার min" গোনা — সেটাই বাঁ-পরিসর × ডান-পরিসর। strict/non-strict অসমতা দিয়ে সমান সংখ্যার double-count আটকাও।

14. Step-by-step dry run¶

Input [3, 1, 2, 4]:

prev_less pass (বাঁ→ডান, >= হলে pop): i=0 → stack খালি, prev_less[0]=-1, push 0; i=1(1) → 3>=1 pop 0, খালি, prev_less[1]=-1, push 1; i=2(2) → 1>=2? না, prev_less[2]=1, push 2; i=3(4) → 2>=4? না, prev_less[3]=2, push 3. → prev_less = [-1,-1,1,2]
next_le pass (ডান→বাঁ, > হলে pop): i=3 → খালি, next_le[3]=4, push 3; i=2(2) → 4>2 pop 3, খালি, next_le[2]=4, push 2; i=1(1) → 2>1 pop 2, খালি, next_le[1]=4, push 1; i=0(3) → 1>3? না, next_le[0]=1, push 0. → next_le = [1,4,4,4]
contribution: left=[1,2,1,1], right=[1,3,2,1] → 3*1*1 + 1*2*3 + 2*1*2 + 4*1*1 = 3+6+4+4 = 17
17 % (10**9+7) = 17 → return 17

15. Python solution¶

def sum_subarray_mins(arr):
    MOD = 10**9 + 7
    n = len(arr)

    prev_less = [-1] * n                       # বাঁয়ে শেষ strictly-ছোট element-এর index
    stack = []
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:   # >= : strict-less বাঁয়ে রাখি
            stack.pop()
        prev_less[i] = stack[-1] if stack else -1
        stack.append(i)

    next_le = [n] * n                          # ডানে পরের ছোট-বা-সমান element-এর index
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:    # > : ছোট-বা-সমান ডানে রাখি
            stack.pop()
        next_le[i] = stack[-1] if stack else n
        stack.append(i)

    total = 0
    for i in range(n):
        left = i - prev_less[i]                # i-তে শেষ হওয়া কয়টা subarray-তে arr[i] min
        right = next_le[i] - i                  # i-তে শুরু হওয়া কয়টা subarray-তে arr[i] min
        total += arr[i] * left * right
    return total % MOD

# ---- tests ----
def brute(arr):                                # সরল কিন্তু ধীর O(n^2) reference
    total = 0
    for i in range(len(arr)):
        m = arr[i]
        for j in range(i, len(arr)):
            m = min(m, arr[j])
            total += m
    return total % (10**9 + 7)

assert sum_subarray_mins([3, 1, 2, 4]) == 17
assert sum_subarray_mins([11, 81, 94, 43, 3]) == 444
assert sum_subarray_mins([7]) == 7                       # একটা element
assert sum_subarray_mins([2, 2, 2]) == 12                # সব সমান -> double-count নেই
assert sum_subarray_mins([5, 4, 3, 2, 1]) == brute([5, 4, 3, 2, 1])
assert sum_subarray_mins([3, 1, 2, 4]) == brute([3, 1, 2, 4])
print("সব test pass!")

16. Line-by-line code explanation¶

MOD = 10**9 + 7 — যোগফল বড় হতে পারে, তাই শেষে modulo।
prev_less pass — প্রতিটা i-র জন্য বাঁয়ের শেষ strictly ছোট index; >= দেখলে pop করি যাতে সমান সংখ্যাও সরে যায় (strict-less টেকে)।
next_le pass — ডান-থেকে-বাঁ গিয়ে ডানের পরের ছোট-বা-সমান index; এখানে > দেখলে pop, তাই সমান সংখ্যা টিকে থাকে (non-strict)। এই strict/non-strict অসমতাই double-count আটকায়।
left = i - prev_less[i] / right = next_le[i] - i — বাঁ আর ডান দিকের শাসন-পরিসর।
total += arr[i] * left * right — এই element কয়টা subarray-র min (left*right), তত গুণ তার value যোগফলে।
return total % MOD — চূড়ান্ত উত্তর modulo করে।

17. Output walkthrough¶

sum_subarray_mins([3,1,2,4]) → section 7-এর table মতো contribution 3,6,4,4, যোগফল 17। sum_subarray_mins([2,2,2]) → strict/non-strict জোড়ার কারণে তিনটা 2 মিলে ঠিক 12 (6 subarray × min 2), কোনো subarray দুবার গোনা হয় না। brute reference-এর সাথেও মিলে যায়। সব assert pass করে শেষে print: সব test pass!।

18. Time complexity¶

O(n) — দুটো monotonic-stack pass আর একটা contribution pass, প্রতিটা O(n); প্রতিটা index বড়জোর একবার push আর একবার pop হয়।

19. Space complexity¶

O(n) — prev_less, next_le দুটো array আর stack, সবচেয়ে খারাপ ক্ষেত্রে stack-এ n-টা index।

20. Common mistakes¶

দুই পাশেই একই অসমতা ব্যবহার করা (দুদিকেই < বা দুদিকেই <=) — সমান সংখ্যা থাকলে subarray গুলো double-count বা miss হয়; এক পাশে strict, আরেক পাশে non-strict লাগবে।
শেষে modulo না নেওয়া — বড় array-তে overflow না হলেও LeetCode ভুল উত্তর ধরবে।
prev_less/next_le-তে "নেই" ক্ষেত্রের sentinel ভুল দেওয়া (-1 আর n) — তাহলে পরিসরের হিসাব এক ঘর এদিক-ওদিক হয়ে যায়।

21. Which basic problem this inherits from¶

ভিত্তি: math level 5-এর contribution technique (prefix-difference-contribution) আর chapter-এর ../patterns.md Pattern 4 (Monotonic Stack)। Problem 9 (daily temperatures) আর 16 (stock span)-এর previous/next-smaller machinery এখানে দুবার ব্যবহার হয়, শুধু উত্তরটা distance নয় — পরিসরের গুণফল।

22. Similar harder problems¶

Sum of Subarray Ranges (max-min, দুটো contribution) — https://leetcode.com/problems/sum-of-subarray-ranges/
Largest Rectangle in Histogram (previous/next-smaller geometry) — https://leetcode.com/problems/largest-rectangle-in-histogram/ (এই tracker-এর #20)
Maximum Subarray Min-Product — https://leetcode.com/problems/maximum-subarray-min-product/

23. Pattern learned¶

Monotonic stack + contribution: "প্রতিটা subarray-র min/max-এর যোগফল/গণনা" দেখলে subarray না গুনে element-ধরে contribution গোনো — বাঁ ও ডানে previous/next-smaller দিয়ে শাসন-পরিসর বের করো, value * left * right যোগ করো, strict/non-strict জোড়া দিয়ে সমানদের double-count আটকাও।

24. Final summary¶

ভবিষ্যতের আমাকে: "সব subarray-র min-এর যোগ" = element-wise contribution। প্রতিটা v কয়টা subarray-র min = (বাঁ পরিসর) × (ডান পরিসর), যেখানে পরিসর থামে previous/next-smaller-এ। একদিকে <, আরেকদিকে <= — এটাই double-count-এর তালা। "subarray-র min/max-এর যোগফল" শব্দ দেখলেই এই জোড়া কৌশল মনে করবে।

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