087 — Minimum Size Subarray Sum

086-এ খুঁজেছিলে সবচেয়ে লম্বা window যার sum ঠিক k। এখানে উল্টো দিক — সবচেয়ে ছোট window যার sum অন্তত target (≥, ঠিক নয়)। একই শুঁয়োপোকা, কিন্তু লক্ষ্য বদলেছে: যত তাড়াতাড়ি target ছোঁয়, তত আক্রমণাত্মকভাবে লেজ গুটিয়ে ছোট কর। longest আর shortest — দুই দিকের অনুশীলন একসাথে হয়ে গেলে variable window হাতে এসে যায়। ধীরে পড়ো।

Source

• Original source: LeetCode Minimum Size Subarray Sum
• Platform: LeetCode — https://leetcode.com/problems/minimum-size-subarray-sum/
• Topic: Sliding window → shrinkable window (minimize length)
• Difficulty: Medium
• Pattern: shrinkable window (যত পারো লেজ গুটাও)
• Basic idea inherited from: 086 — Longest Subarray with Sum K (একই grow/shrink, তবে লক্ষ্য shortest)

1. Problem in simple words

একটা positive সংখ্যার array a আর একটা target দেওয়া। এমন সবচেয়ে ছোট পরপর subarray-র দৈর্ঘ্য বের করো যার যোগফল >= target। এমন subarray না থাকলে 0।

লক্ষ করো — এবার "ঠিক target" নয়, "target বা তার বেশি"। তাই sum target ছুঁলেই থামি না; বরং যত পারি ছোট করি, sum যতক্ষণ ≥ target থাকে।

2. What is the math idea?

মূল idea আবারো monotonic window (positive সংখ্যা)। কিন্তু এবার শর্তটা >=:

• ডানে যোগ করলে sum বাড়ে → target ছোঁয়ার সম্ভাবনা বাড়ে
• বাঁ থেকে বাদ দিলে sum কমে → window ছোট হয়, কিন্তু ≥ target ধরে রাখতে হয়

target ছোঁয়ার পর আমরা আক্রমণাত্মকভাবে লেজ গুটাই — যতক্ষণ sum ≥ target থাকে, তত ছোট করি; প্রতিটা মুহূর্তে দৈর্ঘ্য মেপে সবচেয়ে ছোটটা রাখি।

3. Which basic idea does this inherit from?

086 — Longest Subarray with Sum K-এর কাঁধে — হুবহু একই grow/shrink কাঠামো। পার্থক্য শুধু লক্ষ্য আর shrink-এর শর্ত:

• 086: sum ঠিক k; shrink করি যখন sum > k (বেশি হয়ে গেলে কমাই); সবচেয়ে লম্বা চাই
• 087: sum >= target; shrink করি যখন sum >= target (ছুঁলেই ছোট করি); সবচেয়ে ছোট চাই

কাঠামো এক, কিন্তু "কখন shrink, আর কোন দৈর্ঘ্য রাখি" বদলে যায়। 086 (longest) আর 087 (shortest) পাশাপাশি পড়লে variable window-র দুই মুখই চেনা হয়ে যায়।

4. Real-life analogy

ভাবো তুমি কম পয়সায় ঠিক target ক্যালরি খেতে চাও — কিন্তু চাও যত কম পদ (subarray যত ছোট) তত ভালো। তুমি পরপর পদ যোগ করতে থাকো (মাথা বাড়াও); যেই ক্যালরি target ছুঁল, এবার পেছন থেকে পদ বাদ দিতে থাকো — যতক্ষণ ক্যালরি ≥ target থাকে।

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

5. Visual explanation

a = [2, 3, 1, 2, 4, 3], target = 7 — শুঁয়োপোকা যত পারে ছোট হয়:

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

r=0..3: [2 3 1 2]            sum=8 ≥7 → দৈর্ঘ্য 4; লেজ গুটাও −2 → [3 1 2] sum=6 <7 থামো (best=4)
r=4:    [3 1 2 4]            sum=10 ≥7 → দৈর্ঘ্য 4; −3 → [1 2 4] sum=7 ≥7 দৈর্ঘ্য 3 (best=3); −1 → [2 4] sum=6<7 থামো
r=5:    [2 4 3]              sum=9 ≥7 → দৈর্ঘ্য 3; −2 → [4 3] sum=7 ≥7 দৈর্ঘ্য 2 (best=2)! −4 → [3] sum=3<7 থামো
                            সবচেয়ে ছোট দৈর্ঘ্য = 2  ([4, 3])

লক্ষ — target ছুঁলেই থামিনি; ≥ থাকা পর্যন্ত যত পেরেছি ছোট করেছি:

[====r]        ≥ target ছুঁল
  [==r]        লেজ গুটিয়ে আরো ছোট, এখনো ≥
    [r]        আর গুটালে < target → থামো, এই দৈর্ঘ্যটা ধরো

6. Example input and output

a                       target  ->  min length  (কোন subarray)
--------------------------------------------------------------
[2, 3, 1, 2, 4, 3]      7       ->  2           [4, 3]
[1, 1, 1, 1, 1, 1, 1]   11      ->  0           মোট sum 7 < 11
[1, 2, 3, 4, 5]         11      ->  3           [3, 4, 5]
[1, 4, 4]               4       ->  1           [4]
[5]                     5       ->  1           [5]
[1, 2, 3]               7       ->  0           মোট 6 < 7

Edge case: পুরো array-র sum < target হলে 0; একটা element-ই ≥ target হলে দৈর্ঘ্য 1; positive ধরা।

7. Brute force thinking

সরল পথ — প্রতিটা শুরু থেকে যোগ করতে করতে কখন target ছোঁয় দেখা:

def min_subarray_brute(a, target):
    n = len(a)
    best = float('inf')
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += a[j]
            if s >= target:
                best = min(best, j - i + 1)
                break              # আর বাড়ালে শুধু লম্বা হবে
    return 0 if best == float('inf') else best

ঠিক উত্তর দেয় — প্রতিটা শুরু থেকে যত তাড়াতাড়ি target ছোঁয় সেই দৈর্ঘ্য নিয়ে সবচেয়ে ছোটটা রাখে।

8. Why brute force may be slow

দুটো nested loop — সবচেয়ে খারাপ ক্ষেত্রে প্রায় n²/2। n = 100000 হলে প্রায় ৫০০ কোটি — Time Limit Exceeded।

n = 100000 হলে:
  brute force   : ~5,000,000,000 step      (O(n²))
  sliding window: বড়জোর ~200000 move        (O(n))

মূল অপচয়: positive বলে sum monotonic, একটা চলন্ত window-ই যথেষ্ট — তবু brute force প্রতিটা শুরু থেকে নতুন করে শুরু করছে।

9. Better thinking

মূল insight: একটা চলন্ত window রাখো; target ছুঁলে যত পারো বাঁ থেকে গুটিয়ে ছোট করো।

l = 0, s = 0, best = inf
for r in range(n):
    s += a[r]                     # মাথা এগোলো
    while s >= target:            # ছুঁয়েছে → যত পারো ছোট করো
        best = min(best, r - l + 1)
        s -= a[l]; l += 1
return 0 if best == inf else best

খেয়াল করো — দৈর্ঘ্য মাপা হয় while-এর ভেতরে, কারণ shrink করতে করতে ছোট থেকে ছোট দৈর্ঘ্য পাওয়া যায়।

10. Thinking tweak

আসল "আহা!": target ছুঁলেই থেমো না — ≥ থাকা পর্যন্ত বাঁ থেকে গুটাতে থাকো, প্রতিটা ছোট দৈর্ঘ্য মেপে নাও; ঠিক যেখানে < হয়ে যাবে, সেটাই এই মুহূর্তের সীমা।

086-এর সাথে তফাত: ওখানে দৈর্ঘ্য মাপতাম shrink-এর পরে (sum == k হলে), এখানে মাপি shrink-এর ভেতরে (≥ থাকতেই)। লক্ষ্য longest না shortest — তাই মাপার জায়গাটাই বদলে যায়। এই সূক্ষ্ম তফাতটাই দুই problem-এর আসল শিক্ষা।

11. Step-by-step dry run

a = [2, 3, 1, 2, 4, 3], target = 7। l=0, s=0, best=inf:

r	a[r]	s (যোগের পর)	while s≥7: দৈর্ঘ্য মাপি, বাঁ বের	s, l পরে	best
0	2	2	—	s=2, l=0	inf
1	3	5	—	s=5, l=0	inf
2	1	6	—	s=6, l=0	inf
3	2	8	দৈর্ঘ্য 4(l=0); −2,l=1 → s=6<7 থামো	s=6, l=1	4
4	4	10	দৈর্ঘ্য 4(l=1); −3,l=2 → s=7; দৈর্ঘ্য 3(l=2); −1,l=3 → s=6<7	s=6, l=3	3
5	3	9	দৈর্ঘ্য 3(l=3); −2,l=4 → s=7; দৈর্ঘ্য 2(l=4); −4,l=5 → s=3<7	s=3, l=5	2

সবচেয়ে ছোট দৈর্ঘ্য 2 ([4, 3])। লক্ষ করো r=5-এ দুবার দৈর্ঘ্য মাপলাম (3, তারপর 2) — ভেতরে মাপি বলেই ছোটটা ধরা পড়ল।

12. Python solution

def min_subarray_len(a, target):
    """positive array a-তে sum >= target এমন সবচেয়ে ছোট subarray-র দৈর্ঘ্য (না থাকলে 0)।"""
    l = 0
    s = 0
    best = float('inf')
    for r in range(len(a)):
        s += a[r]                       # মাথা এগোলো
        while s >= target:              # ছুঁয়েছে → যত পারো ছোট করো
            length = r - l + 1
            if length < best:
                best = length
            s -= a[l]                   # লেজ গুটাও
            l += 1
    return 0 if best == float('inf') else best


def min_subarray_brute(a, target):
    """ধীর reference — প্রতিটা শুরু থেকে যোগ করে যত তাড়াতাড়ি target ছোঁয়।"""
    n = len(a)
    best = float('inf')
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += a[j]
            if s >= target:
                best = min(best, j - i + 1)
                break
    return 0 if best == float('inf') else best


# --- ছোট test গুলো (সব pass করা উচিত) ---
assert min_subarray_len([2, 3, 1, 2, 4, 3], 7) == 2
assert min_subarray_len([1, 1, 1, 1, 1, 1, 1], 11) == 0
assert min_subarray_len([1, 2, 3, 4, 5], 11) == 3
assert min_subarray_len([1, 4, 4], 4) == 1
assert min_subarray_len([5], 5) == 1
assert min_subarray_len([1, 2, 3], 7) == 0
assert min_subarray_len([], 1) == 0

# brute force-এর সাথে মিলিয়ে দেখা (positive array, নানা random case)
import random
random.seed(23)
for _ in range(500):
    n = random.randint(0, 12)
    arr = [random.randint(1, 6) for _ in range(n)]   # সব positive
    tgt = random.randint(1, 25)
    assert min_subarray_len(arr, tgt) == min_subarray_brute(arr, tgt), (arr, tgt)

print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))      # 2
print(min_subarray_len([1, 2, 3, 4, 5], 11))        # 3
print(min_subarray_len([1, 2, 3], 7))               # 0
print("সব test pass!")

13. Line-by-line explanation

l = 0 ; s = 0 ; best = float('inf')

l লেজ, s window-র sum, best শুরুতে অসীম (এখনো কিছু পাইনি)।

for r in range(len(a)):
    s += a[r]

r মাথা — নতুন element ঢুকিয়ে window বড়।

    while s >= target:
        length = r - l + 1 ; best = min(best, length)
        s -= a[l] ; l += 1

হৃদয় — sum target ছুঁলে দৈর্ঘ্য মেপে (while-এর ভেতরে), তারপর বাঁ থেকে বের করে আরো ছোট করার চেষ্টা; positive বলে একসময় sum < target হয়ে while থামে।

return 0 if best == float('inf') else best

কখনো target না ছুঁলে best অসীমই থাকবে → 0।

min_subarray_brute test যাচাইয়ের reference; random positive case-এ দুই পথ মিলিয়ে দেখা হয়।

14. Output walkthrough

চালালে ছাপবে:

2
3
0
সব test pass!

প্রথম লাইন [4,3]-এর দৈর্ঘ্য 2; দ্বিতীয় লাইন [3,4,5]-এর দৈর্ঘ্য 3 (sum 12 ≥ 11); তৃতীয় লাইন মোট sum 6 < 7 → 0। তার আগে 500 random positive case brute-force-এর সাথে মিলেছে, তাই সব test pass!।

15. Time complexity

O(n) — r মোট n বার, l-ও বড়জোর n বার (পিছায় না); ভেতরের while মিলিয়ে মোট move ≤ 2n। amortized O(n)।

16. Space complexity

O(1) — শুধু l, s, best, length; বাড়তি array নেই।

17. Common mistakes

• দৈর্ঘ্য while-এর বাইরে মাপা — তাহলে সবচেয়ে ছোট window ধরা পড়ে না; shortest-এ মাপতে হয় shrink-এর ভেতরে।
• shrink-এর শর্ত > লেখা — এখানে >= target (ছুঁলেই ছোট করি); > দিলে ঠিক target-এ থেমে যায়, ছোট করা মিস।
• best না পেলে 0 ফেরত না দেওয়া — inf রয়ে গেলে ভুল; না পেলে 0।
• Negative number-এ চালানো — monotonicity ভাঙে; positive ছাড়া এই পথ অবৈধ।
• 086-এর সাথে গুলিয়ে ফেলা — ওটা "ঠিক k + longest", এটা "≥ target + shortest"; শর্ত ও মাপার জায়গা আলাদা।

18. Harder problems that inherit this idea

• LeetCode Minimum Size Subarray Sum (https://leetcode.com/problems/minimum-size-subarray-sum/) — এই problem-এরই মূল রূপ।
• LeetCode Minimum Window Substring (https://leetcode.com/problems/minimum-window-substring/) — একই shrinkable window, তবে শর্ত "সব দরকারি অক্ষর ঢুকেছে"।
• LeetCode Subarray Product Less Than K (https://leetcode.com/problems/subarray-product-less-than-k/) — যোগের বদলে গুণ, গোনার নিয়ম r−l+1 (090)।

19. Pattern learned

Shrinkable sliding window (minimize length) — r বাড়াও; s >= target হলে while-এর ভেতরে দৈর্ঘ্য মেপে l গুটাও। বড় শিক্ষা: longest চাইলে shrink-এর পরে মাপো, shortest চাইলে shrink-এর ভেতরে মাপো — লক্ষ্যই মাপার জায়গা ঠিক করে।

20. Final summary

ভবিষ্যতের আমাকে এক লাইনে: "positive array + 'sum ≥ target, সবচেয়ে ছোট' = shrinkable window; r বাড়াও, ≥ হলে while-এর ভেতরে দৈর্ঘ্য মেপে l গুটাও। Signal: 'shortest/minimum length subarray' দেখলে shrink-এর ভেতরে মাপা মনে পড়ুক।"

পরের ধাপ → 090 — Number of Subarrays with Product Less Than K (গোনার নিয়ম r−l+1)। ভিত্তি → 086 — Longest Subarray with Sum K।

ফিরে দেখা: এই level-এর map → ../README.md · এই note-টা যে ছকে লেখা → ../../../templates/math-problem-note-template.md।

21. JavaScript solution (with test cases)

shrinkable window — sum ≥ target হলে while-এর ভেতরে দৈর্ঘ্য মেপে বাঁ গুটাও।

const assert = (cond, msg = "") => { if (!cond) throw new Error("FAIL " + msg); };
// smallest subarray length with sum >= target (0 if none), positive array
function minSubarrayLen(a, target) {
  let l = 0, s = 0, best = Infinity;
  for (let r = 0; r < a.length; r++) {
    s += a[r];                         // মাথা এগোলো
    while (s >= target) {               // ছুঁয়েছে -> যত পারো ছোট করো
      best = Math.min(best, r - l + 1);
      s -= a[l];                        // লেজ গুটাও
      l++;
    }
  }
  return best === Infinity ? 0 : best;
}
// ---- test cases (example + edge) ----
assert(minSubarrayLen([2, 3, 1, 2, 4, 3], 7) === 2, "classic");          // [4,3]
assert(minSubarrayLen([1, 1, 1, 1, 1, 1, 1], 11) === 0, "unreachable");  // edge
assert(minSubarrayLen([1, 2, 3, 4, 5], 11) === 3, "mid");
assert(minSubarrayLen([1, 4, 4], 4) === 1, "single-elem");
assert(minSubarrayLen([5], 5) === 1, "one");
assert(minSubarrayLen([], 1) === 0, "empty");                            // edge
console.log("সব JS test pass!");

JS টীকা: "এখনো পাইনি" বোঝাতে Infinity ব্যবহার করো (Python-এর float('inf')-এর সমতুল্য), শেষে না-পেলে 0। দৈর্ঘ্য অবশ্যই while-এর ভেতরে মাপো — shrink করতে করতেই সবচেয়ে ছোটটা ধরা পড়ে।

22. TypeScript solution (with test cases)

function minSubarrayLen(a: number[], target: number): number {
  let l = 0, s = 0;
  let best: number = Infinity;
  for (let r = 0; r < a.length; r++) {
    s += a[r];
    while (s >= target) {
      best = Math.min(best, r - l + 1);
      s -= a[l];
      l++;
    }
  }
  return best === Infinity ? 0 : best;
}
function expect<T>(actual: T, exp: T, msg = ""): void {
  if (actual !== exp) throw new Error(`FAIL ${msg}: got ${actual}`);
}
expect(minSubarrayLen([2, 3, 1, 2, 4, 3], 7), 2, "classic");
expect(minSubarrayLen([1, 1, 1, 1, 1, 1, 1], 11), 0, "unreachable");
expect(minSubarrayLen([5], 5), 1, "one");
console.log("সব TS test pass!");

TS টীকা: best: number annotate করায় Infinity-ও number হিসেবেই থাকে; parameter number[]/number দেওয়ায় ভুল input type compile-time-এ আটকায়, shrinkable-window invariant সুরক্ষিত।

23. কোথায় কাজে লাগে (real-world use)

• Bandwidth/SLA: নির্দিষ্ট থ্রেশহোল্ড (≥ target) ছোঁয়া সবচেয়ে ছোট সময়-উইন্ডো বের করা।
• Streaming/buffering: ন্যূনতম যত data দরকার target পূরণে — সবচেয়ে ছোট contiguous chunk।
• Finance: সবচেয়ে কম দিনে নির্দিষ্ট cumulative return ছোঁয়ার window।
• Sensor alerts: সবচেয়ে ছোট টানা পর্ব যেখানে aggregate reading সীমা পেরোয়।
• Load testing: ন্যূনতম request-burst যা নির্দিষ্ট throughput তৈরি করে।
• Resource allocation: target capacity ছোঁয়া সবচেয়ে ছোট টানা slot-সেট।

মূল pattern: r বাড়াও, ≥ হলে while-এর ভেতরে দৈর্ঘ্য মেপে l গুটাও (longest হলে shrink-এর পরে, shortest হলে ভেতরে) — "minimum length subarray" দেখলেই shrinkable window।

---

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