017 — Sum of Subarray Minimums

Problem link ও উৎস

• 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 যোগ করো

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

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

তোমাকে একটা সংখ্যার 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

Input ও 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

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

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

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

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

এটা 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 দিয়ে মাপা যায়।

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

লুকানো 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 হয় না।

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

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

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

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

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

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

সবচেয়ে সরল চিন্তা: প্রতিটা শুরু 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

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

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

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

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

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

দুটো 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 যোগ করো।

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

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

ছবিতে বোঝা

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

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

Input [3, 1, 2, 4]:

1. 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]
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]
3. 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
4. 17 % (10**9+7) = 17 → return 17

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

Python

Python

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

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

• 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 করে।

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

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

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

সময়

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

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

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

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

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

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

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

ভিত্তি: 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 নয় — পরিসরের গুণফল।

পরের অনুশীলন

• 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/

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

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

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

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