Funcia
Lv.2arraysliding-windowtwo-pointers

Subarrays With Product Below K

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

numskresult
[10, 5, 2, 6]1008
[1, 2, 3]10
[1, 1, 1]26

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

  • 1≤N=1 \le N = nums.length ≤200,000\le 200{,}000
  • 1≤1 \le nums[i] ≤1,000\le 1{,}000
  • 1≤1 \le k ≤109\le 10^9
  • The answer may not fit in a 32-bit integer.

Expected complexity

Time
O(N)
Space
O(1)

Examples

numskExpected
[10,5,2,6]1008
[1,2,3]10
[1,1,1]26

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 O(N)O(N). Recomputing products from every start is O(N2)O(N^2) on inputs full of 1s and times out. If k ≤ 1 the answer is 0.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251018 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4012verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.