077 — Sum of Subarray Minimums

এই level-এর সবচেয়ে কঠিন problem — কিন্তু ভয় পেও না, এটা 076-এর contribution চিন্তারই গাঢ় রূপ। 076-এ প্রতিটা element সব subarray-তে যোগ হতো; এখানে প্রতিটা element শুধু সেই subarray গুলোতে "গোনা" হয় যেখানে সে-ই minimum। তাই প্রশ্ন বদলায়: "তুমি কয়টা subarray-তে minimum?" উত্তরের জন্য লাগবে next-smaller span আর monotonic stack — যার আসল বাড়ি stack-and-queue folder। ধীরে, খুব ধীরে পড়ো; tie (সমান মান) সামলানোটাই আসল সূক্ষ্মতা।

Source

• Original source: Classic technique (contribution + monotonic stack spans)
• Platform: LeetCode — https://leetcode.com/problems/sum-of-subarray-minimums/
• Topic: Math-based programming fundamentals → Level 5: Prefix, Difference, Contribution
• Difficulty: Hard
• Pattern: contribution + next/previous-smaller spans (monotonic stack)
• Basic idea inherited from: 076 — Sum of All Subarrays

1. Problem in simple words

একটা array a (দৈর্ঘ্য n) দেওয়া। প্রতিটা contiguous subarray-র minimum (সবচেয়ে ছোট element) বের করো, তারপর সেই minimum গুলোর মোট যোগফল চাই। সংখ্যা বড় হতে পারে, তাই উত্তর 10^9 + 7 দিয়ে mod করে দাও।

যেমন a = [3, 1, 2, 4]-এর subarray গুলোর minimum যোগ করলে মোট 17। তোমার কাজ এই যোগফল দ্রুত বের করা — প্রতিটা subarray ধরে min বের করে যোগ না করে।

2. What is the math idea?

মূল idea হলো contribution technique + span গোনা। 076-এর মতো প্রতিটা element-এর অবদান গুনব, কিন্তু এবার শর্তসাপেক্ষে:

a[i]-এর অবদান = a[i] × (কয়টা subarray-তে a[i]-ই minimum)

a[i] কয়টা subarray-তে minimum? যতদূর বাঁয়ে যাওয়া যায় যেখানে a[i]-এর চেয়ে ছোট কেউ নেই (left রকম শুরু), গুণ যতদূর ডানে (right রকম শেষ)। অর্থাৎ দরকার প্রতিটা i-এর previous-smaller আর next-smaller element-এর দূরত্ব। তারপর:

উত্তর = Σ a[i] * left[i] * right[i]    (mod 10^9 + 7)

এই span দ্রুত বের করার যন্ত্র monotonic stack — O(n)-এ সব previous/next smaller।

3. Which basic idea does this inherit from?

মূলত 076 (Sum of All Subarrays) থেকে — সেই "প্রতিটা element কয়টা subarray-তে আছে, সেই count × মান" চিন্তা। পার্থক্য: 076-এ count ছিল (i+1)*(n-i) (সব subarray), এখানে count শুধু "যেখানে সে minimum"।

আর নতুন হাতিয়ার monotonic stack — span (next/previous smaller) বের করার যন্ত্র, যার বিস্তারিত ../../04-stack-and-queue/-তে (যেমন Next Greater Element, Daily Temperatures)। contribution-এর কাঠামো 076 থেকে, span-এর কৌশল stack folder থেকে — দুটো মিলে এই Hard problem। তাই দুটোই আগে থাকা দরকার।

4. Real-life analogy

ভাবো পাহাড়ি রাস্তায় পরপর কিছু খুঁটি, প্রতিটার উচ্চতা ভিন্ন। প্রতিটা খুঁটিকে জিজ্ঞেস করো: "তুমি কতদূর পর্যন্ত এলাকার সবচেয়ে ছোট খুঁটি?"

একটা খুঁটি বাঁ দিকে ততদূর "রাজত্ব" করে যতক্ষণ না তার চেয়ে খাটো কেউ আসে; ডান দিকেও তাই। এই বাঁ-দূরত্ব আর ডান-দূরত্ব গুণ করলে — সে কয়টা টানা অংশের (subarray) সবচেয়ে ছোট। সেই সব অংশে "সবচেয়ে ছোট"-এর হিসাবে তার উচ্চতাই গোনা হয়।

তাই মোট = প্রতিটা খুঁটির (উচ্চতা × কতগুলো অংশে সে সবচেয়ে ছোট)। খাটো খুঁটি অনেক অংশে রাজত্ব করে (দূর পর্যন্ত কেউ ছোট নেই), লম্বা খুঁটি অল্প — ঠিক এই কারণেই minimum-এর হিসাব এমন।

5. Visual explanation

a = [3, 1, 2, 4]। প্রতিটা element কতদূর বাঁয়ে-ডানে minimum:

index:        0     1     2     3
a:          [ 3 ] [ 1 ] [ 2 ] [ 4 ]

i=1 (মান 1, পুরো array-র সবচেয়ে ছোট):
   বাঁয়ে: 1-এর চেয়ে ছোট কেউ নেই index 0 পর্যন্ত → শুরু-option {0,1} = 2  (left)
   ডানে : 1-এর চেয়ে ছোট কেউ নেই শেষ পর্যন্ত    → শেষ-option {1,2,3} = 3  (right)
   1 minimum থাকে 2 × 3 = 6 টা subarray-তে → অবদান 1 × 6 = 6

প্রতিটা element-এর span আর অবদান:

index i:      0     1     2     3
a[i]:         3     1     2     4
left[i]:      1     2     1     1     ← বাঁয়ে শুরুর রকম (prev-smaller পর্যন্ত)
right[i]:     1     3     2     1     ← ডানে শেষের রকম (next-smaller পর্যন্ত)
অবদান:        3     6     4     4     ← a[i]*left*right

মোট = 3 + 6 + 4 + 4 = 17

মিলিয়ে দেখো (brute, প্রতি subarray-র min):

[3]=3  [1]=1  [2]=2  [4]=4
[3,1]=1  [1,2]=1  [2,4]=2
[3,1,2]=1  [1,2,4]=1
[3,1,2,4]=1
যোগ = 3+1+2+4 + 1+1+2 + 1+1 + 1 = 17   ✓

মূল কথা: ছোট element (1) দূর পর্যন্ত "minimum-রাজত্ব" করে (6টা subarray), তাই বেশি অবদান। left × right = কয়টা subarray-তে সে min।

6. Example input and output

a = [3, 1, 2, 4]            -> 17
a = [11, 81, 94, 43, 3]     -> 444    (LeetCode example)
a = [1, 2, 3, 4]            -> 20
a = [4, 3, 2, 1]            -> 20     (উল্টো দিকে একই, symmetric নয় তবু এখানে মিলল)
a = [2, 2, 2]               -> 12     (সব সমান — tie সাবধানে!)
a = [1, 3, 1, 3, 1]         -> 19     (একই মান বারবার)

সবচেয়ে গুরুত্বপূর্ণ edge case: সমান মান (tie)। [2, 2, 2]-এ যদি বাঁ আর ডান দুই দিকেই "≤" বা দুই দিকেই "<" ব্যবহার করো, একই subarray দুবার গোনা পড়বে বা বাদ পড়বে। সমাধান: এক দিকে strictly-smaller, অন্য দিকে smaller-or-equal — তাহলে সমান element-গুলোর মধ্যে প্রতিটা subarray ঠিক একবার গোনা হয়।

7. Brute force thinking

সব subarray ঘুরে প্রতিটার min বের করে যোগ। running min দিয়ে:

def sum_subarray_mins_brute(a):
    MOD = 10**9 + 7
    n = len(a)
    total = 0
    for l in range(n):
        m = a[l]
        for r in range(l, n):
            m = min(m, a[r])     # subarray (l..r)-এর running min
            total += m
    return total % MOD

সরল, ঠিক উত্তর — প্রতিটা শুরু l-এর জন্য r বাড়িয়ে min হালনাগাদ করে যোগ করে।

8. Why brute force may be slow

দুটো nested loop, প্রায় n²/2 subarray — O(n²)।

n = 30000 হলে:
  brute force: ~4.5 × 10^8 operation  (O(n²)) — TLE
  stack way  : ~30000 operation       (O(n) দুটো pass)

অপচয়টা: একই element নানা subarray-তে বারবার "min" হিসেবে গোনা হচ্ছে — অথচ "সে কয়টা subarray-তে min" এক স্প্যান-গোনায় বেরিয়ে আসে, প্রতিবার আলাদা না দেখে।

9. Better thinking

মূল insight: প্রতি subarray-র min না খুঁজে, প্রতিটা element কয়টা subarray-তে min গোনো — সেটা left[i] * right[i], যেখানে left = previous-smaller পর্যন্ত দূরত্ব, right = next-smaller পর্যন্ত দূরত্ব। span দুটো monotonic stack-এ O(n):

def sum_subarray_mins(a):
    MOD = 10**9 + 7
    n = len(a)
    prev_less = [-1] * n          # previous strictly-smaller-এর index
    next_le = [n] * n            # next smaller-or-equal-এর index (tie ভাঙতে)
    st = []
    for i in range(n):
        while st and a[st[-1]] >= a[i]:
            st.pop()
        prev_less[i] = st[-1] if st else -1
        st.append(i)
    st = []
    for i in range(n - 1, -1, -1):
        while st and a[st[-1]] > a[i]:
            st.pop()
        next_le[i] = st[-1] if st else n
        st.append(i)
    total = 0
    for i in range(n):
        left = i - prev_less[i]
        right = next_le[i] - i
        total += a[i] * left * right
    return total % MOD

দুটো O(n) stack pass + একটা O(n) যোগ — মোট O(n)। O(n²) থেকে নেমে এল।

10. Thinking tweak

দুটো "আহা!" মুহূর্ত এখানে।

প্রথম: 76-এর contribution-কে শর্তযুক্ত করো — "সব subarray"-র জায়গায় "যেখানে আমি minimum"। count বদলে (i+1)*(n-i) থেকে left * right হয়, যেখানে span দুই দিকের nearest-smaller পর্যন্ত।

দ্বিতীয় (সবচেয়ে সূক্ষ্ম): tie ভাঙো asymmetry দিয়ে — এক পাশে strict (<), অন্য পাশে non-strict (≤)। সমান মানের element থাকলে, এই asymmetry নিশ্চিত করে প্রতিটা subarray-র min ঠিক একটা index-এ গোনা হয় (দুবার নয়, শূন্যবার নয়)। এই একটা সিদ্ধান্তই tie-bug-এর রক্ষাকবচ। (span বের করার যন্ত্র monotonic stack — stack folder-এর Next Greater Element-এরই আত্মীয়।)

11. Step-by-step dry run

a = [3, 1, 2, 4]। প্রথমে previous-strictly-smaller (prev_less) আর next-smaller-or-equal (next_le):

prev_less = [-1, -1, 1, 2]     (index 0: বাঁয়ে ছোট নেই; index 2: বাঁয়ে ছোট index 1)
next_le   = [ 1,  4, 4, 4]     (index 0: ডানে ছোট/সমান index 1; বাকিদের শেষ পর্যন্ত নেই)

তারপর span আর অবদান:

i	a[i]	prev_less	next_le	left = i−prev_less	right = next_le−i	অবদান a[i]·left·right
0	3	-1	1	1	1	3
1	1	-1	4	2	3	6
2	2	1	4	1	2	4
3	4	2	4	1	1	4

মোট = 3 + 6 + 4 + 4 = 17 ✓। element 1 সবচেয়ে ছোট, তাই সবচেয়ে বড় span (2×3=6) আর বড় অবদান।

12. Python solution

def sum_subarray_mins(a):
    """সব subarray-র minimum-এর যোগফল (mod 1e9+7); contribution + monotonic stack, O(n)।
    span: এক পাশে strictly-smaller, অন্য পাশে smaller-or-equal — tie ঠিক একবার গোনে।"""
    MOD = 10**9 + 7
    n = len(a)
    prev_less = [-1] * n         # previous strictly-smaller index
    next_le = [n] * n           # next smaller-or-equal index
    st = []
    for i in range(n):
        while st and a[st[-1]] >= a[i]:
            st.pop()
        prev_less[i] = st[-1] if st else -1
        st.append(i)
    st = []
    for i in range(n - 1, -1, -1):
        while st and a[st[-1]] > a[i]:
            st.pop()
        next_le[i] = st[-1] if st else n
        st.append(i)
    total = 0
    for i in range(n):
        left = i - prev_less[i]
        right = next_le[i] - i
        total += a[i] * left * right
    return total % MOD


def sum_subarray_mins_brute(a):
    """ধীর O(n^2) version — প্রতি subarray-র min যোগ; মিলিয়ে দেখার জন্য।"""
    MOD = 10**9 + 7
    n = len(a)
    total = 0
    for l in range(n):
        m = a[l]
        for r in range(l, n):
            m = min(m, a[r])
            total += m
    return total % MOD


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert sum_subarray_mins([3, 1, 2, 4]) == 17
assert sum_subarray_mins([11, 81, 94, 43, 3]) == 444   # LeetCode example
assert sum_subarray_mins([1, 2, 3, 4]) == 20
assert sum_subarray_mins([4, 3, 2, 1]) == 20
assert sum_subarray_mins([2, 2, 2]) == 12              # tie — সাবধানে
assert sum_subarray_mins([1, 3, 1, 3, 1]) == 19        # একই মান বারবার
assert sum_subarray_mins([7]) == 7

# fast আর brute একই উত্তর কিনা (random brute-force cross-check, tie সহ):
import random
random.seed(29)
for _ in range(500):
    arr = [random.randint(1, 6) for _ in range(random.randint(1, 12))]  # ছোট রেঞ্জ = বহু tie
    assert sum_subarray_mins(arr) == sum_subarray_mins_brute(arr)

print(sum_subarray_mins([3, 1, 2, 4]))          # 17
print(sum_subarray_mins([11, 81, 94, 43, 3]))   # 444
print("সব test pass!")

13. Line-by-line explanation

while st and a[st[-1]] >= a[i]:
    st.pop()
prev_less[i] = st[-1] if st else -1
st.append(i)

বাঁ থেকে ডান pass — previous strictly-smaller খোঁজা। stack-এ index রাখি যাদের মান বাড়ন্ত; a[i]-এর চেয়ে বড়-বা-সমান সব pop (তাই বাকি থাকে কঠোরভাবে ছোট)। stack-এর top-ই previous-smaller, নাহলে -1।

while st and a[st[-1]] > a[i]:
    st.pop()
next_le[i] = st[-1] if st else n

ডান থেকে বাঁ pass — next smaller-or-equal খোঁজা। এখানে শুধু কঠোরভাবে বড় pop (>), তাই সমান element থেমে যায় — এই asymmetry-ই (এক পাশে >=, অন্য পাশে >) tie একবার গোনা নিশ্চিত করে।

left = i - prev_less[i]
right = next_le[i] - i
total += a[i] * left * right

span: বাঁয়ে left রকম শুরু, ডানে right রকম শেষ। গুণ = a[i] কয়টা subarray-তে min; মান দিয়ে গুণ করে অবদান জমাই।

বাকি assert গুলো নির্দিষ্ট উদাহরণ + ছোট-রেঞ্জ random array (বহু tie) তে fast আর brute মিলিয়ে দেখছে (brute-force cross-check) — tie-handling ঠিক কিনা এখানেই যাচাই। সব মিললে সব test pass!।

14. Output walkthrough

a = [3, 1, 2, 4]:

• prev_less = [-1, -1, 1, 2], next_le = [1, 4, 4, 4]
• অবদান: 3, 6, 4, 4
• মোট 17 → প্রথম print
• [11, 81, 94, 43, 3] → 444 → দ্বিতীয় print
• সব assert (tie সহ) pass → সব test pass!

ছাপা output:

17
444
সব test pass!

15. Time complexity

O(n) — দুটো stack pass, প্রতিটায় প্রতিটা index ঠিক একবার push আর সর্বোচ্চ একবার pop (amortized O(1) per element), তারপর একটা O(n) যোগ। brute force-এর O(n²) থেকে বিশাল উন্নতি।

16. Space complexity

O(n) — prev_less, next_le দুটো array আর stack (সর্বোচ্চ n element)। সবই O(n)।

17. Common mistakes

1. দুই পাশেই একই কঠোরতা (< বা ≤) ব্যবহার — সমান মান থাকলে subarray দুবার গোনা বা বাদ পড়ে। এক পাশে strict, অন্য পাশে non-strict — এটাই tie-এর #1 bug-রক্ষা।
2. mod নিতে ভুলে যাওয়া — যোগফল বিশাল হতে পারে; % (10^9 + 7) দিতে হবে (অন্য ভাষায় overflow-ও)।
3. span গণনায় off-by-one — left = i - prev_less[i], right = next_le[i] - i; prev_less/next_le-এর sentinel (-1 আর n) এই দূরত্ব ঠিক রাখে।
4. prev/next-smaller আর prev/next-greater গুলিয়ে ফেলা — minimum-এর জন্য smaller লাগে; maximum-এর problem-এ greater (sign উল্টো)।
5. brute-এ min প্রতিবার গোড়া থেকে বের করা — running min না রাখলে brute O(n³); যাই হোক, বড় input-এ stack version ব্যবহার করো।

18. Harder problems that inherit this idea

• LeetCode — Sum of Subarray Minimums (https://leetcode.com/problems/sum-of-subarray-minimums/) — ঠিক এই problem।
• LeetCode — Sum of Subarray Ranges (https://leetcode.com/problems/sum-of-subarray-ranges/) — max-contribution − min-contribution; এই কৌশলের যুগল প্রয়োগ।
• LeetCode — Largest Rectangle in Histogram (https://leetcode.com/problems/largest-rectangle-in-histogram/) — একই previous/next-smaller span, ভিন্ন প্রয়োগ (stack folder-এ আছে)।
• span-এর গভীরে → ../../04-stack-and-queue/ (Next Greater Element, monotonic stack)।

19. Pattern learned

Contribution + nearest-smaller spans (monotonic stack) — প্রতিটা element কয়টা subarray-তে min = left * right (prev/next smaller পর্যন্ত), tie ভাঙো asymmetric strict/non-strict দিয়ে। বড় শিক্ষা: "sum over all subarrays of f(min/max)" ঘরানায় — প্রতি subarray না ঘুরে প্রতিটা element কোথায় কোথায় min/max সেই span গোনো; span-এর যন্ত্র monotonic stack।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "sum of subarray minimums = Σ a[i] * left[i] * right[i] (left=prev-smaller span, right=next-smaller span, monotonic stack-এ O(n))। tie ভাঙতে এক পাশে <, অন্য পাশে ≤। mod নিতে ভুলো না।"

পরের ধাপ → 079 — Imos Method Basic (difference-চিন্তা event-এর জগতে)। সম্পর্কিত → 076 — Sum of All Subarrays।

ফিরে দেখা: শিকড় → 076 — Sum of All Subarrays · span-এর যন্ত্র → ../../04-stack-and-queue/ · এই level-এর map → ../README.md · concept ঝালাই → ../concept-notes.md · template → ../../../templates/math-problem-note-template.md।

---

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