Workspace

Problem workspace

3 day streakD

Subarray Product Less Than K

MediumSliding WindowCounting windows

The challenge

Count nonempty contiguous subarrays whose product is strictly smaller than k.

1 ≤ nums[i] ≤ 10⁶; 0 ≤ k ≤ 10⁹. Empty input returns 0.

Example

[10, 5, 2, 6], k = 100 → 8. The product 10 × 5 × 2 = 100 is excluded.

Use the walkthrough below to inspect the input and each state change.

See Product below K, step by step

Expand, shrink, and inspect the window state.

4 elements · zero-based indicesk = 100
Sliding window over 4 elementsThe current window is empty. Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.Empty window · L = 0, R = -1100512263
Current windowRecorded answerOutside window
Left
0
Right
-1
Length
0
Step 01 / 11

Start with an empty window

Both boundaries move forward. Watch what enters, what leaves, and when the answer changes.

left = 0; right = −1

Answer so far

0
View exact input

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

Current window is empty.

Put it into code

With positive integers, dropping elements cannot increase a product. Restore product < k, then count all suffixes ending at right.

Indices are zero-based. C++ uses C++17 or later.

def product_below_k(nums, k):
    # Positive integers only.
    if k <= 1:
        return 0
    left = total = 0
    product = 1
    for right, value in enumerate(nums):
        product *= value
        while product >= k:
            product //= nums[left]
            left += 1
        total += right - left + 1
    return total

A good place to start

Explore a pattern

A little guidance

Start with a pattern, read through a problem, and mark it solved when the idea clicks. Save anything you want to revisit.

New tutorials are added one at a time. Your bookmarks and solved checkmarks stay in this browser.

Explore the roadmap