Subarray Product Less Than K

1. Define the problem

Given an array of positive integers nums and an integer k, return the number of contiguous subarrays where the product of all elements is strictly less than k . Grow a window on the right, dividing back out from the left whenever the running product meets or exceeds k, and count every window ending at right that stays valid.

Constraints

1 ≤ nums.length ≤ 3 × 10⁴
1 ≤ nums_i ≤ 1000
0 ≤ k ≤ 10⁶

Example

Inputnums = [10, 5, 2, 6], k = 100

Output8

Explanation The eight subarrays are [10], [5], [2], [6], [10,5], [5,2], [2,6], and [5,2,6].

2. Visualize the solution

Shrink left whenever the product hits k

010

Statusvalid

Window [10,5] product 50 < 100; count += 2.

What happens in this step

right=1: product = 10 * 5 = 50
  50 < 100 → window stays valid, no shrinking needed
  count += (right - left + 1) = (1 - 0 + 1) = 2
  running count = 1 (from right=0) + 2 = 3

Step 1 of 4

Steps to visualize

Grow right and multiply the running product by the new value.
While the product is greater than or equal to k, divide out the leftmost value and advance left.
Every subarray ending at right and starting at or after left is valid.
Add the window size (right - left + 1) to the running count.
Continue until right reaches the end of the array.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Shrink left whenever the product hits k

010

Statusvalid

Window [10,5] product 50 < 100; count += 2.

What happens in this step

right=1: product = 10 * 5 = 50
  50 < 100 → window stays valid, no shrinking needed
  count += (right - left + 1) = (1 - 0 + 1) = 2
  running count = 1 (from right=0) + 2 = 3

Step 1 of 4

4. Solution

Solution

solution.tsTypeScript

function numSubarrayProductLessThanK(nums, k) {
  if (k <= 1) return 0;

  let left = 0;
  let product = 1;
  let count = 0;

  for (let right = 0; right < nums.length; right++) {
    product *= nums[right];

    while (product >= k) {
      product /= nums[left];
      left++;
    }

    count += right - left + 1;
  }

  return count;
}

Time: O(n)
Space: O(1)

5. Test cases

Test cases

Input	Expected	Covers
`nums = [10, 5, 2, 6], k = 100`	`8`	Docstring example
`nums = [1, 2, 3], k = 1`	`0`	k <= 1 can never be strictly beaten
`nums = [5], k = 10`	`1`	Single element below k
`nums = [5], k = 5`	`0`	Single element equal to k is excluded
`nums = [1, 1, 1], k = 2`	`6`	Every subarray stays under k
`nums = [2, 3], k = 6`	`2`	A subarray whose product equals k is excluded
`nums = [1, 2, 3], k = 1000`	`6`	k large enough that every subarray counts

Subarray Product Less Than K