Skip to main content
Ace Hired
All coding problems

Number of Subarrays with Product Less Than K

Mediumsliding windowSliding window (two pointers) on a monotonic productsliding-windowarraystwo-pointers

Maintained by Vikas D, software engineer

You are handed an array of positive integers and a single positive integer k. A contiguous slice, or subarray, is a run of one or more neighbouring values taken in their original order with nothing skipped. The task is to count every such slice whose elements multiply together to something strictly less than k.

Because all the numbers are positive, the product of a slice can only grow as you add more elements to it and can only shrink as you drop elements from the front. That monotonic behaviour is the lever that makes an efficient solution possible.

Watch the edge where k is very small. When k is 0 or 1, no product of positive integers can ever fall below it, since the smallest possible product is 1, so the answer is simply 0.

Return a single integer: the total number of qualifying subarrays.

Examples

Input: nums = [10, 5, 2, 6], k = 100
Output: 8

The qualifying slices are [10], [5], [2], [6], [10,5], [5,2], [2,6], and [5,2,6]. The slice [10,5,2] multiplies to exactly 100, which is not strictly less than 100, so it does not count.

Input: nums = [1, 2, 3], k = 1
Output: 0

Every slice has a product of at least 1, so nothing is strictly below 1. The same reasoning gives 0 for any k of 0 or 1.

Input: nums = [1, 2, 3, 4], k = 10
Output: 7

Counting slices that stay under 10: [1], [2], [3], [4], [1,2], [2,3], and [1,2,3] (product 6). Slices like [3,4] (12) and [2,3,4] (24) are too large.

Constraints

  • 1 <= nums.length <= 3 * 10^4
  • 1 <= nums[i] <= 1000 (all values are positive integers)
  • 0 <= k <= 10^6
  • Subarrays must be contiguous and contain at least one element

Visible test cases

  • numSubarrayProductLessThanK([10,5,2,6], 100) == 8
  • numSubarrayProductLessThanK([1,2,3], 0) == 0
  • numSubarrayProductLessThanK([1,2,3], 1) == 0
  • numSubarrayProductLessThanK([1,1,1], 2) == 6
  • numSubarrayProductLessThanK([2,3,4], 100) == 6
  • numSubarrayProductLessThanK([100,200,300], 50) == 0
  • numSubarrayProductLessThanK([1,2,3,4], 10) == 7

Hints

Hint 1

Since every number is positive, a window's product never decreases when you push a new element onto the right and never increases when you pop one off the left. That gives you a clean monotonic property to exploit.

Hint 2

Slide a window with two pointers. Keep multiplying in the new right element, and whenever the running product reaches k or more, divide out elements from the left until it drops back under k.

Hint 3

Once the window ending at the right pointer is valid, every subarray that ends at that right index and starts anywhere inside the window is also valid. The count of those is the window length, right - left + 1, so add that each step. Handle k <= 1 up front by returning 0.

Loading the editor...

Approaches

Brute force over all subarrays

Time O(n^2) · Space O(1)

Enumerate every start and end, multiply the run as you extend it, and increment a counter whenever the running product stays under k.

  1. Initialize a counter to 0.
  2. For each start index i, set a running product to 1.
  3. For each end index j from i forward, multiply the running product by nums[j].
  4. If the product is still less than k, increment the counter; once it reaches k, break out of the inner loop since extending further only grows it.
  5. Return the counter after all starts are processed.

Optimal sliding window with two pointers

Time O(n) · Space O(1)

Maintain a window whose product is always below k. Because the inputs are positive, growing the window on the right and shrinking it on the left moves the product in predictable directions, so each valid right end contributes a window's worth of subarrays at once.

  1. If k is 0 or 1, return 0 immediately, because no product of positive integers can be strictly less than 1.
  2. Set count = 0, product = 1, and left = 0.
  3. Move right across the array, multiplying product by nums[right] each step.
  4. While product is greater than or equal to k, divide product by nums[left] and advance left, shrinking the window until it is valid again.
  5. Add right - left + 1 to count, which is the number of valid subarrays ending at the right pointer, then continue.
  6. Return count after the right pointer reaches the end.

Common mistakes

  • Forgetting the k <= 1 guard. With k of 0 or 1 the while loop logic still runs but division by left can walk past right, so handle this case explicitly and return 0.
  • Counting with a strict-versus-non-strict mistake. The product must be strictly less than k, so the shrink loop condition is product >= k, not product > k. Using > would wrongly accept a window whose product equals k.
  • Adding 1 per valid window instead of right - left + 1. Each new right end introduces a whole batch of new subarrays, one for every valid start, so a single increment undercounts badly.
  • Assuming the array can contain zeros or negatives. This solution relies on strictly positive values for the monotonic shrink-and-grow argument; a zero would make division by left meaningless and a negative would break the direction of the inequality.
  • Recomputing the window product from scratch on every step, which quietly turns the linear solution back into a quadratic one.

Follow-up variations

  • Return the number of subarrays whose product is less than or equal to k instead of strictly less than, and reason about how the boundary condition changes.
  • Find the single longest subarray whose product is below k, returning its length rather than a total count.
  • Switch to a sum constraint: count subarrays whose element sum is below k, and discuss why the same window trick still works for positive values.
  • Allow zeros or negative numbers in the array and explain why the simple sliding window breaks, then design a prefix-product or divide-and-conquer alternative.
  • Answer the query for many different values of k efficiently, for example by precomputing prefix products and binary searching.

Recommended problems

Build the rest of your prep