LeetCode 713: Subarray Product Less Than K

Problem Restatement

We are given an integer array nums and an integer k.

We need to count how many contiguous subarrays have product strictly less than k.

A subarray must be contiguous. That means we can take a continuous segment of the array, not arbitrary elements.

For example:

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

The valid subarrays are:

[10]
[5]
[2]
[6]
[10, 5]
[5, 2]
[2, 6]
[5, 2, 6]

There are 8 valid subarrays.

Input and Output

The function shape is:

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        ...

Examples

Example 1:

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

Valid subarrays:

[10]
[5]
[2]
[6]
[10, 5]
[5, 2]
[2, 6]
[5, 2, 6]

Output:

8

Example 2:

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

All numbers are positive, so every subarray product is at least 1.

No product can be less than 0.

Output:

0

First Thought: Check Every Subarray

A direct approach is to enumerate every subarray.

For each start index i, multiply values from i to every possible end index j.

Whenever the product is less than k, count it.

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        count = 0

        for i in range(len(nums)):
            product = 1

            for j in range(i, len(nums)):
                product *= nums[j]

                if product < k:
                    count += 1
                else:
                    break

        return count

This works because all values in nums are positive, so once the product reaches k or more, extending the subarray can only keep it the same or make it larger.

Problem With Brute Force

The brute force method can still examine many subarrays.

If the array has n elements, the number of contiguous subarrays is:

n * (n + 1) / 2

So the worst-case time is:

O(n^2)

We need a faster method.

Key Insight

Because all numbers are positive, we can use a sliding window.

Maintain a window:

nums[left:right + 1]

and its product.

For every right, expand the window by multiplying nums[right].

If the product becomes greater than or equal to k, move left rightward and divide out nums[left] until the product is less than k again.

Once the window product is less than k, every subarray ending at right and starting between left and right is valid.

The number of such subarrays is:

right - left + 1

For example, suppose the current valid window is:

[5, 2, 6]

ending at 6.

The valid subarrays ending at 6 are:

[6]
[2, 6]
[5, 2, 6]

There are 3, equal to the window length.

Algorithm

Handle small k first.

Since every number in nums is positive, if:

k <= 1

then no subarray can have product less than k.

Return 0.

Otherwise:

1. Set left = 0.
2. Set product = 1.
3. Set count = 0.
4. For each right from 0 to len(nums) - 1:
   • Multiply product by nums[right].
   • While product >= k, divide by nums[left] and increment left.
   • Add right - left + 1 to count.
5. Return count.

Correctness

The algorithm maintains the invariant that after the while loop finishes, the window from left to right has product less than k.

When we extend the window by including nums[right], the product may become too large. Since all numbers are positive, removing elements from the left decreases or preserves the product. The while loop keeps removing leftmost elements until the product is less than k.

After this adjustment, the full window nums[left:right + 1] has product less than k.

Now consider any subarray ending at right whose start index is between left and right. This subarray is formed by removing zero or more elements from the left side of a valid positive-product window. Removing positive factors cannot increase the product, so each of these subarrays also has product less than k.

There are exactly right - left + 1 such subarrays.

Any subarray ending at right and starting before left is invalid, because left was advanced until the product became valid. Therefore the algorithm counts exactly all valid subarrays ending at each right.

Summing over all right counts every valid subarray exactly once, according to its ending index.

Complexity

Let n be the length of nums.

Implementation

class Solution:
    def numSubarrayProductLessThanK(self, nums: list[int], k: int) -> int:
        if k <= 1:
            return 0

        left = 0
        product = 1
        count = 0

        for right, value in enumerate(nums):
            product *= value

            while product >= k:
                product //= nums[left]
                left += 1

            count += right - left + 1

        return count

Code Explanation

The early return handles the impossible case:

if k <= 1:
    return 0

All numbers are positive, so every non-empty subarray product is at least 1.

We initialize the sliding window:

left = 0
product = 1
count = 0

Then we extend the right side:

for right, value in enumerate(nums):
    product *= value

If the product is too large, shrink from the left:

while product >= k:
    product //= nums[left]
    left += 1

After this loop, the current window product is less than k.

All valid subarrays ending at right are counted by:

count += right - left + 1

Finally:

return count

Example Walkthrough

Use:

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

Start with:

left = 0
product = 1
count = 0

At right = 0, value 10:

product = 10

Window [10] is valid.

Add:

right - left + 1 = 1

Count is 1.

At right = 1, value 5:

product = 50

Window [10, 5] is valid.

Valid subarrays ending here:

[5]
[10, 5]

Add 2.

Count is 3.

At right = 2, value 2:

product = 100

This is not valid because the condition is strictly less than 100.

Shrink from the left:

product = 100 // 10 = 10
left = 1

Window [5, 2] is valid.

Valid subarrays ending here:

[2]
[5, 2]

Add 2.

Count is 5.

At right = 3, value 6:

product = 60

Window [5, 2, 6] is valid.

Valid subarrays ending here:

[6]
[2, 6]
[5, 2, 6]

Add 3.

Final count is:

8

Testing

def test_num_subarray_product_less_than_k():
    s = Solution()

    assert s.numSubarrayProductLessThanK([10, 5, 2, 6], 100) == 8
    assert s.numSubarrayProductLessThanK([1, 2, 3], 0) == 0
    assert s.numSubarrayProductLessThanK([1, 1, 1], 2) == 6
    assert s.numSubarrayProductLessThanK([100], 100) == 0
    assert s.numSubarrayProductLessThanK([99], 100) == 1
    assert s.numSubarrayProductLessThanK([2, 5, 3, 10], 30) == 6

    print("all tests passed")

test_num_subarray_product_less_than_k()

Test coverage: