090 — Number of Subarrays with Product Less Than K

087-এ তুমি window গুটিয়ে সবচেয়ে ছোট দৈর্ঘ্য খুঁজেছিলে। এবার একই shrinkable window, কিন্তু লক্ষ্য বদলে গেল — এখন আর দৈর্ঘ্য নয়, গুনতে হবে: কতগুলো subarray-র গুণফল k-এর চেয়ে ছোট। সবচেয়ে মিষ্টি জায়গাটা হলো গোনার একটা ছোট্ট জাদু-সূত্র — r − l + 1। এই এক লাইনের ট্রিক একবার বুঝে গেলে এই pattern-এর গোটা পরিবার তোমার হাতের মুঠোয়।

Problem link ও উৎস

• Original source: LeetCode — Subarray Product Less Than K
• Platform: LeetCode — https://leetcode.com/problems/subarray-product-less-than-k/
• 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

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

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

একটা 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

উদাহরণ

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।

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

ভাবো তুমি একটা দোকানে ঢুকছ, হাতে 100 টাকা (k)। তুমি বাঁ থেকে ডানে সাজানো তাক ধরে ধরে জিনিস তুলছ, কিন্তু এখানে দাম যোগ হয় না, গুণ হয় (ধরো এক অদ্ভুত দোকান, যেখানে প্রতিটা জিনিস আগের মোটকে গুণ করে দেয়)।

তুমি ডান হাত (r) বাড়িয়ে নতুন জিনিস তুলছ। যদি মোট গুণফল 100 ছুঁয়ে ফেলে বা ছাড়িয়ে যায়, তুমি বাঁ হাত (l) দিয়ে সবচেয়ে পুরোনো জিনিসটা তাকে ফিরিয়ে রাখছ — যতক্ষণ না আবার বাজেটের ভেতরে আসো। প্রতিবার যখন তোমার ঝুড়ি বাজেটের ভেতরে, তুমি মনে মনে গোনো — "এই শেষ জিনিসটা রেখে আমি কত রকম ভাবে ঝুড়ি বানাতে পারতাম?" উত্তর: ঝুড়িতে যত জিনিস আছে, ঠিক ততগুলো (r − l + 1)। সব মিলিয়ে সেই গোনাই উত্তর।

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

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

এটা সরাসরি দাঁড়িয়ে আছে 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।

ভেতরের অঙ্ক

মূল গাণিতিক ভিত্তি — 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-এর গুণফলের চেয়ে কখনো বড় নয়।

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

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

সবচেয়ে সরল চিন্তা — প্রতিটা সম্ভব 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 হিসেবে কাজে লাগবে।

কোথায় বেশি কাজ হতে পারে

সমস্যা হলো জোড়া (i, j)-এর সংখ্যা — n লম্বা array-তে প্রায় n² / 2। n = 10000 হলে সেটা প্রায় 5 কোটি ধাপ, আর n = 100000 হলে 500 কোটি — interview/contest-এ নিশ্চিত Time Limit Exceeded।

উদাহরণ

n = 100000 হলে:
  brute force: ~5,000,000,000 ধাপ   (O(n^2), ধীর)
  window     : ~200,000 ধাপ          (O(n), প্রতিটা index l আর r দিয়ে একবার করে ছোঁয়া)

মূল অপচয়টা চোখে পড়ে: i যখন এক ঘর ডানে সরে, আমরা আগের সব কাজ ফেলে আবার শূন্য থেকে গুণ শুরু করি। অথচ আগের গণনার অনেকটাই পুনর্ব্যবহার করা যেত — সেখানেই window-র সুযোগ।

আরও ভালোভাবে ভাবা

মূল 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 গুনে নেয়।

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

আসল "আহা!" মুহূর্ত — প্রতিটা 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, এবং আরও অনেক)।

ছবিতে বোঝা

nums = [10, 5, 2, 6], k = 100। window [l..r] ডানে এগোচ্ছে, product track হচ্ছে:

উদাহরণ

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-এ ধাপে ধাপে

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-র সৌন্দর্য।

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

Python

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

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

উদাহরণ

if k <= 1:
    return 0

positive সংখ্যার গুণফল সবসময় কমপক্ষে 1। তাই k যদি 1 বা তার ছোট হয়, কোনো subarray-র product কখনো < k হতে পারে না — সরাসরি 0। (এই guard না থাকলে নিচের while-এ গণ্ডগোল হতো — empty window-এও prod=1 >= k হয়ে left array ছাড়িয়ে যেত।)

উদাহরণ

prod = 1; left = 0; count = 0

prod = চলতি window-এর গুণফল (শূন্য উপাদানে 1, কারণ গুণের identity 1), left = window-এর বাঁ প্রান্ত, count = মোট valid subarray।

উদাহরণ

prod *= nums[right]

right এক ধাপ ডানে গেল, নতুন উপাদান window-এ ঢুকল, গুণফল আপডেট।

উদাহরণ

while prod >= k:
    prod //= nums[left]; left += 1

window-এর গুণফল k ছুঁয়ে/ছাড়িয়ে গেলে আর valid নয় — তাই বাঁ দিক থেকে উপাদান সরাই (গুণফলকে সেই সংখ্যা দিয়ে ভাগ করি, কারণ সরানো মানে গুণফল থেকে তাকে বের করা), left এগোয়। সব positive বলে integer ভাগ // ঠিকঠাক উল্টো গুণ করে।

উদাহরণ

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 মিলিয়ে দেখা

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

উদাহরণ

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! — সব মিলেছে।

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

সময়

O(n) — right array-র উপর একবার ঘোরে (n ধাপ)। while-এর ভেতরে left শুধু সামনে এগোয়, কখনো পিছায় না; পুরো run-এ left সব মিলিয়ে সর্বোচ্চ n ধাপ এগোতে পারে। তাই দুই pointer মিলে মোট কাজ 2n-এর মধ্যে — অর্থাৎ O(n)। (brute force-এর O(n²) থেকে বিশাল লাফ।)

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

O(1) — শুধু prod, left, count কয়টা variable। কোনো বাড়তি array, list বা hash map লাগছে না। input ছাড়া স্মৃতি প্রায় শূন্য।

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

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-এ ভুল গোনা হতে পারে।

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

এই ধারণার পরের অনুশীলন

• LeetCode — Subarrays with K Different Integers (https://leetcode.com/problems/subarrays-with-k-different-integers/) — গোনার একই r − l + 1 চিন্তা, কিন্তু "exactly K = atMost(K) − atMost(K−1)" মোচড়ে (এই repo-র 089)।
• LeetCode — Count Number of Nice Subarrays (https://leetcode.com/problems/count-number-of-nice-subarrays/) — odd সংখ্যা গোনা, atMost প্রযুক্তি ফিরে আসে।
• LeetCode — Binary Subarrays With Sum (https://leetcode.com/problems/binary-subarrays-with-sum/) — sum দিয়ে atMost, একই গোনার কাঠামো।

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

Counting subarrays via sliding window (r − l + 1 trick) — positive সংখ্যায় window valid রাখো (এখানে product < k), আর প্রতি r-এ valid subarray-র সংখ্যা = r − l + 1 যোগ করো। বড় শিক্ষা: subarray গুনতে চাইলে প্রতিটা আলাদা না দেখে "এই ডান-প্রান্তে শেষ হওয়া কতগুলো" এক ধাপে গোনো — window-এর দৈর্ঘ্যই সেই সংখ্যা।

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

ভবিষ্যতের আমাকে এক লাইনে: "positive array + 'product < k subarray গোনো' = shrinkable window; r বাড়িয়ে prod ×=, prod ≥ k হলে বাঁ দিক ভাগ করে গুটাও, তারপর count += r−l+1। Signal: 'count subarrays' + monotonic invariant দেখলে r−l+1 ট্রিক মনে পড়ুক। আর গোড়ায় k ≤ 1 → 0।"

পরের ধাপ → এই level শেষ; এবার ../../07-binary-search-on-answer/problems/README.md। ভিত্তি → 087 — Minimum Size Subarray Sum। সম্পর্কিত → 089 — Count Subarrays with Exactly K Distinct।

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

---

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