713. Subarray Product Less Than K

713

MediumSliding WindowTwo pointers with running productVariable window counting

Subarray Product Less Than K

Given an array of positive integers nums and an integer k, return the number of contiguous subarrays whose product of all elements is strictly less than k.

Open official problem prompt ↗

In plain English

Count how many contiguous slices have a product strictly below the threshold k.

Picture it like this

Imagine filling a shopping cart from left to right where each item multiplies your total cost. As soon as the cart is too expensive you remove items from the front until it is affordable again; every affordable cart ending at the current item is a valid purchase to tally.

Example

Input: nums = [10, 5, 2, 6], k = 100
Output: 8
Why: The qualifying subarrays are [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6] — eight in total ([10,5,2] has product 100, not < 100).

Constraints

1 <= nums.length <= 3 * 10^41 <= nums[i] <= 10000 <= k <= 10^6

Pattern lesson

See the pattern, then code

Variable window counting

↗

Sliding Window

Longest, shortest, maximum, or minimum contiguous subarray or substring.. Because every element is at least 1, extending the window can only increase the product. So for each right end, shrink from the left until the product drops below k; then every subarray ending at right and starting anywhere in [left, right] is valid, adding right-left+1 to the count.

New words, made simpleKnow these before the algorithm

Contiguous subarray: A run of consecutive elements with no gaps.
Running product: The product of all elements currently inside the window.
Windows-ending-here counting: Adding right-left+1 to count every valid subarray that ends at the current right index.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Enumerate all subarrays

Quadratic; too slow for n up to 3*10^4 in the worst case.

For each start, extend the end and multiply, counting those under k.

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

Prefix products + binary search

Works but floating-point logs risk precision errors near the boundary.

Use log-prefix sums and binary search for each right end.

Time O(n log n)Space O(n)

Best choiceSliding window with running product

Exact integer arithmetic, linear time, constant space.

Maintain a window whose product stays < k and count windows ending at each index.

Time O(n)Space O(1)

The rule we keep true

Invariant

At the end of each iteration the window [left, right] is the longest window ending at right whose product is strictly less than k.

Why this is correct

Reasoning

All values are >= 1, so the product is monotonic as the window grows or shrinks. That monotonicity guarantees left never moves backward, giving an amortized linear scan. For each right, the number of valid subarrays ending there equals the window width, and summing across all right ends counts every qualifying subarray exactly once.

The algorithm in three movesSay these aloud before coding

1Return 0 immediately if k <= 1 (no positive product can be < 1)

right=3, product path: shrink until 5*2*6=60 < 100, left=1

2Multiply the running product by the entering element

subarrays ending at 3: [6],[2,6],[5,2,6] -> +3

3While the product is >= k, divide out the left element and advance left

running total = 8

4Add right - left + 1 to the answer for all valid subarrays ending at right

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

100

1 · Readx=10

2 · Askproduct < k?

3 · Update stateprod=10, left=0

4 · Resultcount += 1 (=1).

Key takeaway

At right index 3 the window [5,2,6] has product 60 < 100, contributing 3 subarrays.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 3-4Degenerate threshold
If k is 0 or 1, no product of positive integers can be strictly less, so return 0 and avoid an infinite shrink loop.
2
Lines 9-10Grow the product
Include the new right element in the running product.
3
Lines 11-13Shrink until valid
Divide out left elements while the product is too large, moving left rightward.
4
Lines 14Count windows ending here
Every start in [left, right] yields a valid subarray, so add right-left+1.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

k <= 1 returns 0
single-element array
all elements individually >= k (only shorter valid windows, possibly zero)
large products handled by Python big integers but still bounded by shrinking

Common beginner mistakes

Forgetting the k <= 1 guard, which causes an out-of-bounds shrink or infinite loop
Using >= vs > incorrectly: the loop must run while product >= k because the requirement is strictly less than k
Adding 1 instead of right-left+1 and thus undercounting longer valid windows
Assuming this works with zeros or negatives — it relies on all values being positive

Check your understanding

Why does adding right-left+1 count each valid subarray exactly once with no double counting?

Subarray Product Less Than K

Subarray Product Less Than K

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Sliding Window