MediumArraySliding WindowTwo Pointers

Subarray Product Less Than K

1 approach, code in every language

Given an array of positive integers and a threshold k, count how many contiguous slices of the array have a product of all their elements strictly below k.

Since every value is positive, extending a window can only grow the product and shrinking it can only reduce the product. That monotonic behavior means a sliding window can maintain the running product and, whenever it grows too large, slide the left edge forward until the window is valid again.

Example 1

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

Output: 8

The valid contiguous slices are [10], [5], [2], [6], [10,5], [5,2], [2,6], and [5,2,6]. The slice [10,5,2] is excluded because 100 is not strictly less than 100.

Example 2

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

Output: 0

No product of positive integers can be below 0, so nothing qualifies.

Constraints

1 ≤ nums.length ≤ 3 × 10^4
1 ≤ nums[i] ≤ 10^3
0 ≤ k ≤ 10^6

Sliding Window on the Product

Keep a running product for the current window; whenever it reaches k, advance the left edge to divide it back down, then add the number of new subarrays ending at the right edge.

Loading animation…

Intuition

Fix the right end of the window and ask how many valid subarrays end exactly there. Because all numbers are positive, once the window product drops below k it is the widest valid window ending at that right index, and every suffix of that window is also valid. The count of such subarrays ending at the right index is simply the window length. Sliding the left pointer only ever moves forward, so each element enters and leaves the window at most once.

Algorithm walkthrough

1Handle the trivial case: if k is 1 or less, no product of positive integers can be strictly smaller, so return 0.
2Walk a right pointer across the array, multiplying its value into a running product.
3While the product is at least k, divide out the element at the left pointer and move the left pointer forward.
4Add (right - left + 1) to the answer, which is the number of valid subarrays ending at the current right index.
5Return the accumulated count after the sweep finishes.

Implementation

class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        if k <= 1:
            return 0
        prod = 1
        left = 0
        count = 0
        for right, val in enumerate(nums):
            prod *= val
            while prod >= k:
                prod //= nums[left]
                left += 1
            count += right - left + 1
        return count

Time

O(n)

Space

O(1)

Each pointer moves forward at most n times.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Safe Stretches of the Filter Cascade is our own problem on the technique behind Subarray Product Less Than K: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free