Count runs whose product is below k
Medium · Target 20 minutes · Sliding window· Type asked at
Amazon
Goldman Sachs
IMC
Given an array nums of positive integers and an integer k, return the
number of contiguous subarrays whose product is strictly less than k.
Examples
| Input | Output | Why |
|---|---|---|
nums = [10,5,2,6], k = 100 | 8 | [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]. |
nums = [1,2,3], k = 0 | 0 | No product of positive numbers is below 0. |
nums = [1,1,1], k = 2 | 6 | Every subarray has product 1. |
Constraints
- 1 ≤ n ≤ 3 × 10⁴
- 1 ≤ nums[i] ≤ 1000
- 0 ≤ k ≤ 10⁶
Hints
Hint 1
All numbers are at least 1, so extending a subarray never lowers its product.
Hint 2
For each right end hi, find the furthest-left start lo with product below k. How many valid subarrays end at hi?
Hint 3
Exactly hi − lo + 1: every start from lo to hi. Add that at each step.
Where people lose marks
- Forgetting k ≤ 1: the window can never be valid, and the shrink loop must not run past hi.
- Overflow when the product is kept without shrinking: in this method it never exceeds k × 1000, which fits in 64 bits.
- Adding 1 per valid window instead of hi − lo + 1.
Dry run on [10,5,2,6],100
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 4nums100lo/hi512263product10count1
Multiply by 10: the window 0..0 has product 10. The 1 subarray ending at 0 that start at 0 or later all qualify. Total 1.
-
Step 2 / 4nums100lo51hi2263product50count3
Multiply by 5: the window 0..1 has product 50. The 2 subarrays ending at 1 that start at 0 or later all qualify. Total 3.
-
Step 3 / 4nums10051lo22hi63product10count5
Multiply by 2: the window 0..2 has product 100. Not below 100, so divide out 10; now 10. The 2 subarrays ending at 2 that start at 1 or later all qualify. Total 5.
-
Step 4 / 4nums10051lo2263hiproduct60count8
Multiply by 6: the window 1..3 has product 60. The 3 subarrays ending at 3 that start at 1 or later all qualify. Total 8.
How to think about it
With every element at least 1, a product can only grow as the subarray grows, so "product below k"
survives shrinking and the variable window applies. For each right end hi, shrink until the
window is valid. Then every subarray ending at hi and starting anywhere from lo to
hi is a suffix of a valid window, hence valid, and those are all the valid subarrays ending at
hi. So add hi − lo + 1.
That one line turns a window that measures into a window that counts, and it is the first of three counting moves in this module. If k ≤ 1 nothing qualifies, which is worth handling up front: otherwise the shrinking loop would empty the window and keep dividing.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def count_product_below(nums, k):
if k <= 1:
return 0 # no product of positive integers is below 1
total = lo = 0
prod = 1
for hi, x in enumerate(nums):
prod *= x
while prod >= k: # shrink until the window is valid
prod //= nums[lo]
lo += 1
total += hi - lo + 1 # every start from lo to hi works
return total#include <vector>
long long solve(const std::vector<int>& nums, long long k) {
if (k <= 1) return 0; // no product of positive integers is below 1
long long total = 0, prod = 1;
int lo = 0;
for (int hi = 0; hi < (int)nums.size(); ++hi) {
prod *= nums[hi];
while (prod >= k) prod /= nums[lo++]; // shrink until valid
total += hi - lo + 1; // every start from lo to hi works
}
return total;
}class Solution {
public long countProductBelow(int[] nums, long k) {
if (k <= 1) return 0; // no product of positive integers is below 1
long total = 0, prod = 1;
int lo = 0;
for (int hi = 0; hi < nums.length; hi++) {
prod *= nums[hi];
while (prod >= k) prod /= nums[lo++]; // shrink until valid
total += hi - lo + 1; // every start from lo to hi works
}
return total;
}
}function countProductBelow(nums, k) {
if (k <= 1) return 0; // no product of positive integers is below 1
let total = 0, lo = 0, prod = 1;
for (let hi = 0; hi < nums.length; hi++) {
prod *= nums[hi];
while (prod >= k) prod /= nums[lo++]; // shrink until valid
total += hi - lo + 1; // every start from lo to hi works
}
return total;
}fn solve(nums: &[i64], k: i64) -> i64 {
if k <= 1 { return 0; } // no product of positive integers is below 1
let (mut total, mut prod, mut lo) = (0i64, 1i64, 0usize);
for hi in 0..nums.len() {
prod *= nums[hi];
while prod >= k { // shrink until valid
prod /= nums[lo];
lo += 1;
}
total += (hi + 1 - lo) as i64; // every start from lo to hi works
}
total
}import Data.Array
-- Fold carrying (window start, product, count); each step adds the starts that work for this end.
solve :: [Int] -> Int -> Int
solve nums k
| k <= 1 = 0
| otherwise = third (foldl step (0, 1, 0) (zip [0 ..] nums))
where
arr = listArray (0, length nums - 1) nums
third (_, _, c) = c
step (lo, prod, total) (hi, x) =
let (lo', p') = shrink lo (prod * x)
in (lo', p', total + hi - lo' + 1)
shrink lo p
| p >= k = shrink (lo + 1) (p `div` (arr ! lo))
| otherwise = (lo, p)Variants to try
- Products of numbers that may be fractions or zero: take logarithms for the fractions; zeros split the array.
- Sum below k instead of product, with positive numbers: the same counting line.
Next problems
Count substrings holding a, b and c
When validity survives growing, count from the other side: after shrinking to the last valid start, every earlier start works too.
Open the problem → Hard30 minCount runs with exactly k distinct values
"Exactly k" is not monotone, so no single window counts it. Two windows that count "at most" do, and their difference is the answer.
Open the problem → Easy10 minBest total over k consecutive days
A window of fixed width slides one place at a time: add the element that enters, subtract the one that leaves.
Open the problem →Write a solution and run it against the real test table.
Keep going
Count substrings holding a, b and c
When validity survives growing, count from the other side: after shrinking to the last valid start, every earlier start works too.
Open the problem → Hard30 minCount runs with exactly k distinct values
"Exactly k" is not monotone, so no single window counts it. Two windows that count "at most" do, and their difference is the answer.
Open the problem → Easy10 minBest total over k consecutive days
A window of fixed width slides one place at a time: add the element that enters, subtract the one that leaves.
Open the problem → Sliding windowThe pattern behind it
A window that grows on the right, shrinks on the left, and holds an invariant at all times.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.