Subarray product less than K

Count contiguous subarrays whose product stays under a given threshold.

sliding-window two-pointers subarray counting

Given a list of positive integers `nums` and an integer `k`, return the number of contiguous subarrays whose product is strictly less than `k`.

Implement the function `num_subarrays_product_less_than_k(nums: list[int], k: int) -> int`.

- All elements in `nums` are positive integers.
- A subarray is a contiguous non-empty sequence of elements.
- The result may be large, so return it as an integer.
- If `k <= 1`, no subarray can have a product less than `k` (since all products are at least 1), so return 0.

Your solution should run in O(n) time using a sliding window approach.

Constraints

- 1 <= len(nums) <= 50000
- 1 <= nums[i] <= 1000
- 0 <= k <= 10^9
- The answer is guaranteed to fit in a 64-bit signed integer.

Example

>>> num_subarrays_product_less_than_k([10, 5, 2, 6], 100)
8

>>> num_subarrays_product_less_than_k([1, 2, 3], 0)
0

25 points ~30 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a sliding window with two pointers. Maintain the product of the current window.

For each right endpoint, find the smallest left such that product < k. All subarrays ending at that right with start >= left are valid.

If k <= 1, no subarray qualifies because all numbers are positive and >= 1.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.