023 — Shortest Subarray with Sum at Least K¶

Source¶

Original source: Classic monotonic-deque-on-prefix-sums exercise
Platform: LeetCode — https://leetcode.com/problems/shortest-subarray-with-sum-at-least-k/
Topic: queue (monotonic deque) + prefix sums
Difficulty: Hard
Pattern: monotonic deque on prefix sums
Basic idea inherited from: Problem 19-এর deque + math level 5-এর prefix sums — subarray-র যোগফলকে দুটো prefix-এর পার্থক্য বানিয়ে deque দিয়ে অপ্টিমাইজ করা

1. Problem in simple words¶

তোমাকে একটা পূর্ণসংখ্যার array nums (ঋণাত্মক সংখ্যাও থাকতে পারে) আর একটা সংখ্যা k দেওয়া আছে। এমন সবচেয়ে ছোট দৈর্ঘ্যের contiguous subarray খুঁজতে হবে যার যোগফল অন্তত k (মানে >= k)। তেমন subarray না থাকলে -1 ফেরত দাও।

nums=[2,-1,2], k=3  -> 3   (পুরো [2,-1,2]=3, এর চেয়ে ছোট কিছু >=3 হয় না)
nums=[1],     k=1   -> 1
nums=[1,2],   k=4   -> -1  (কোনো subarray-র যোগ 4 ছোঁয় না)

ঋণাত্মক সংখ্যা থাকায় এটা সাধারণ "all-positive sliding window" দিয়ে হয় না — সেখানেই আসল চ্যালেঞ্জ।

2. Which basic idea does this inherit from?¶

দুটো জিনিসের মিলন। প্রথমত prefix sums (math level 5): subarray (i, j)-র যোগফল = prefix[j] - prefix[i], যেখানে prefix[t] হলো প্রথম t-টা element-এর যোগফল। দ্বিতীয়ত Problem 19-এর monotonic deque: prefix array-র উপর একটা increasing deque চালিয়ে আমরা প্রতিটা j-র জন্য দ্রুত খুঁজি — এমন সবচেয়ে কাছের বাঁ-দিকের i যাতে prefix[j] - prefix[i] >= k।

3. What is the hidden math or logic?¶

সমস্যাটা prefix-এ অনুবাদ করো: এমন i < j খোঁজো যাতে prefix[j] - prefix[i] >= k, আর j - i সবচেয়ে ছোট। অর্থাৎ একটা j ঠিক রেখে এমন i চাই যেটা (১) prefix[i] <= prefix[j] - k মানে, আর (২) j-এর যত কাছে সম্ভব।

deque-তে আমরা candidate index-দের রাখি, যাদের prefix মান increasing। দুটো নিয়ম এই invariant রক্ষা করে আর উত্তর দেয়:

Front থেকে answer: front-এর prefix[deque[0]] সবচেয়ে ছোট; যদি prefix[j] - prefix[deque[0]] >= k হয়, তবে এই জোড়া বৈধ — দৈর্ঘ্য j - deque[0] রেকর্ড করো, আর front-কে popleft করো (এই i আর কোনো বড় j-র জন্য ছোট উত্তর দেবে না, কারণ j শুধু বাড়বে)।
Back থেকে maintenance: নতুন prefix[j] যদি prefix[deque[-1]]-এর চেয়ে ছোট-বা-সমান হয়, তবে পুরোনো বড় back-টা চিরতরে useless — j একইসাথে নতুন (কাছে) আর ছোট (সহজে শর্ত মেটায়), তাই back pop করো।

4. Which data structure is needed?¶

একটা collections.deque যেটা prefix array-র index রাখে, আর সেই index-গুলোর prefix মান increasing। সাথে একটা prefix array (দৈর্ঘ্য n+1)। deque লাগে কারণ দুই প্রান্তেই O(1) দরকার — front-এ answer তুলে popleft, back-এ useless pop।

5. Why this data structure fits¶

প্রতিটা j-র জন্য আমরা চাই সবচেয়ে কাছের বৈধ i — front-এ ছোট prefix রাখলে সেটা সরাসরি পাওয়া যায়। আর back-এ বড় prefix রাখা অর্থহীন (নতুন ছোট prefix সবদিকে ভালো), তাই সেগুলো ছাঁটি। এই দুই-প্রান্তের ছাঁটাই deque ছাড়া সস্তায় হয় না; ফলে প্রতিটা index একবার push একবার pop → O(n)।

6. Real-life analogy¶

ভাবো তুমি পাহাড়ি পথে হাঁটছ, প্রতি বিন্দুতে তোমার উচ্চতা = prefix। তুমি চাও এমন একটা শুরুর বিন্দু থেকে এখন পর্যন্ত নামা/ওঠা যেখানে উচ্চতার পার্থক্য অন্তত k, আর পথটা যত ছোট সম্ভব। তুমি শুধু সেই পুরোনো বিন্দুগুলো মনে রাখো যেগুলো ক্রমশ নিচু (increasing prefix-এর উল্টো দিক থেকে দেখলে) — কারণ একটা নতুন বিন্দু যদি আগের কোনো বিন্দুর সমান বা নিচু হয় আর কাছেও হয়, তবে পুরোনো উঁচু-দূরের বিন্দুটা আর কোনো কাজে লাগবে না, ফেলে দাও।

7. Visual explanation¶

nums=[2,-1,2], k=3 → prefix=[0, 2, 1, 3] (দৈর্ঘ্য 4)। deque index রাখে, prefix মান increasing:

j  prefix[j]  front-check (>=k?)                 back-maintain            deque(idx)  best
0    0        deque খালি                          —                        [0]         inf
1    2        2-prefix[0]=2 >=3? না               prefix[0]=0<=2? রাখো     [0,1]       inf
2    1        1-prefix[0]=1 >=3? না               prefix[1]=2>1 pop ->[0]  [0,2]       inf
                                                  prefix[0]=0<=1? রাখো
3    3        3-prefix[0]=3 >=3? হ্যাঁ -> len=3-0=3, popleft  [2]
              3-prefix[2]=2 >=3? না               prefix[2]=1<=3? রাখো     [2,3]       3
উত্তর: best=3

8. Example input and output¶

Input : nums=[1], k=1                 -> 1
Input : nums=[1,2], k=4               -> -1
Input : nums=[2,-1,2], k=3            -> 3
Input : nums=[84,-37,32,40,95], k=167 -> 3

Edge case 1 (negative k, negative nums): [-1,-2], k=-3 -> 1
Edge case 2 (পুরোটা লাগে)              : [1,1,1], k=3  -> 3
Edge case 3 (প্রথম element-ই যথেষ্ট)    : [5,1,1], k=5  -> 1

9. Brute force thinking¶

সরল চিন্তা: প্রতিটা শুরু i-র জন্য ডান দিকে যোগ করতে করতে প্রথম যেখানে চলমান যোগ >= k, সেই দৈর্ঘ্য রেকর্ড করি (ওই i-র জন্য ওটাই সবচেয়ে ছোট), সবার মধ্যে সর্বনিম্নটা রাখি।

best = inf
for i in range(n):
    s = 0
    for j in range(i, n):
        s += nums[j]
        if s >= k:
            best = min(best, j - i + 1)
            break

10. Why brute force is slow¶

দুটো nested loop → O(n^2), n = 10^5 হলে প্রায় 10^10 step — অসম্ভব। ঋণাত্মক সংখ্যার কারণে সাধারণ two-pointer sliding window-ও খাটে না (window ছোট করলে যোগফল আবার বেড়ে যেতে পারে)। তাই prefix sums + monotonic deque দিয়ে O(n)-তে নামাই।

11. Key observation¶

দুটো observation। (১) subarray-যোগ = দুই prefix-এর পার্থক্য, তাই সমস্যাটা "এমন কাছের ছোট prefix খোঁজো" হয়ে যায়। (২) যদি একটা পুরোনো index-এর prefix কোনো নতুন index-এর prefix-এর চেয়ে বড়-বা-সমান হয়, তবে পুরোনোটা চিরতরে অকেজো — নতুনটা ছোট (শর্ত সহজে মেটায়) আর কাছে (দৈর্ঘ্য কম)। তাই deque-তে শুধু increasing prefix রাখাই যথেষ্ট।

12. Optimized intuition¶

prefix array বানাও (prefix[0]=0, prefix[t]=prefix[t-1]+nums[t-1])। একটা খালি deque নাও। প্রতিটা j (0 থেকে n) এর জন্য: প্রথমে front-check — যতক্ষণ deque খালি নয় আর prefix[j] - prefix[deque[0]] >= k, ততক্ষণ best আপডেট করে popleft করো। তারপর back-maintain — যতক্ষণ deque খালি নয় আর prefix[deque[-1]] >= prefix[j], ততক্ষণ pop করো। শেষে j push করো। best কখনো না বদলালে -1।

13. Thinking tweak¶

মোচড়: ঋণাত্মক সংখ্যায় "window বড়/ছোট করি" ভেবো না (ভেঙে পড়ে)। বরং সমস্যাটাকে prefix-এর জগতে নিয়ে যাও: প্রতিটা ডান-প্রান্ত j-র জন্য চাই একটা কাছের, যথেষ্ট-ছোট বাঁ-প্রান্ত prefix। তারপর deque দিয়ে দুটো জিনিস একসাথে করো — front থেকে বৈধ উত্তর তোলো, back থেকে চিরতরে-অকেজো বড় prefix ছাঁটো।

14. Step-by-step dry run¶

Input nums=[2,-1,2], k=3, তাই prefix=[0,2,1,3]:

j=0: deque খালি; back-maintain কিছু না; push 0 → [0]
j=1 (prefix 2): front 2-0=2 >= 3? না। back: prefix[0]=0 >= 2? না। push 1 → [0,1]
j=2 (prefix 1): front 1-0=1 >= 3? না। back: prefix[1]=2 >= 1? হ্যাঁ → pop → [0]; prefix[0]=0 >= 1? না। push 2 → [0,2]
j=3 (prefix 3): front 3-0=3 >= 3? হ্যাঁ → best=min(inf, 3-0)=3, popleft → [2]; front 3-prefix[2]=3-1=2 >= 3? না। back: prefix[2]=1 >= 3? না। push 3 → [2,3]
best=3 <= n → return 3

15. Python solution¶

from collections import deque

def shortest_subarray(nums, k):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]   # prefix[t] = প্রথম t element-এর যোগ

    dq = deque()                              # index into prefix; prefix মান increasing
    best = n + 1                              # "পাওয়া যায়নি" sentinel
    for j in range(n + 1):
        while dq and prefix[j] - prefix[dq[0]] >= k:
            best = min(best, j - dq.popleft())    # বৈধ window; front সবচেয়ে কাছের ছোট start
        while dq and prefix[dq[-1]] >= prefix[j]:
            dq.pop()                              # prefix[j] ছোট ও নতুন -> পুরোনো বড়রা useless
        dq.append(j)
    return best if best <= n else -1

# ---- tests ----
def brute(nums, k):                          # সরল O(n^2) reference
    n = len(nums)
    best = n + 1
    for i in range(n):
        s = 0
        for j in range(i, n):
            s += nums[j]
            if s >= k:
                best = min(best, j - i + 1)
                break
    return best if best <= n else -1

assert shortest_subarray([1], 1) == 1
assert shortest_subarray([1, 2], 4) == -1
assert shortest_subarray([2, -1, 2], 3) == 3
assert shortest_subarray([84, -37, 32, 40, 95], 167) == 3
assert shortest_subarray([-1, -2], -3) == 1                         # negative k ও nums
assert shortest_subarray([2, -1, 2], 3) == brute([2, -1, 2], 3)
assert shortest_subarray([84, -37, 32, 40, 95], 167) == brute([84, -37, 32, 40, 95], 167)
print("সব test pass!")

16. Line-by-line code explanation¶

prefix লুপ — prefix[t] = প্রথম t-টা element-এর যোগ; subarray-যোগ prefix[j]-prefix[i]।
dq = deque() — prefix-এর index রাখে; এদের prefix মান নিচ→উপর increasing।
best = n + 1 — "এখনো বৈধ subarray পাইনি"; বৈধ দৈর্ঘ্য কখনো n-এর বেশি হয় না, তাই n+1 নিরাপদ sentinel।
while dq and prefix[j] - prefix[dq[0]] >= k: — front-এর index দিয়ে subarray-যোগ >= k হলে এটা একটা বৈধ window; j - dq.popleft() দৈর্ঘ্য রেকর্ড করে front ফেলে দাও (এই start আর কোনো বড় j-তে ছোট উত্তর দেবে না)।
while dq and prefix[dq[-1]] >= prefix[j]: / dq.pop() — নতুন prefix ছোট-বা-সমান হলে পুরোনো বড় back-রা চিরতরে useless, ছাঁটো; এতে deque increasing থাকে।
dq.append(j) — current index candidate হিসেবে যোগ।
return best if best <= n else -1 — কোনো বৈধ window না পেলে -1।

17. Output walkthrough¶

shortest_subarray([2,-1,2], 3) → section 14-এর trace মতো j=3-এ front index 0 দিয়ে যোগ 3 >= 3, দৈর্ঘ্য 3, যা best। shortest_subarray([1,2], 4) → কোনো j-তেই front-check >= 4 হয় না, best থাকে n+1=3, তাই -1। brute reference-এর সাথেও মিলে যায়। সব assert pass করে শেষে print: সব test pass!।

18. Time complexity¶

O(n) — prefix বানাতে O(n); মূল loop-এ প্রতিটা index ঠিক একবার deque-তে push হয় আর বড়জোর একবার pop হয় (front বা back থেকে)। মোট deque operation ≤ 2(n+1)।

19. Space complexity¶

O(n) — prefix array O(n), আর deque-তে সবচেয়ে খারাপ ক্ষেত্রে O(n) index।

20. Common mistakes¶

সাধারণ two-pointer sliding window দিয়ে চেষ্টা করা — ঋণাত্মক সংখ্যায় window সঙ্কুচিত করলে যোগ আবার বাড়তে পারে, তাই ভুল; prefix + deque লাগে।
front-check আর back-maintain-এর ক্রম উল্টে দেওয়া — আগে front থেকে answer তোলা (পুরো deque ধরে), তারপর back ছাঁটা; ক্রম ভুল হলে কিছু উত্তর miss হতে পারে।
back-maintain-এ > বনাম >= — >= দিলে সমান prefix-ও সরে, ফলে front-এ সবচেয়ে কাছের সমান-prefix থাকে (ছোট দৈর্ঘ্য); > রাখলেও ভুল হয় না কিন্তু >= পরিষ্কার।
prefix array-র দৈর্ঘ্য n ধরা — n+1 লাগে (prefix[0]=0 সহ), নাহলে শুরু-থেকের subarray বাদ পড়ে।

21. Which basic problem this inherits from¶

ভিত্তি: Problem 19-এর monotonic deque + math level 5-এর prefix sums; chapter-এর ../patterns.md Pattern 5-এর variant। পার্থক্য — fixed window নয়, বরং prefix-এর উপর deque চালিয়ে variable-length shortest খোঁজা, আর element front (answer) ও back (useless) দুদিক থেকেই বেরোয়।

22. Similar harder problems¶

Sliding Window Maximum (fixed-window deque) — https://leetcode.com/problems/sliding-window-maximum/ (এই tracker-এর #19)
Constrained Subsequence Sum (deque-optimized DP) — https://leetcode.com/problems/constrained-subsequence-sum/
Maximum Sum Circular Subarray — https://leetcode.com/problems/maximum-sum-circular-subarray/

23. Pattern learned¶

Monotonic deque on prefix sums: "ঋণাত্মক সংখ্যা সহ subarray-যোগ অন্তত K, shortest/longest" দেখলে prefix array বানাও আর তার উপর increasing deque চালাও — front থেকে বৈধ window তুলে popleft, back থেকে বড় prefix ছাঁটো।

24. Final summary¶

ভবিষ্যতের আমাকে: shortest subarray sum>=K (negative allowed) = prefix + monotonic deque। prefix বানাও (n+1 লম্বা); প্রতি j-তে আগে front থেকে prefix[j]-prefix[front]>=k হলে দৈর্ঘ্য তুলে popleft, তারপর back থেকে prefix[back]>=prefix[j] হলে pop, শেষে push। না পেলে -1। two-pointer খাটে না (negative)। "subarray sum at least K, negatives" দেখলেই এই pattern।

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