Subarray Product Less Than K
Medium · Sliding Window · Array · Sliding Window · Two Pointers
Problem
Given an array of positive integers nums and an integer k, return how many contiguous subarrays have a product of all their elements strictly less than k.
Every subarray is counted by its position, so equal subarrays at different places count separately, and a single element is a subarray too.
Examples
Input: nums = [2,5,3,10], k = 30 Output: 6
The qualifying subarrays are [2], [5], [3], [10], [2,5] and [5,3].
Input: nums = [4,1,1], k = 5 Output: 6
Every subarray has product 4 or 1, both below 5.
Input: nums = [7,8], k = 1 Output: 0
Every product is at least 1, so none is below 1.
Constraints
- 1 <= len(nums) <= 3 · 10^4
- 1 <= nums[i] <= 1000
- 0 <= k <= 10^6
Approaches
- Baseline: every start, stop when too big — time O(n²), space O(1)
Follow-up
With zeros or negative numbers allowed, the product is no longer monotone and the window breaks. Then you can split at zeros and track signs, or work with prefix sums of logarithms and binary search, which is exact only up to floating-point error.
Related problems
Start free on Cariara · Coding problems · System design studio
