Subarrays with Product Less than a Target
Mahabharata — The Garden of Multiplication — Shakuni's Dice Game
गुणनफलं यदा वर्धते सीमां च लङ्घयते। आदिं त्यक्त्वा पुनः गण्यं लघु यावत् न भवेत्॥
*When the product of multiplication grows and exceeds the limit, discard the beginning and count again until it becomes light.*
The Story
In the darker chambers of Hastinapura, Shakuni practiced his craft—not just loaded dice, but the mathematics of multiplication that governed his schemes.
"Every gamble," he explained to Duryodhana, "involves multiplied risks. When you bet on three consecutive throws, your combined risk is the product of individual risks, not the sum."
He laid out a sequence of risk multipliers for consecutive dice throws: [10, 5, 2, 6, 3, 4]
"Our tolerance is a product of 100," Shakuni said. "I want to count how many consecutive sequences of throws have combined risk below this threshold. Not the sequences themselves—just how many exist."
Duryodhana began the naive approach: "Sequence from position 0: just [10] has product 10 < 100, valid. [10,5] has product 50 < 100, valid. [10,5,2] has product 100, NOT < 100, invalid. So starting at 0, we have 2 valid sequences..."
"That approach," Shakuni interrupted, "requires checking every possible starting and ending position. O(n²) at best. When the game stretches through the night with hundreds of throws, we need efficiency."
He picked up two stones—one black, one white—and placed them at the start of the sequence.
"The black stone marks the beginning of my window. The white stone marks the end. I will slide the white stone right, multiplying as I go. When the product exceeds 100, I slide the black stone right, dividing as I go."
The algorithm unfolded:
**Window starts at position 0:** - White stone at 0: product = 10. Product < 100, so window [0,0] is valid. - How many valid subarrays end at position 0? Just one: [10]. Count = 1.
**Extend window:** - White stone moves to 1: product = 10 × 5 = 50. Product < 100. - Valid subarrays ending at position 1: [5] and [10,5]. Count += 2. Total = 3.
**Extend again:** - White stone moves to 2: product = 50 × 2 = 100. Product NOT < 100! - Shrink from left: divide by 10, black stone moves to 1. Product = 10. - Product < 100 now. Valid subarrays ending at position 2: [2] and [5,2]. Count += 2. Total = 5.
"Wait," Duryodhana interrupted. "How do you know there are 2 valid subarrays ending at position 2?"
"Simple arithmetic," Shakuni smiled. "The window currently spans from black stone (position 1) to white stone (position 2). That's positions 1 and 2. The number of subarrays ending at position 2 is exactly (white - black + 1) = (2 - 1 + 1) = 2."
"These subarrays are [2] (just position 2) and [5,2] (positions 1-2). Both have products less than 100."
The pattern continued through the array: - Position 3 (value 6): product becomes 10 × 6 = 60 after shrinking. Window [1,3]. Count += 3. - Position 4 (value 3): product becomes 60 × 3 = 180, too big! Shrink: 180/5 = 36. Window [2,4]. Count += 3. - Position 5 (value 4): product becomes 36 × 4 = 144, too big! Shrink: 144/2 = 72. Window [3,5]. Count += 3.
Final count: 1 + 2 + 2 + 3 + 3 + 3 = 14 valid subarrays.
"The key insight," Shakuni concluded, "is that for contiguous subarrays with a product constraint, a sliding window with two pointers handles everything. Extend right to include new elements, shrink left when the product exceeds the threshold. At each position, the count of valid subarrays ending there equals the window length."
Duryodhana marveled at his uncle's mathematical cunning. "O(n) time. Each element is added once and removed at most once."
"Exactly. Now let's apply this to counting winning sequences in tonight's game against Yudhishthira."
This is the Two Pointer (Sliding Window) technique for counting subarrays with product less than a target.
Duryodhana's First Instinct
Check every possible subarray by iterating all start and end positions. Calculate product for each. O(n²) time.
public int numSubarrayProductLessThanKBruteForce(int[] nums, int k) {
if (k <= 1) return 0; // Product can't be less than 1 with positive integers
int count = 0;
for (int start = 0; start < nums.length; start++) {
int product = 1;
for (int end = start; end < nums.length; end++) {
product *= nums[end];
if (product < k) {
count++;
} else {
break; // Products will only get larger
}
}
}
return count;
}Shakuni's Wisdom
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (k <= 1) return 0; // No valid subarrays possible
int count = 0;
int product = 1;
int left = 0;
for (int right = 0; right < nums.length; right++) {
// Extend window: multiply by new element
product *= nums[right];
// Shrink window from left while product >= k
while (product >= k && left <= right) {
product /= nums[left];
left++;
}
// All subarrays ending at 'right' with start in [left, right] are valid
// Count of such subarrays = right - left + 1
count += (right - left + 1);
}
return count;
}
// Test with Shakuni's risk multipliers
public static void main(String[] args) {
int[] risks = {10, 5, 2, 6};
int threshold = 100;
int validSequences = new Solution().numSubarrayProductLessThanK(risks, threshold);
System.out.println("Valid subarrays: " + validSequences);
// Output: Valid subarrays: 8
}Step-by-Step Walkthrough
Array: [10, 5, 2, 6], k=100
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=0: product = 1 × 10 = 10
10 < 100 ✓ (no shrinking needed)
Window: [0, 0], length = 1
Count += 1 → Total: 1
Valid subarrays: [10]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=1: product = 10 × 5 = 50
50 < 100 ✓
Window: [0, 1], length = 2
Count += 2 → Total: 3
Valid subarrays: [5], [10,5]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=2: product = 50 × 2 = 100
100 >= 100 ✗ → Shrink!
product = 100 / 10 = 10, left = 1
10 < 100 ✓
Window: [1, 2], length = 2
Count += 2 → Total: 5
Valid subarrays: [2], [5,2]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
right=3: product = 10 × 6 = 60
60 < 100 ✓
Window: [1, 3], length = 3
Count += 3 → Total: 8
Valid subarrays: [6], [2,6], [5,2,6]
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
✅ Final Count: 8 valid subarrays
All valid subarrays:
[10], [5], [10,5], [2], [5,2], [6], [2,6], [5,2,6]Deep Insight
**Why does (right - left + 1) count all valid subarrays ending at right?**
If the window is [left, right], then the valid subarrays ending at `right` are: - [right] (length 1) - [right-1, right] (length 2) - ... - [left, ..., right] (length right-left+1)
That's exactly `right - left + 1` subarrays.
**Why is the sliding window approach correct?**
Invariant: at any time, the window [left, right] has product < k (or window is empty). When we extend to include nums[right], we shrink from left until the product is valid again. Any subarray within this valid window also has product < k.
**Critical edge case: k ≤ 1** With positive integers, the smallest possible product is 1 (single element = 1). If k ≤ 1, no product can be less than k, so return 0 immediately.
**Why multiply/divide instead of recompute?** Recomputing the product from scratch each time would be O(n) per position. By maintaining a running product and adjusting with multiply/divide, each element is processed at most twice (once when added, once when removed), giving O(n) total.
Complexity Analysis
| Approach | Time | Space | Note |
|---|---|---|---|
| Brute Force | O(n²) | O(1) | Nested loops, early termination helps but worst case still quadratic |
| Optimal | O(n) | O(1) | Each element added once, removed at most once |
Pattern Recognition
✅ Contiguous subarrays (not subsequences) ✅ Product constraint (not sum) ✅ Counting, not finding specific subarrays ✅ "Product less than K" phrasing **LeetCode Trigger Phrases:** → "subarray product less than k" → "count contiguous subarrays... product below" → "number of subarrays where product < target"
Bhagavad Gita 4.37
यथैधांसि समिद्धोऽग्निर्भस्मसात्कुरुतेऽर्जुन। ज्ञानाग्निः सर्वकर्माणि भस्मसात्कुरुते तथा॥
As a blazing fire reduces fuel to ashes, O Arjuna, so does the fire of knowledge reduce all actions to ashes.
Connection: The sliding window burns through the array like fire through fuel—consuming each element exactly once, transforming the complex task of counting into simple arithmetic. When the product grows too large (exceeds threshold), the algorithm 'burns away' elements from the left, reducing the problem back to a manageable state. Each contraction is like the fire of knowledge simplifying complexity into clarity.