Definition
- Sliding window – maintain a window
[left, right]with a running product; expandrightto include new elements and shrinkleftwhen the product reaches or exceeds the target. - Counting – at each valid right position, the number of valid subarrays ending at
rightisright - left + 1. - Monotonic product – because all elements are positive, multiplying grows the product and dividing shrinks it, which is the property the window needs.
- Shrink guard – never let
leftpassright; checkleft <= rightin the shrink loop. - Complexity – O(n) time, O(1) space; each pointer moves forward at most n times total.
Rajesh at the National Bank of India tracks daily growth multipliers for a portfolio. He needs to count how many consecutive stretches of days have a combined growth factor below a risk threshold. He grows a window by including the next day on the right; if the combined factor gets too big, he drops days off the left until it is safe again. For each new right day, every valid window ending there counts.
Understanding the Concepts
What is the subarrays with product less than target problem?
Given an array of positive numbers and a target, count the number of contiguous subarrays whose product is strictly less than the target. This is a sliding-window counting problem that works because all numbers are positive, which guarantees the product changes monotonically as the window grows and shrinks.
package com.bank.core;
public class SubarrayProductLessThanK {
public static int countSubarrays(int[] arr, int target) {
if (target <= 1) return 0;
int count = 0;
int product = 1;
int left = 0;
for (int right = 0; right < arr.length; right++) {
product *= arr[right];
while (product >= target && left <= right) {
product /= arr[left];
left++;
}
count += right - left + 1;
}
return count;
}
public static void main(String[] args) {
int[] multipliers = {10, 5, 2, 6};
int target = 100;
System.out.println("Count: " + countSubarrays(multipliers, target));
}
}
Count: 8
Why does the window length give the count of valid subarrays?
When the window is [left, right] and the product is below the target, every subarray that ends at right and starts anywhere from left to right is also valid. That is because removing elements from the left can only decrease the product (since all elements are positive), so shorter subarrays within the window also have products below the target. The count of such subarrays is right - left + 1.
package com.bank.core;
public class WindowLengthCount {
public static void main(String[] args) {
int[] arr = {10, 5, 2, 6};
int target = 100;
int product = 1, left = 0, count = 0;
for (int right = 0; right < arr.length; right++) {
product *= arr[right];
while (product >= target && left <= right) {
product /= arr[left];
left++;
}
int windowLen = right - left + 1;
System.out.println("right=" + right + " window=[" + left + "," + right
+ "] product=" + product + " new subarrays=" + windowLen);
count += windowLen;
}
System.out.println("Total: " + count);
}
}
right=0 window=[0,0] product=10 new subarrays=1
right=1 window=[0,1] product=50 new subarrays=2
right=2 window=[0,2] product=100 new subarrays=2
right=3 window=[1,3] product=60 new subarrays=3
Total: 8
Why does the shrink loop divide out from the left?
Multiplying in a new right element can push the product above the target. The only way to bring it back down is to remove elements from the left by dividing them out. Because all elements are positive, each division strictly reduces the product. We keep dividing until the product drops back below the target or the window becomes empty.
package com.bank.core;
public class ShrinkDemo {
public static void main(String[] args) {
int[] arr = {10, 5, 2, 6};
int target = 100;
int product = 1, left = 0;
// Simulate reaching right=2: product = 10*5*2 = 100
for (int i = 0; i <= 2; i++) product *= arr[i];
System.out.println("Before shrink: product=" + product + " left=" + left);
while (product >= target) {
System.out.println(" Dividing out arr[" + left + "]=" + arr[left]);
product /= arr[left];
left++;
}
System.out.println("After shrink: product=" + product + " left=" + left);
}
}
Before shrink: product=100 left=0
Dividing out arr[0]=10
After shrink: product=10 left=1
Why do all elements need to be positive?
The sliding window works because multiplying a positive number always increases the product and dividing always decreases it. If a zero appeared, the product would drop to zero and never recover through division. If a negative appeared, multiplying could flip the sign, breaking the monotonic property. In those cases, a different approach such as prefix products in log space would be needed.
package com.bank.core;
public class PositivityRequirement {
public static void main(String[] args) {
// With all positives: monotonic product
int product = 1;
int[] positive = {2, 3, 4};
for (int val : positive) {
product *= val;
System.out.println("After multiplying " + val + ": product=" + product);
}
// With a zero: product collapses
product = 1;
int[] withZero = {2, 0, 4};
for (int val : withZero) {
product *= val;
System.out.println("After multiplying " + val + ": product=" + product);
}
}
}
After multiplying 2: product=2
After multiplying 3: product=6
After multiplying 4: product=24
After multiplying 2: product=2
After multiplying 0: product=0
After multiplying 4: product=0
What happens when the target is 1 or less?
If the target is 1 or less, no subarray of positive integers (each at least 1) can have a product below it. We return zero immediately. This edge case guard also prevents the shrink loop from producing incorrect counts.
package com.bank.core;
public class TargetEdgeCase {
public static int countSubarrays(int[] arr, int target) {
if (target <= 1) return 0; // Guard: no positive product < 1
int count = 0, product = 1, left = 0;
for (int right = 0; right < arr.length; right++) {
product *= arr[right];
while (product >= target && left <= right) {
product /= arr[left]; left++;
}
count += right - left + 1;
}
return count;
}
public static void main(String[] args) {
System.out.println("target=0: " + countSubarrays(new int[]{1, 2, 3}, 0));
System.out.println("target=1: " + countSubarrays(new int[]{1, 2, 3}, 1));
}
}
target=0: 0
target=1: 0
What are the edge cases?
Edge cases include a single-element array, all elements equal to 1, and a target larger than the product of the entire array.
package com.bank.core;
public class ProductEdgeCases {
public static int countSubarrays(int[] arr, int target) {
if (target <= 1) return 0;
int count = 0, product = 1, left = 0;
for (int right = 0; right < arr.length; right++) {
product *= arr[right];
while (product >= target && left <= right) { product /= arr[left]; left++; }
count += right - left + 1;
}
return count;
}
public static void main(String[] args) {
System.out.println("Single below: " + countSubarrays(new int[]{5}, 10));
System.out.println("Single at: " + countSubarrays(new int[]{10}, 10));
System.out.println("All ones: " + countSubarrays(new int[]{1, 1, 1}, 2));
System.out.println("Huge target: " + countSubarrays(new int[]{2, 3, 4}, 1000));
}
}
Single below: 1
Single at: 0
All ones: 6
Huge target: 6
How is this different from subarray sum problems?
Subarray sum problems use a similar sliding-window approach but add and subtract instead of multiply and divide. The key difference is that product-based windows require strictly positive elements for monotonicity, while sum-based windows require non-negative elements.
| Aspect | Product window | Sum window |
|---|---|---|
| Grow operation | Multiply | Add |
| Shrink operation | Divide | Subtract |
| Monotonic when | All elements positive | All elements non-negative |
| Breaks when | Zeros or negatives present | Negatives present |
What should a senior engineer know?
A senior engineer should know that the linear-time sliding window depends entirely on the positivity of the elements. They should mention the edge case guard for target <= 1, the left <= right guard in the shrink loop, and the fact that integer overflow is possible if the product of the window exceeds Integer.MAX_VALUE before the shrink loop fires. Using long for the product is a safe practice.
Visual Overview
Array: [10, 5, 2, 6] Target: 100
right=0: product=10 window=[0,0] count += 1 (total: 1)
[10]
right=1: product=50 window=[0,1] count += 2 (total: 3)
[10, 5]
right=2: product=100 >= 100 → shrink
divide 10 → product=10 left=1
window=[1,2] count += 2 (total: 5)
[5, 2]
right=3: product=60 window=[1,3] count += 3 (total: 8)
[5, 2, 6]
┌───────────────────────────────────────┐
│ Valid subarrays (product < 100): │
│ [10], [5], [2], [6], │
│ [10,5], [5,2], [2,6], [5,2,6] │
│ Total: 8 │
└───────────────────────────────────────┘
Key Takeaway
Counting contiguous subarrays whose product is strictly below a target is a sliding-window problem that works beautifully because all the numbers are positive. Positivity gives a monotonic property: multiplying a new element into the product can only make it larger, and dividing an element out can only make it smaller, which is exactly what a sliding window needs to decide when to expand and when to shrink.
The counting trick is that at each right position, after shrinking from the left to bring the product back below the target, every subarray ending at right and starting anywhere from left to right is valid. The count of those subarrays is simply the window length, right minus left plus one. Because each pointer only moves forward, the entire algorithm runs in O(n) time with O(1) space.
In Rajesh's work at the National Bank of India, the portfolio risk team tracks daily growth multipliers and needs to count how many consecutive stretches of days have a combined growth factor below a risk threshold. Over long histories the brute-force check of every stretch would be quadratic, and the single sliding window gives the exact count efficiently.
The senior-level point is the positivity requirement. This technique depends on every number being strictly positive so the product changes monotonically as the window grows and shrinks. If zeros or negatives were allowed, the shrink-from-left logic would break. The target <= 1 edge case must also be guarded, because no product of positive integers can fall below 1, and using long for the product avoids overflow when the window grows large before the shrink fires.
Remember one sentence: expand right to multiply in, shrink left to divide out, and add the window length at each step to count valid subarrays in O(n) time.
---