Problem link ও উৎস
- **Original source:** LeetCode — Subarray Product Less Than K
- **Platform:** LeetCode —
- **Topic:** Math-based programming fundamentals → Level 6: Two Pointers ও Sliding Window
- **Difficulty:** Medium
- **Pattern:** window count r−l+1 (window-এ নতুন উপাদান জুড়ে কতগুলো নতুন subarray যোগ হলো গোনা)
- **Basic idea inherited from:** 087 — Minimum Size Subarray Sum
## প্রশ্ন ও উদাহরণ {#problem}
### সহজ করে প্রশ্ন {#1-problem-in-simple-words}
একটা array দেওয়া আছে যেখানে সব সংখ্যা **positive** (`nums[i] >= 1`), আর একটা সংখ্যা `k`। বলতে হবে — কতগুলো **contiguous subarray** (পরপর কয়েকটা উপাদান) আছে যাদের সব উপাদানের **গুণফল কড়াভাবে `k`-এর ছোট** (product `< k`)।
উদাহরণ: `nums = [10, 5, 2, 6]`, `k = 100`। এখানে `[10]`, `[5]`, `[2]`, `[6]`, `[10, 5]`, `[5, 2]`, `[2, 6]`, `[5, 2, 6]` — মোট 8টা subarray-র গুণফল 100-এর ছোট। `[10, 5, 2]`-এর গুণফল 100, কিন্তু আমাদের চাই **কড়াভাবে ছোট**, তাই 100 বাদ।
দুটো জিনিস গোড়াতেই মাথায় রাখো: সংখ্যাগুলো সব positive (এটাই window-কে কাজ করায়), আর `k <= 1` হলে উত্তর সবসময় 0 (কারণ সবচেয়ে ছোট গুণফলও অন্তত 1, সেটা 1-এর ছোট হতে পারে না)।
### Input ও output {#6-example-input-and-output}
```text
nums k output কেন
-----------------------------------------------------------
[10, 5, 2, 6] 100 8 উপরে দেখানো 8টা
[1, 2, 3] 0 0 k <= 1, কোনো product < 0 হতে পারে না
[1, 1, 1] 2 6 সব subarray-র product 1 < 2 (n*(n+1)/2 = 6)
[10, 9, 10, 4, 3] 19 6 [10],[9],[10],[4],[4,3],[3] — সব single + একটা জোড়া
[1] 1 0 product 1, কিন্তু < 1 চাই, তাই 0
[] 100 0 ফাঁকা array
```
মূল edge case দুটো: **`k <= 1` হলে সবসময় 0** (positive সংখ্যার গুণফল ≥ 1, কখনো 1-এর ছোট হয় না), আর **ফাঁকা array-তে 0**।
### চেনা উদাহরণে বোঝা {#4-real-life-analogy}
ভাবো তুমি একটা দোকানে ঢুকছ, হাতে 100 টাকা (`k`)। তুমি বাঁ থেকে ডানে সাজানো তাক ধরে ধরে জিনিস তুলছ, কিন্তু এখানে দাম **যোগ** হয় না, **গুণ** হয় (ধরো এক অদ্ভুত দোকান, যেখানে প্রতিটা জিনিস আগের মোটকে গুণ করে দেয়)।
তুমি ডান হাত (`r`) বাড়িয়ে নতুন জিনিস তুলছ। যদি মোট গুণফল 100 ছুঁয়ে ফেলে বা ছাড়িয়ে যায়, তুমি বাঁ হাত (`l`) দিয়ে সবচেয়ে পুরোনো জিনিসটা তাকে ফিরিয়ে রাখছ — যতক্ষণ না আবার বাজেটের ভেতরে আসো। প্রতিবার যখন তোমার ঝুড়ি বাজেটের ভেতরে, তুমি মনে মনে গোনো — "এই শেষ জিনিসটা রেখে আমি কত রকম ভাবে ঝুড়ি বানাতে পারতাম?" উত্তর: ঝুড়িতে যত জিনিস আছে, ঠিক ততগুলো (`r − l + 1`)। সব মিলিয়ে সেই গোনাই উত্তর।
## ভিত্তির ধারণা {#idea}
### আগের কোন ধারণাটি লাগবে {#3-which-basic-idea-does-this-inherit-from}
এটা সরাসরি দাঁড়িয়ে আছে **087 — Minimum Size Subarray Sum**-এর কাঁধে। সেখানে তুমি shrinkable window শিখেছিলে: `r` বাড়াও, invariant ভাঙলে while-loop-এ `l` গুটিয়ে আবার valid করো। এখানেও হুবহু সেই কাঠামো — শুধু invariant-টা "sum ≥ target" থেকে বদলে "product < k" হলো, আর shrink-এর শর্ত উল্টে গেল (087-এ valid হলে গুটাতাম, এখানে **invalid হলে** গুটাই)।
আসল নতুন জিনিস এখানে একটাই — দৈর্ঘ্য মাপার বদলে **গোনা** (`r − l + 1`)। এই গোনার ট্রিক 088 (at most K distinct)-এও ছায়া ফেলেছে, আর 089-এর "exactly K = atMost(K) − atMost(K−1)" চিন্তার সাথেও আত্মীয়। তাই 087-এ window নাড়ানো আর 088-এ গোনা — দুটো মিলে এই problem।
### ভেতরের অঙ্ক {#2-what-is-the-math-idea}
মূল গাণিতিক ভিত্তি — **positive সংখ্যার গুণফল monotonic**। window-এ ডান দিক থেকে আরেকটা সংখ্যা (≥ 1) জুড়লে গুণফল কখনো কমে না, শুধু বাড়ে বা সমান থাকে; বাঁ দিক থেকে একটা সংখ্যা সরালে গুণফল কখনো বাড়ে না। এই "একদিকে জুড়লে বাড়ে, একদিকে সরালে কমে" ধর্মটাই দুই pointer-কে নিরাপদে চালাতে দেয়।
দ্বিতীয় ভিত্তি — **গোনার সূত্র**। `r` যখন একটা নতুন উপাদান যোগ করল আর window `[l..r]` valid (product `< k`) হলো, তখন এই `r`-এ শেষ হওয়া যত subarray valid, তাদের সংখ্যা ঠিক `r − l + 1`। কারণ valid window-এর ভেতরের যেকোনো **suffix** (`[l..r]`, `[l+1..r]`, ..., `[r..r]`) নিজেও valid — ছোট window-এর গুণফল বড় window-এর গুণফলের চেয়ে কখনো বড় নয়।
## ধাপে ধাপে সমাধান {#walkthrough}
### প্রথম সরল উপায় {#7-brute-force-thinking}
সবচেয়ে সরল চিন্তা — প্রতিটা সম্ভব subarray ধরো, তার গুণফল হিসাব করো, `k`-এর ছোট হলে গোনায় যোগ করো। দুটো nested loop দিয়ে শুরু আর শেষ index বেছে নাও:
```python
def count_brute(nums, k):
n = len(nums)
count = 0
for i in range(n):
prod = 1
for j in range(i, n):
prod *= nums[j]
if prod < k:
count += 1
return count
```
এখানে ভেতরের loop-এ `prod` ধরে ধরে গুণ করছি (প্রতিবার নতুন করে পুরো subarray গুণ করছি না — সেটা হলে O(n³) হতো)। তাই এটা O(n²)। ঠিক উত্তর দেয়, ছোট input-এ চমৎকার — আমাদের asserts-এ এটাই reference হিসেবে কাজে লাগবে।
### কোথায় বেশি কাজ হতে পারে {#8-why-brute-force-may-be-slow}
সমস্যা হলো জোড়া `(i, j)`-এর সংখ্যা — n লম্বা array-তে প্রায় `n² / 2`। `n = 10000` হলে সেটা প্রায় 5 কোটি ধাপ, আর `n = 100000` হলে 500 কোটি — interview/contest-এ নিশ্চিত Time Limit Exceeded।
```text
n = 100000 হলে:
brute force: ~5,000,000,000 ধাপ (O(n^2), ধীর)
window : ~200,000 ধাপ (O(n), প্রতিটা index l আর r দিয়ে একবার করে ছোঁয়া)
```
মূল অপচয়টা চোখে পড়ে: `i` যখন এক ঘর ডানে সরে, আমরা আগের সব কাজ ফেলে আবার শূন্য থেকে গুণ শুরু করি। অথচ আগের গণনার অনেকটাই পুনর্ব্যবহার করা যেত — সেখানেই window-র সুযোগ।
### আরও ভালোভাবে ভাবা {#9-better-thinking}
মূল observation — সংখ্যাগুলো সব positive, তাই **গুণফল monotonic**: window বাড়লে product বাড়ে, কমালে কমে। তাই দুটো pointer যথেষ্ট। একটা চলন্ত window `[l..r]` রাখো যার গুণফল সবসময় `< k`:
```python
def count_window(nums, k):
if k <= 1:
return 0
prod = 1
l = 0
count = 0
for r in range(len(nums)):
prod *= nums[r] # ডান দিক বাড়ালাম
while prod >= k: # বড় হয়ে গেলে
prod //= nums[l] # বাঁ দিক গুটিয়ে ছোট করি
l += 1
count += r - l + 1 # এই r-এ শেষ হওয়া valid subarray-র সংখ্যা
return count
```
`l` আর `r` দুজনেই শুধু সামনে এগোয়, কখনো পিছায় না — তাই মোট কাজ O(n)। গোনার সূত্র `r − l + 1` এক ধাপে অনেকগুলো subarray গুনে নেয়।
### ভাবনার পরিবর্তন {#10-thinking-tweak}
আসল "আহা!" মুহূর্ত — **প্রতিটা subarray আলাদা করে গোনার দরকার নেই; প্রতি `r`-এর জন্য একবারে গুনে ফেলো।**
যখন window `[l..r]` valid, তখন `r`-এ শেষ হওয়া valid subarray গুলো হলো `[l..r], [l+1..r], ..., [r..r]` — এদের সংখ্যা ঠিক window-এর দৈর্ঘ্য, `r − l + 1`। কেন এরা সবাই valid? কারণ এদের প্রত্যেকে `[l..r]`-এর একটা suffix, আর positive সংখ্যা সরালে গুণফল কমেই — তাই সবার product `[l..r]`-এর product-এর `<=`, যা ইতিমধ্যে `< k`।
এই "শেষ-বিন্দু ধরে গোনা" tweak-টা মাথায় গেঁথে নাও — subarray গোনার অসংখ্য problem-এ ফিরবে (088, 089, এবং আরও অনেক)।
### ছবিতে বোঝা {#5-visual-explanation}
`nums = [10, 5, 2, 6]`, `k = 100`। window `[l..r]` ডানে এগোচ্ছে, product track হচ্ছে:
```text
index: 0 1 2 3
nums: 10 5 2 6
--------------------
r=0: [10] prod=10 < 100 -> নতুন subarray গোনা: r-l+1 = 0-0+1 = 1
l,r
(window: [10])
r=1: [10 5] prod=50 < 100 -> গোনা: 1-0+1 = 2
l r
(নতুন valid: [5], [10,5])
r=2: [10 5 2] prod=100 NOT < 100 -> shrink! l বাড়াও
l r prod /= 10 -> 10, l=1
[5 2] prod=10 < 100 -> গোনা: 2-1+1 = 2
l r (নতুন valid: [2], [5,2])
r=3: [5 2 6] prod=60 < 100 -> গোনা: 3-1+1 = 3
l r (নতুন valid: [6], [2,6], [5,2,6])
```
প্রতি ধাপের গোনা যোগ করো: 1 + 2 + 2 + 3 = **8**। লক্ষ করো — প্রতিবার আমরা শুধু "এই `r`-এ শেষ হওয়া" subarray গুনছি, তাই দুবার গোনা হয় না।
### ছোট input-এ ধাপে ধাপে {#11-step-by-step-dry-run}
`nums = [10, 5, 2, 6]`, `k = 100`। শুরুতে `prod = 1`, `l = 0`, `count = 0`:
| r | nums[r] | prod ×= nums[r] | while prod≥100? | shrink পরে prod, l | count += r−l+1 | মোট count |
| --- | --- | --- | --- | --- | --- | --- |
| 0 | 10 | 1×10 = 10 | না | prod=10, l=0 | 0−0+1 = 1 | 1 |
| 1 | 5 | 10×5 = 50 | না | prod=50, l=0 | 1−0+1 = 2 | 3 |
| 2 | 2 | 50×2 = 100 | হ্যাঁ → prod//=10 → 10, l=1 | prod=10, l=1 | 2−1+1 = 2 | 5 |
| 3 | 6 | 10×6 = 60 | না | prod=60, l=1 | 3−1+1 = 3 | 8 |
শেষ অবস্থা: `count = 8`। ঠিক brute force-এর সাথে মিলে গেল। লক্ষ করো r=2-এ shrink হওয়ায় l এক ধাপ এগোল, আর তার ফলে r=3-এ গোনাটা 4 না হয়ে 3 হলো — এটাই window-র সৌন্দর্য।
## কোড ও ব্যাখ্যা {#code}
### Python {#12-python-solution}
```python
def num_subarray_product_less_than_k(nums, k):
"""positive nums-এ product < k হওয়া contiguous subarray গোনে। O(n)।"""
if k <= 1: # গুণফল সবসময় >= 1, তাই < 1 অসম্ভব
return 0
prod = 1
left = 0
count = 0
for right in range(len(nums)):
prod *= nums[right] # window-এ ডান দিক জুড়লাম
while prod >= k: # বড় হয়ে গেলে বাঁ দিক গুটাই
prod //= nums[left]
left += 1
count += right - left + 1 # এই right-এ শেষ হওয়া valid subarray-র সংখ্যা
return count
def count_brute(nums, k):
"""O(n^2) reference — উত্তর মিলিয়ে দেখার জন্য।"""
n = len(nums)
count = 0
for i in range(n):
prod = 1
for j in range(i, n):
prod *= nums[j]
if prod < k:
count += 1
return count
# --- হাতে বাছা test ---
assert num_subarray_product_less_than_k([10, 5, 2, 6], 100) == 8
assert num_subarray_product_less_than_k([1, 2, 3], 0) == 0 # k <= 1
assert num_subarray_product_less_than_k([1, 1, 1], 2) == 6 # সব 6টা subarray
assert num_subarray_product_less_than_k([1], 1) == 0 # product 1, < 1 চাই
assert num_subarray_product_less_than_k([], 100) == 0 # ফাঁকা
assert num_subarray_product_less_than_k([10, 9, 10, 4, 3], 19) == 6
# --- brute force-এর সাথে cross-check (random, অনেক কেস) ---
import random
random.seed(7)
for _ in range(2000):
n = random.randint(0, 8)
arr = [random.randint(1, 6) for _ in range(n)]
k = random.randint(0, 50)
assert num_subarray_product_less_than_k(arr, k) == count_brute(arr, k), (arr, k)
print(num_subarray_product_less_than_k([10, 5, 2, 6], 100)) # 8
print(num_subarray_product_less_than_k([1, 1, 1], 2)) # 6
print("সব test pass!")
```
### কোডের প্রতিটি অংশ {#13-line-by-line-explanation}
```text
if k <= 1:
return 0
```
positive সংখ্যার গুণফল সবসময় কমপক্ষে 1। তাই `k` যদি 1 বা তার ছোট হয়, কোনো subarray-র product কখনো `< k` হতে পারে না — সরাসরি 0। (এই guard না থাকলে নিচের `while`-এ গণ্ডগোল হতো — empty window-এও `prod=1 >= k` হয়ে `left` array ছাড়িয়ে যেত।)
```text
prod = 1; left = 0; count = 0
```
`prod` = চলতি window-এর গুণফল (শূন্য উপাদানে 1, কারণ গুণের identity 1), `left` = window-এর বাঁ প্রান্ত, `count` = মোট valid subarray।
```text
prod *= nums[right]
```
`right` এক ধাপ ডানে গেল, নতুন উপাদান window-এ ঢুকল, গুণফল আপডেট।
```text
while prod >= k:
prod //= nums[left]; left += 1
```
window-এর গুণফল `k` ছুঁয়ে/ছাড়িয়ে গেলে আর valid নয় — তাই বাঁ দিক থেকে উপাদান সরাই (গুণফলকে সেই সংখ্যা দিয়ে ভাগ করি, কারণ সরানো মানে গুণফল থেকে তাকে বের করা), `left` এগোয়। সব positive বলে integer ভাগ `//` ঠিকঠাক উল্টো গুণ করে।
```text
count += right - left + 1
```
এখন `[left..right]` আবার valid। এই `right`-এ শেষ হওয়া valid subarray-র সংখ্যা = window-এর দৈর্ঘ্য = `right − left + 1`। এক ধাপে সব suffix গুনে নিলাম।
cross-check অংশে 2000টা random কেসে window আর brute force মিলিয়ে দেখা — মিললে তবেই `সব test pass!`।
### Output মিলিয়ে দেখা {#14-output-walkthrough}
চালালে যা ছাপবে:
```text
8
6
সব test pass!
```
প্রথম লাইন: `[10, 5, 2, 6]`, `k=100` → dry run-এ পাওয়া 8। দ্বিতীয়: `[1, 1, 1]`, `k=2` → সব 6টা subarray-র product 1 < 2, তাই 6 (= 3×4/2)। তার আগের সব `assert` (হাতে বাছা + 2000টা random cross-check) চুপচাপ pass করেছে। সবশেষে `সব test pass!` — সব মিলেছে।
## খরচ ও সাধারণ ভুল {#cost}
### সময় {#15-time-complexity}
**O(n)** — `right` array-র উপর একবার ঘোরে (n ধাপ)। `while`-এর ভেতরে `left` শুধু সামনে এগোয়, কখনো পিছায় না; পুরো run-এ `left` সব মিলিয়ে সর্বোচ্চ n ধাপ এগোতে পারে। তাই দুই pointer মিলে মোট কাজ 2n-এর মধ্যে — অর্থাৎ O(n)। (brute force-এর O(n²) থেকে বিশাল লাফ।)
### অতিরিক্ত জায়গা {#16-space-complexity}
**O(1)** — শুধু `prod`, `left`, `count` কয়টা variable। কোনো বাড়তি array, list বা hash map লাগছে না। input ছাড়া স্মৃতি প্রায় শূন্য।
### যে ভুলগুলো এড়াতে হবে {#17-common-mistakes}
1. **`k <= 1` guard ভুলে যাওয়া** — তাহলে empty window-এও `prod = 1 >= k` হয়ে `while`-এ `left` array ছাড়িয়ে index error দেবে। গোড়াতেই `return 0`।
2. **`<` আর `<=` গুলিয়ে ফেলা** — problem চায় product **কড়াভাবে ছোট** (`< k`)। `<=` লিখলে `[10,5,2]` (product 100) ভুল করে গোনা হবে।
3. **দৈর্ঘ্যের জায়গায় ভুল গোনা** — `r − l + 1`-এর বদলে শুধু 1 যোগ করলে (প্রতি r-এ একটা) উত্তর কম হবে; এটা subarray গোনা, single উপাদান গোনা নয়।
4. **negative সংখ্যা ধরে নেওয়া** — এই window logic শুধু positive সংখ্যায় খাটে; negative বা 0 থাকলে গুণফল monotonic থাকে না, window ভাঙে।
5. **`prod` reset না করা / float ব্যবহার** — integer-এ `//` ব্যবহার করো; float দিয়ে ভাগ করলে rounding error-এ ভুল গোনা হতে পারে।
## শেখা ও পরের অনুশীলন {#practice}
### এই ধারণার পরের অনুশীলন {#18-harder-problems-that-inherit-this-idea}
- **LeetCode — Subarrays with K Different Integers** (