Subarrays With Product Below K
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
Given an array nums of positive integers and an integer k, return the number of contiguous subarrays whose
product of all elements is strictly less than k. Subarrays at different positions are counted separately.
Examples
| nums | k | result |
|---|---|---|
[10, 5, 2, 6] | 100 | 8 |
[1, 2, 3] | 1 | 0 |
[1, 1, 1] | 2 | 6 |
Example 1 — [10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]. [10, 5, 2] has product exactly 100.
Example 2 — Every product is at least 1.
Example 3 — All 6 subarrays have product 1.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(nums: int[], k: int) → long
Constraints
-
nums.length -
nums[i] -
k - The answer may not fit in a 32-bit integer.
Expected complexity
- Time
- O(N)
- Space
- O(1)
Examples
| nums | k | Expected |
|---|---|---|
[10,5,2,6] | 100 | 8 |
[1,2,3] | 1 | 0 |
[1,1,1] | 2 | 6 |
Hint
Hint
All values are ≥ 1, so the product never shrinks when the window grows. Move the right end r forward, multiply, and while the
product is ≥ k divide out nums[l] and advance l; then exactly r - l + 1 windows end at r. Both pointers move one way,
so it is . Recomputing products from every start is on inputs full of 1s and times out. If k ≤ 1 the answer is 0.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1018 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 12 | verdict only |
| performance | 60 | 4 | verdict only |